**Problem Outline**

This I tackled previously when working on the design and implementation of routing optimization algorithms for telecommunications networks. Given that a wide area network with nodes and interconnecting links can be modelled as a graph with vertices and edges, the problem is to find all path combinations(containing no cycles) between selected pairs of communicating end nodes. Please note that this is not a problem of just finding the shortest paths between nodes, for which Dijkstra’s algorithm can be readily employed.

An additional factor in finding all paths is that the algorithm should be able to handle both directed graphs or graphs whose edges are assumed to be bi-directional.

Downloadable implementations of this algorithm are available in C++ and C#/.NET. See download link below.

**The graph searching algorithm**

The National Institute of Standards and Technology (NIST) online Dictionary of Algorithms and Data Structures describes this particular problem as “all simple paths” and recommends a depth-first search to find all non-cyclical paths between arbitrary pairs of nodes.

**Modelling Networks**

The network connectivity is modelled using the following `Network `

class which uses a Sedgewick’s implementation of a `Graph`

class as the means to uniquely identify individual links, as well as add new links and check for the presence of links. The `Network `

class can also set the bi-directional status of the links that are added and store each path found by the graph searching algorithm:

#pragma once #include "Graph.h" #include <vector> #include <map> #include <string> typedef std::pair< int, int> Link; typedef std::vector<int> Path; typedef std::vector<Path> PathSet; typedef std::vector<Path>::const_iterator Paths; class Network { private: DenseGRAPH<Edge>* graph; PathSet pathset; public: Network() {} Network( const std::vector<Link>& links, const bool& bi = false ); ~Network(); void AddPath( const Path& p ); void ShowPaths() const; std::vector<int> GetAdjNodeIDs( const int& n ) const; };

**The depth-first algorithm**

As can be seen from the code sample, beginning from the start node, the algorithm examines all outgoing links and progresses by expanding the first child node of the search tree that appears, searching progressively deeper until a target node is found, or until it encounters a node that has no children. The search then backtracks, returning to the most recent node it hasn’t finished exploring.

The `max_hops`

and `min_hops`

arguments passed to `DepthFirst`

method can be used to filter the sets of paths found by their maximum and minimum number of hops respectively; otherwise thse parameters are set to -1, then no such restrictions are imposed on the path searches, and all possible paths are found.

// Algorithm to recursively search for all paths between // chosen source - destination nodes void Algorithm::DepthFirst( Network* network, Path& visited, const int& end, const int& max_hops, const int& min_hops) { const int back = visited.back(); std::vector< int > adjNode = network->GetAdjNodeIDs( back ); // Examine adjacent nodes for ( std::vector<int>::const_iterator node_it = adjNode.begin(); node_it != adjNode.end(); node_it++ ) { const int node = (*node_it); bool startEqualTarget = ContainsNode( visited, node ) && startNodeId == end && node == startNodeId; if ( ContainsNode( visited, node ) && !startEqualTarget ) continue; if ( node == end ) { visited.push_back( *node_it ); // Get hop count for this path const int size = (int) visited.size(); const int hops = size - 1; if ( ( max_hops < 1 || hops <= max_hops ) && hops >= min_hops ) { Path path( visited.begin(), visited.begin() + size ); network->AddPath( path ); } visited.erase( visited.begin() + hops ); break; } } // in depth-first, recursion needs to come after visiting adjacent nodes for ( std::vector<int>::const_iterator node_it = adjNode.begin(); node_it != adjNode.end(); node_it++ ) { int node = (*node_it); if ( ContainsNode( visited, node ) || node == end ) continue; visited.push_back( node ); DepthFirst( network, visited, end, max_hops, min_hops ); int n = (int) visited.size() - 1; visited.erase( visited.begin() + n ); } }

**Example 1: network topology with uni-directional links**

Here is the graphical representation of a 5-node directed graph problem used in the example presented here:

In the main main program loop, the network was set as having directed edges which are inserted using calls to the Network object’s AddLink method. For example a directed edge exists between nodes [1,3], but not nodes [3,1], hence the single arrow between the node [1,3] pair. Directed edges exist between nodes [1,2] and nodes [2,1], hence the bi-directional link between them.

