# Improved Networks Routing Using an Arrow-Based Description
## 5 Routing Algorithm Using Arrows
### Series-Parallel Composition of Graph Arrows  
We can combine the two basic operations we described in the previous sections.  
We begin from the complex graph in Figure 8a. By a serial composition on the first three nodes we would obtain the graph in Figure 8b. The parallel composition of the arrows in the right-most node yields Figure 8c. Finally, a renewed serial composition yields the arrow in Figure 8d.  
We note that using a sequence of serial and parallel compositions based on arrow addition will ultimately turn a complex planar graph into a simple one, as it will eliminate self-loops and parallel links.  
Figure 8: (a-d) Series-parallel composition of graph arrows. Reprinted with permission from [1].  
Figure 6: (a,b) Serial composition of graph arrows. Reprinted with permission from [1].  
Figure 7: (a,b) Parallel composition of graph arrows. Reprinted with permission from [1].  
The following Algorithm 1 describes the path finding using graph arrows:  
```
Input: the starting node \(n_{s}\) and the end node \(n_{e}\);  Determine the cycles containing \(n_{s}\) and \(n_{e}\);  Determine the cycles paths comprising both \(n_{s}\) and \(n_{e}\) using cycles mergers;  If there is no path, then STOP and print \"No path found\";  Once a path is found, translate the list of graph arrows to sets T and H as discussed.  By successive applications of the KMP algorithm as described above, find a direct and a return path between the nodes; Output: the path discovered.
```  
**Algorithm 1**The path finding using graph arrows.  
The following observations apply (see [6]):  
1. Each time, the number of cycles limits the iterations to less than C.
2. The end criteria of the program can be flexible such that it can be stopped whenever a first path is found or alternatively it can be run until a path with a specific length is obtained.  
Because of the linear costs of the KMP algorithm, the overall cost of finding the longest path becomes \(O\!\left(N^{2}\right)\)--the algorithm has linear complexity and it must be run at most \(N\) times. Obviously, the additional finding that the Knuth-Morris-Pratt algorithm adds nothing to the complexity encourages us to say that there are good prospects that the algorithm may be used in real-time systems.  
[PERSON]'s algorithm [13, 14] describes how to find a path between a source node and an end node in a given graph. Its complexity depends on graph sparsity and on data representation and in the most optimistic case its complexity is O(N). This algorithm, however, only finds the shortest path in a graph, yielding thus the same result consistently if the graph, the source, and the end nodes are unchanged. This does not, therefore, take into account particularities of the telecom network, which requires redundant paths to avoid collisions and congested traffic. If run on all the nodes, [PERSON]'s algorithm has a worst-case complexity of O(N\({}^{2}\)), as with the algorithm presented in this paper.  
Incidentally, let us observe that the Algorithm 1 presented in this paper also provides for a return path which is different that the direct path and therefore any collision that may occur can be avoided.