10 Lessons About C++(2015)
Chapter 9: Path finding in networks
A frequently occurring requirement in solving network optimization problems is to find all path combinations that contain no cycles between a selected pair of communicating end nodes. An additional factor in finding all combinations of paths is that the algorithm should be able to handle both directed or undirected graphs. 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 seatch to find all non-cyclical paths between arbitrary pairs of nodes.
Problem definition: Find all simple paths from a starting vertex (source) to a destination vertex (sink) in a directed graph. In an undirected graph, find all simple paths between two vertices.
Network connectivity is modeled using a Graph class as the means to uniquely identify individual links, as well as add new links and check for the presence of existing links. It also involves setting a graph’s directed/undirected status of added links.
The algorithm used for identifying and enumerating paths uses using a recursive depth-first search . The search avoids repeating vertices (nodes) by marking them with a boolean visited value as they are visited during the recursion, then unmarking the node just before returning from the recursive call.
DepthFirstSearch( Graph G, vertex v )
{
Set vertex v as visited;
For ( each neighbor vertex w of v )
{
If ( vertex w is unvisited )
{
DepthFirstSearch( w );
Add edge vw to tree T
}
}
}
Practical application of the depth-first algorithm
Beginning from the start node, the depth first search algorithm examines all outgoing links and progresses by expanding the first child node of the search tree that appears. It searches 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.
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:
#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;
}
This gives 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 the same way as shown in this main.cpp example:
#include "Algorithm.h"
#include <iostream>
#include <vector>
const Link<int> linkset[] = { Link<int>( 1, 2 ),
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;
}
This gives 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. Themin_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 possible enhancement could be to allow the nodes to be labeled as string variables as well as integers. Consider the following 9-node network representing UK towns and cities:
Given that we want to label the nodes to give a more meaningful description, it is possible to maintain a two-way mapping between the integer used to uniquely identify each node created and the text 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. The usage would be 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;
}
This gives 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:
To find all paths that start from the node 2 and return to node 2, an example 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;
}
This gives the list of all found paths to and from the node labelled 2:
If you would rather not have paths such as 2 - 1 - 2 then specify a minimum hop count of 3:
algorithm.GetAllPaths( &nw, 2, 2, -1, 3 );
Which would give the following path list:
Full Code listings
Graph.h
#pragma once
#include "PriorityQueue.h"
#include <vector>
#include <memory>
class Edge
{
public:
int v, w;
double wt;
Edge(int v = -1, int w = -1, double wt = 0.0) :
v(v), w(w), wt(wt) { }
};
typedef std::shared_ptr<Edge> EdgePtr;
template <class Edge>
class DenseGRAPH
{
private:
int Vcnt, Ecnt;
bool digraph;
std::vector <std::vector <EdgePtr>> adj;
public:
DenseGRAPH(int V, bool digraph = false) :
adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
{
for ( int i = 0; i < V; i++ ) {
adj[ i ].resize( V );
}
}
int V() const { return Vcnt; }
int E() const { return Ecnt; }
bool directed() const { return digraph; }
void insert( EdgePtr e )
{
int v = e->v;
int w = e->w;
if (adj[v][w] == 0) Ecnt++;
adj[v][w] = e;
if (!digraph)
adj[w][v] = e;
}
void remove(EdgePtr e)
{
int v = e->v; int w = e->w;
if (adj[v][w] != 0) Ecnt--;
adj[v][w] = 0;
if (!digraph) adj[w][v] = 0;
}
EdgePtr edge(int v, int w) const
{
return adj[v][w];
}
class adjIterator;
friend class adjIterator;
};
template <class Edge>
class DenseGRAPH<Edge>::adjIterator
{
private:
const DenseGRAPH &G;
int i, v;
public:
adjIterator(const DenseGRAPH<Edge> &G, int v) :
G(G), v(v), i(0) {}
EdgePtr beg() { i = -1; return nxt(); }
EdgePtr nxt()
{
for (i++; i < G.V(); i++)
if (G.edge(v, i))
return G.adj[v][i];
return 0;
}
bool end() const { return i >= G.V(); }
};
PriorityQueue.h
#include <memory>
#include <vector>
template <class keyType>
class PriorityQueue
{
private:
int d, N;
std::vector<int> pq, qp;
const std::vector<keyType> &a;
void Exchange(int i, int j)
{
int t = pq[i];
pq[i] = pq[j];
pq[j] = t;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
void fixUp(int k)
{
while ( k > 1 && a[pq[(k+d-2)/d]] > a[pq[k]] )
{
Exchange(k, (k+d-2)/d);
k = (k+d-2)/d;
}
}
void fixDown(int k, int N)
{
int j;
while ((j = d*(k-1)+2) <= N)
{
for (int i = j+1; i < j+d && i <= N; i++)
if (a[pq[j]] > a[pq[i]])
j = i;
if (!(a[pq[k]] > a[pq[j]]))
break;
Exchange(k, j);
k = j;
}
}
public:
PriorityQueue(int N, const std::vector<keyType> &a, int d = 3) :
a(a), pq(N+1, 0), qp(N+1, 0), N(0), d(d) {}
int empty() const { return N == 0; }
void insert(int v)
{
pq[++N] = v;
qp[v] = N;
fixUp(N);
}
int getmin()
{
Exchange( 1, N );
fixDown(1, N-1);
return pq[N--];
}
void lower(int k)
{
fixUp(qp[k]);
}
};
Network.h
#pragma once
#include "Graph.h"
#include <vector>
#include <map>
#include <string>
typedef std::vector<int> Path;
typedef std::vector<Path> PathSet;
typedef std::vector<Path>::const_iterator Paths;
template< class T >
class Link
{
private:
T from;
T to;
double weight;
public:
Link( const T& from, const T& to, const double &weight = 1.0 ) :
from( from ), to( to ), weight( weight ) {}
const T& From() const
{ return from; }
const T& To() const
{ return to; }
const double& Weight() const
{ return weight; }
};
class Network
{
private:
DenseGRAPH<Edge>* graph;
PathSet pathset;
std::map<std::string, int > label2index;
std::map<int, std::string > index2label;
public:
Network() {}
Network( const std::vector<Link<std::string> >& links,
const bool& bi = false );
Network( const std::vector<Link<int> >& links,
const bool& bi = false );
~Network();
void AddPath( const Path& p );
void ShowPaths() const;
int NodeIndex( const std::string& label ) const;
std::vector<int> GetAdjNodeIDs( const int& n ) const;
};
Network.cpp
#include "Network.h"
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <set>
#include <stack>
Network::~Network()
{
if ( graph != NULL ) {
delete graph;
graph = NULL;
}
}
Network::Network( const std::vector<Link<std::string>>& links,
const bool& bi_connected )
{
typedef std::vector<Link<std::string>>::const_iterator v_iter;
label2index.clear();
index2label.clear();
std::set<std::string> unique_id_str;
for ( v_iter it = links.begin(); it != links.end(); ++it ) {
const Link<std::string> l = (*it);
std::string first = l.From();
std::string second = l.To();
unique_id_str.insert( first );
unique_id_str.insert( second );
}
int i = 0;
for ( std::set<std::string>::const_iterator it = unique_id_str.begin();
it != unique_id_str.end();
++it )
{
std::string label = (*it);
index2label[ i ] = label;
label2index[ label ] = i;
i++;
}
std::set<int> unique_ids;
const int nodes = unique_id_str.size();
graph = new DenseGRAPH<Edge>( nodes + 1, !bi_connected );
for ( v_iter it = links.begin(); it != links.end(); ++it )
{
const Link<std::string> l = (*it);
std::string first = l.From();
std::string second = l.To();
int s = label2index.find( first )->second;
int d = label2index.find( second )->second;
double weight = l.Weight();
EdgePtr e( new Edge( s, d, weight ) );
graph->insert( e );
}
}
Network::Network( const std::vector<Link<int>>& links,
const bool& bi_connected )
{
typedef std::vector<Link<int>>::const_iterator v_iter;
label2index.clear();
index2label.clear();
std::set<std::string> unique_id_str;
for ( v_iter it = links.begin(); it != links.end(); ++it )
{
const Link<int> l = (*it);
int first = l.From();
int second = l.To();
std::string strFirst = static_cast<std::ostringstream*>(
&(std::ostringstream() << first ) )->str();
std::string strSecond = static_cast<std::ostringstream*>(
&(std::ostringstream() << second ) )->str();
unique_id_str.insert( strFirst );
unique_id_str.insert( strSecond );
}
int i = 0;
for ( std::set<std::string>::const_iterator it = unique_id_str.begin();
it != unique_id_str.end();
++it )
{
std::string label = (*it);
index2label[ i ] = label;
label2index[ label ] = i;
i++;
}
std::set<int> unique_ids;
const int nodes = unique_id_str.size();
graph = new DenseGRAPH<Edge>( nodes + 1, !bi_connected );
for ( v_iter it = links.begin(); it != links.end(); ++it ) {
const Link<int> l = (*it);
int first = l.From();
int second = l.To();
std::string strFirst = static_cast<std::ostringstream*>(
&(std::ostringstream() << first ))->str();
std::string strSecond = static_cast<std::ostringstream*>(
&(std::ostringstream() << second ))->str();
int s = label2index.find( strFirst )->second;
int d = label2index.find( strSecond )->second;
double weight = l.Weight();
EdgePtr e( new Edge( s, d, weight ) );
graph->insert( e );
}
}
void Network::AddPath( const Path& p )
{
pathset.push_back( p );
}
// Get the set of nodes adjacent to this node
std::vector< int > Network::GetAdjNodeIDs( const int& n ) const
{
std::vector< int > adj;
DenseGRAPH<Edge>::adjIterator A(*graph, n );
for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() ) {
const int s = e->v;
const int d = e->w;
if ( !graph->directed() && ( s == n || d == n ) ) {
adj.push_back( s == n ? d : s );
}
else if ( s == n ) {
adj.push_back( d );
}
}
return adj;
}
// Output the set of paths found
void Network::ShowPaths() const
{
for ( Paths paths = pathset.begin();
paths != pathset.end();
++paths )
{
Path path = *paths;
for ( std::vector<int>::const_iterator it = path.begin();
it != path.end();
++it )
{
int n = (*it);
std::string node_str = index2label.find( n )->second;
std::cout << node_str << " ";
}
std::cout << std::endl;
}
}
int Network::NodeIndex( const std::string& label ) const
{
int n = label2index.find( label )->second;
return n;
}
Algorithm.h
#include "Network.h"
#ifndef ALGORITHM_H
#define ALGORITHM_H
class Algorithm
{
public:
Algorithm() {}
Algorithm( Network* network );
void GetAllPaths( Network* network,
const std::string& start,
const std::string& target,
const int& max_hops,
const int& min_hops );
void GetAllPaths( Network* network,
const int& start,
const int& target,
const int& max_hops,
const int& min_hops );
private:
void DepthFirst( Network* network,
Path& visited,
const int& end,
const int& max_hops,
const int& min_hops );
void SetNetwork( Network* network );
bool ContainsNode( Path& nodes, const int& node );
Network *nw;
int startNodeId;
};
#endif /* ALGORITHM_H */
Algorithm.cpp
#include <iostream>
#include <sstream>
#include <iterator>
#include "Algorithm.h"
Algorithm::Algorithm( Network* network )
{
SetNetwork( network );
}
void Algorithm::SetNetwork( Network* network )
{
nw = network;
}
// 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 breadth-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 );
}
}
bool Algorithm::ContainsNode( Path& nodes, const int& node )
{
for ( std::vector<int>::const_iterator nodes_it = nodes.begin();
nodes_it != nodes.end(); nodes_it++ )
{
if ( (*nodes_it) == node ) return true;
}
return false;
}
void Algorithm::GetAllPaths( Network* network,
const std::string& start,
const std::string& target,
const int& max_hops,
const int& min_hops )
{
int s = network->NodeIndex( start );
int d = network->NodeIndex( target );
startNodeId = s;
Path visited;
visited.push_back( s );
DepthFirst( network, visited, d, max_hops, min_hops );
}
void Algorithm::GetAllPaths( Network* network,
const int& start,
const int& target,
const int& max_hops,
const int& min_hops )
{
std::string strFirst = static_cast<std::ostringstream*>(
&(std::ostringstream() << start ) )->str();
std::string strSecond = static_cast<std::ostringstream*>(
&(std::ostringstream() << target ) )->str();
int s = network->NodeIndex( strFirst );
int d = network->NodeIndex( strSecond );
startNodeId = s;
Path visited;
visited.push_back( s );
DepthFirst( network, visited, d, max_hops, min_hops );
}
Chapter Summary
To summarize this master lesson, you have:
·Implemented a recursive algorithm to solve the “all simple paths” problem in C++.
·Made further refinements and enhancements to present the results in different ways, such as labeling nodes with meaningful names.
·Applied further adjustments such as finding all paths going out from and returning to the same node or how to constrain the paths found to a maximum number of hops.