To find all possible combinations of paths between nodes [2,5] for example, we simply set the start and target nodes and feed the `GetAllPaths`

method with them. The -1 value passed to `GetAllPaths`

signifies that we do not wish to filter any of the search results for maximum number of hops, but return all possible paths it finds.

Example `main.cpp`

usage shown in the following code:

#include "Algorithm.h" #include <iostream> #include <vector> const Link<int> linkset[] = { Link<int>( 1, 2 ), Link<int>( 1, 3 ), Link<int>( 1, 4 ), Link<int>( 2, 1 ), Link<int>( 2, 4 ), Link<int>( 2, 3 ), Link<int>( 3, 5 ), Link<int>( 4, 5 ), Link<int>( 5, 3 ) }; const size_t size = sizeof( linkset ) / sizeof( linkset[ 0 ] ) ; const std::vector<Link<int>> links (linkset, linkset + size ); int main() { // Create network from interconnections given Network nw( links, false ); // Create the algorithm object Algorithm algorithm( &nw ); // Get all paths between nodes 2 and 5 algorithm.GetAllPaths( &nw, 2, 5, -1, -1 ); // Output the set of paths found nw.ShowPaths(); return 0; }

Giving the following output for finding all paths between nodes 2 and 5:

**Example 2: network topology with bi-directional links**

Using a very simple tweak we can also construct network topologies with link interconnections that are are *bi-directional*; that is, a link between [1,2] is the same as the link between [2,1]. In other words, adding link [2,1] when link [1,2] already exists will make no difference.

Simply, set the bi-directional flag in the `Network`

class constructor to `true`

, and build the network in the same way, as shown in this next `main.cpp`

example:

#include "Algorithm.h" #include <iostream> #include <vector> const Link<int> linkset[] = { Link<int>( 1, 2 ), Link<int>( 2, 1 ), // [1,2] = [2,1] Link<int>( 1, 4 ), Link<int>( 1, 7 ), Link<int>( 2, 4 ), Link<int>( 2, 3 ), Link<int>( 3, 5 ), Link<int>( 3, 8 ), Link<int>( 4, 5 ), Link<int>( 4, 9 ), Link<int>( 5, 6 ), Link<int>( 5, 7 ), Link<int>( 5, 9 ), Link<int>( 6, 8 ), Link<int>( 6, 10 ), Link<int>( 7, 8 ), Link<int>( 8, 10 ), Link<int>( 9, 10 ) }; const size_t size = sizeof( linkset ) / sizeof( linkset[ 0 ] ) ; const std::vector<Link<int>> links (linkset, linkset + size ); int main() { // Create network from interconnections given Network nw( links, true ); // Create the algorithm object Algorithm algorithm( &nw ); // Get all paths between nodes 2 and 5 algorithm.GetAllPaths( &nw, 2, 5, -1, -1 ); // Output the set of paths found nw.ShowPaths(); return 0; }

Giving the following output for finding all paths between nodes 2 and 5:

**Example 3: filtering by the maximum number of hops**

We may wish to restrict paths found to those whose maximum hop count is no larger than a set maximum, say 4 hops.

By using another simple tweak we can achieve this. Simply set the `max_hops`

argument that is passed to `Algorithm::GetAllPaths`

to some value greater than zero. The `min_hops`

argument is kept as default -1::

algorithm.GetAllPaths( &nw, 2, 5, 4, -1 );

Re-running the program with the same network as in example 2, gives the following paths, restricted to a maximum of 4 hops:

**Example 4: Labeling network nodes arbitrarily**

A recent improvement to the software has been to allow the user to label the nodes arbitrarily as standard strings, or as integers. Either way, it is no longer a requirement for the nodes to be labelled as an ascending order of integers of say 1-5 for a five node network. You can now call them what you like.

For example, Consider the following 9-node network representing towns and cities in the UK:

It is no longer necessary to label the nodes using integers, but can be done using strings to give a more meaningful description. There now exists a two-way mapping between the integer used to uniquely identify each node created and the string/integer label used to describe it.

Supposing we wish to construct the above network and find all possible paths between Bristol and Edinburgh for an undirected representation of the graph, then the usage is as follows:

