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 may 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ò