#include "Algorithm.h" #include <iostream> #include <vector> const Link<std::string> linkset[] = { Link<std::string>( "Bristol", "London" ), Link<std::string>( "Bristol", "Cardiff" ), Link<std::string>( "Oxford", "Cardiff" ), Link<std::string>( "Glasgow", "Manchester" ), Link<std::string>( "Manchester", "Leeds" ), Link<std::string>( "Manchester", "Cardiff" ), Link<std::string>( "Glasgow", "Edinburgh" ), Link<std::string>( "Edinburgh", "Newcastle" ), Link<std::string>( "Leeds", "London" ), Link<std::string>( "Newcastle", "Leeds" ) }; const size_t size = sizeof( linkset ) / sizeof( linkset[ 0 ] ) ; const std::vector<Link<std::string>> links (linkset, linkset + size ); int main() { // Create network from interconnections given Network nw( links, true ); // Create the algorithm object Algorithm algorithm( &nw ); // Get all paths between nodes Bristol and Bath algorithm.GetAllPaths( &nw, "Bristol", "Edinburgh", -1, -1 ); // Output the set of paths found nw.ShowPaths(); return 0; }

Giving the following output:

Example 5: Finding all paths between the same node

You may wish to find all paths between the same node. Take the following network with bi-directional links:

You my wish to find all paths that start from the node 2 that return to node 2. Example usage is shown here:

#include "Algorithm.h" #include <iostream> #include <vector> const Link<int> linkset[] = { Link<int>( 1, 2 ), Link<int>( 1, 3 ), Link<int>( 1, 4 ), Link<int>( 2, 1 ), Link<int>( 2, 4 ), Link<int>( 2, 3 ), Link<int>( 3, 5 ), Link<int>( 4, 5 ), Link<int>( 5, 3 ) }; const size_t size = sizeof( linkset ) / sizeof( linkset[ 0 ] ) ; const std::vector<Link<int>> links (linkset, linkset + size ); int main() { // Create network from interconnections given Network nw( links, true ); // Create the algorithm object Algorithm algorithm( &nw ); // Get all paths between nodes 2 and 5 algorithm.GetAllPaths( &nw, 2, 2, -1, -1 ); // Output the set of paths found nw.ShowPaths(); return 0; }

Giving the list of all found paths to and from node labelled 2:

If you would rather not have paths such as 2 – 1 – 2 then just specify a minimum hop count of 3:

algorithm.GetAllPaths( &nw, 2, 2, -1, 3 );

Which would give the following path list:

**Download C++ (Visual Studio 2010 and Linux NetBeans) and C#/.NET implementations:**

Comments and feedback welcome. Some testimonials:

*“Hi Andy,
The program ran beautifully with my file input today. It traced all possible paths for 11,169 source-destination pairs in well under a minute … I still have more to do on the project, but you saved me so much time, and I deeply appreciate that. Sincerely, Julia”*

Julia L. Chariker

Professor of Psychology, University of Louisville, KY

*“Thank you [Andrew]. It works perfectly …”*

Jeandre Prinsloo

*“Hi Andrew,
Sorry for the late reply, but I had a hard week of work and I forgot to reply…
I want to thank you for the code, it really is very efficient and easy to use, I’ve solved a big problem of searching nodes!
Thank you very much, your work is great and help me a lot!”*

Michele Condò

I really like this algoriithm but the problem is I’m working with java on my final year project and will appreciate it if I can get the java version or a general algorithm to implement for the depth first algorithm thanks very much.

I’ve not yet tackled this in Java but if it helps, StackOverflow may contain one or two articles on this.

I really like this algoriithm but the problem is I’m working with C++ on my Thesis and will appreciate it if I can get the C++ or a general algorithm to implement for the depth first algorithm.

do you can send this C++ version of this algorithm for me?

thanke you so much

C# download is now available. Not Java but should not be too dissimilar.

Where can i download code in C#?

Hi the C++ and C# projects are contained in the same download.

I love your code, but I don’t understand something there. what is containsNode and there is no such function of containsNode in the declaration functions. could you explain me why?

Thanks A lot..!

Hi Moses, ContainsNode I think is a simple test to test for the presence or absence of a specific node. It is to be found in the downloadable code, this article contains only selected aspects.

Very nice code. Easy to understand.

How is the stability of this algorithm, say for graphs with more than thousand nodes?

Will it work for undirected graphs…currently m doing project on undirected graphs/networks in telecommunication networks area…thats why…kindly can u give a solution for finding all combination of paths between source and sink node.

Yes it will, directed or undirected graphs. You simply set the bi_direction flag to true or false depending on what your needs are, done via the Network class.

Sir

Can I get this code for matrix representation of graph. Please.

Thank You in anticipation.

Hi Himanshu

Yes, you probably can. This algorithm uses Sedgewick’s implementation of a Graph class, which can either be implemented using an adjacency matrix, or an adjacency list.

Andy

Hi there, I’m just wondering if there are any iterative ways to achieve the same thing since recursion may be time-expensive when the graph is big. Thank you!

Hi Thao, the recursive approach is really the only approach that I know of, although it must be possible to come up with an iterative approach? Have you tried searching the online forums or StackOverflow for example? I’d be interested to find out.

An alternative may be to just consider a subset of the total possible paths as in k-shortest paths?

I’ve tried searching but seems like this is the only way to do it. Thanks anyway

I’m looking for an Algorithm to Find all Paths Between Two Given Nodes

in a directd acyclic graph in matlab,but it seems there is nobody in all over the world, who can help me:(((((((((((((((

I need it ASAP.

How about this:

http://www.mathworks.co.uk/matlabcentral/newsreader/view_thread/315198

Finding all possible paths using Yen’s algorithm in Matlab

Thanks u verrrrrrrrrry much,Finally I did it with some modification in the function that u commented,u don’t know how much I am thankful,God bless u and wishing the best for u.

BIG TNX

You’re welcome. Hope it goes well.

Hi Hoda

I have your problem too.plz help me

I want this code in MATLAB.

Thanks and Best regards.

my Email: v.hamidreza66@gmail.com

Hi !

Listed in the downloads sections, there’s a link titled “Implementing Dijkstra’s Algorithm using Sedgewick’s C++ Code”, which I presume was the basis of this algorithm. I’ve tried adding the Network.h class and Algorithm.h class using the code listed above, and changing the Main.cpp with the code in “Example 5: Finding all paths between the same node”, however, when compiling with Code::Blocks or Dev-C++, I get a load of errors (I have to mention that my coding skills are equal to zero; but I really need the algorithm on a personal project) . Is the code supposed to run only on Visual Studio or is it something that I’m missing ?

Hi Adrian

There is an implementation of Dijkstra that comes with this, but this is not the same as the all paths problem. So far I have only provided this in Visual Studio 2010 and as a Linux-based NetBeans project. I will investigate looking at other IDEs like Code:Blocks and Eclipse when I get the chance.

Andy

hi,

This algorithm looks great. Can you provide the map reduce map-reduce implementation of this algorithm in java.

Hi the downloadable implementation of this is now available in C#. Andy.

For example i have lots of paths in one file like

file 1

1,2,4

4,5,6

And in 2nd file i have string like

file2

1,2,6

How can i find this string of file 2 in file 1

which is a path in file 1 when two strings are combined

1,2,4,4,5,6—–>1,2,6 is present in this string

How can i do this in python?? Kindly help me through this. I am stuck at this point

good job!I have been looking for it for a long time.

Sir,

Have been finding it difficult to write a code in C# to develop a grid network illustrating the road network consisting of 100vertices and 360edges for an agent which has a start and goal location. please sir, can you help me out.

Thanks

Hi the download contains the C# project in addition to the C++ versions, but please remember that this problem is NP hard – ie cannot be solved in polynomial time, and you will find that time taken to solve the problem increases exponentially with the number of nodes – this might be an issue with the size of the problem you have in mind – unless it is a directed acyclic graphs in which case it can be solved in linear time.

Hi,

I want the source code. How to make payment to buy this code? I can not pay in USD. Will it be secured payment through the link provided?

Heyy,

I would like to know more about this …

hi,

is it possible to have the output paths in specific order for example number of hops in increasing order, or they should be sorted later?

and also if the graph is weighted, dose the code return the weight of each path? (needed for sorting)

Hi yes it should be possible to do the things you state. The way I would do it would be to modify the data structures to add on the weight metric for each path and sort them after all paths have been found either by weight value or the number of hops.