10 Lessons About C++(2015)

Chapter 4: Practical Applications of Graph Algorithms

A graph is a data structure that is used to represent networks and their interconnections. Network nodes are frequently known as vertices, while the links connecting them are known as edges or sometimes arcs. In practical scenarios, graphs can be used to model telecommunications networks, transportation systems, water distribution networks (pipes) and electrical wiring amongst other things. Graphs are usually visually represented as a series of dots or circles representing the vertices and lines drawn between them to represent the edges, sometimes using arrows to indicate direction.

4.1 Modeling Networks as Graphs

This example Graph class is based on Sedgewick’s C++ implementation2, specifically, the DenseGRAPH class. Sedgewick’s implementation (see https://www.cs.princeton.edu/~rs/Algs3.cxx5/code.txt) specifically track the number of edges and vertices, have methods for inserting and removing edges, and use an adjacency matrix or adjacency list to track interconnections between vertices. I have modified the class slightly to allocate Edge objects as smart pointers to ensure memory is deallocated upon completion.

#include <vector>

// This code is from "Algorithms in C++, Third Edition,"

// by Robert Sedgewick, Addison-Wesley, 2002.

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(); }

};

Representations of network topologies can be created by creating an instance of DenseGRAPH (renamed as Graph) and adding the sets of edges:

#include "Graph.h"

#include <iostream>

int main()

{

Graph<Edge>* graph = new Graph<Edge>( 5, false );

graph->insert( EdgePtr( new Edge( 0, 1 ) ) );

graph->insert( EdgePtr( new Edge( 1, 2 ) ) );

graph->insert( EdgePtr( new Edge( 2, 3 ) ) );

graph->insert( EdgePtr( new Edge( 3, 4 ) ) );

graph->insert( EdgePtr( new Edge( 0, 4 ) ) );

std::cout << "No. vertices = " << graph->V() << std::endl;

std::cout << "No. edges = " << graph->E() << std::endl;

EdgePtr edgePtr = graph->edge( 2, 3 );

return 0;

4.2 Implementing Dijkstra’s Algorithm

Dijkstra’s algorithm solves the shortest path problem for a graph with non-negative edge weights by producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms such as the k-shortest paths algorithm. We build a shortest path tree (SPT) one edge at a time by always taking the next edge that gives a shortest path from the source to a vertex not on the SPT. In other words, we add vertices to the SPT in order of their distance (through the SPT) to the start vertex.

The original Dijkstra’s algorithm did not use min priority queues and was of complexity O(|V|2), where V is the number of vertices. This performance was later improved by the use of linked-list representations and min priority queues. Edges that connect tree vertices to nontree vertices are stored using a priority queue implementation that allows for the updating of priorities.

This implementation initially finds all shortest paths within the constructor of the SPT template class and uses a priority queue of vertices held in order of their distance from the source node. This determines all the shortest paths from the source node.

The queue is initialized with priority 0 for the source node and priority infinity for the other nodes. The implementation then enters a loop whereby the lowest-priority node from the queue is moved to the SPT and relaxed along its incident edges. To relax an edge v->w means to test whether the best known way to get from s to w is to go from s to v, and then go from v to w. If so, we update our data structures.

#include "Graph.h"

template <class Graph, class Edge>

class SPT

{

private:

const Graph &G;

std::vector<double> wt;

std::vector<EdgePtr> spt;

public:

SPT(const Graph& G, int s) :

G(G),

spt(G.V()),

wt(G.V(), G.V())

{

PQi<double> pQ(G.V(), wt);

for (int v = 0; v < G.V(); v++)

{

pQ.insert(v);

}

wt[s] = 0.0;

pQ.lower(s);

while (!pQ.empty())

{

int v = pQ.getmin();

if ( v != s && spt[v] == 0 ) return;

typename Graph::adjIterator A(G, v);

for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() )

{

int w = e->w;

double P = wt[v] + e->wt;

if ( P < wt[w] )

{

wt[w] = P;

pQ.lower(w);

spt[w] = e;

}

}

}

}

EdgePtr pathR(int v) const

{

return spt[v];

}

double dist(int v) const

{

return wt[v];

}

};

Suppose we wish to use the Graph data structure to represent the following network nodes and interconnections:

We can represent this by building a Graph structure with calls to the insert function:

std::auto_ptr< Graph<Edge> > graph( new Graph<Edge>( 8, true ) );

graph->insert( EdgePtr( new Edge( 1, 6, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 1, 2, 2.5 ) ) );

graph->insert( EdgePtr( new Edge( 1, 4, 3.0 ) ) );

graph->insert( EdgePtr( new Edge( 1, 5, 0.5 ) ) );

graph->insert( EdgePtr( new Edge( 2, 1, 0.5 ) ) );

graph->insert( EdgePtr( new Edge( 2, 3, 3.0 ) ) );

graph->insert( EdgePtr( new Edge( 2, 4, 2.0 ) ) );

graph->insert( EdgePtr( new Edge( 2, 5, 2.5 ) ) );

graph->insert( EdgePtr( new Edge( 3, 4, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 3, 7, 1.5 ) ) );

graph->insert( EdgePtr( new Edge( 4, 5, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 5, 4, 0.5 ) ) );

graph->insert( EdgePtr( new Edge( 5, 6, 0.5 ) ) );

graph->insert( EdgePtr( new Edge( 5, 7, 1.5 ) ) );

graph->insert( EdgePtr( new Edge( 7, 6, 1.0 ) ) );

To find all the shortest paths emanating from node 2 is a straightforward matter of creating the SPT template class instance.

This computes the complete shortest path tree in the constructor. The following code snippet shows how to generate the shortest paths and display the shortest path possible between nodes 2 to 7, which in this case would be 2->1->5->7:

// Find shortest path between nodes 2->7

int source = 2;

int target = 7;

std::stack<int> path;

SPT<Graph<Edge>, Edge> sp( *graph, source );

while ( true )

{

EdgePtr e = sp.pathR( target );

path.push( target );

if ( target == source )

break;

target = e->v;

}

// Print the path nodes

while ( !path.empty() )

{

std::cout << path.top() << " ";

path.pop();

}

This gives the shortest possible path between nodes 2 and 7 as [2,1,5,7]:

4.3 Testing for Graph Connectivity

A frequent requirement for graphs is as an efficient means of determining whether it is connected - or not.

Is it possible a selected pair of nodes to communicate with each other? Or is the graph disconnected in some way?

Using the same Graph class discussed in the previous sections, this program uses a depth-first search algorithm to test whether all the graph nodes get visited during the recursive search. Here are some examples:

1. A disconnected un-directed graph, whereby nodes [3,4] are disconnected from nodes [0,1,2], thereby making it impossible for node [0] to communicate with node [3]:

2. A disconnected directed graph. Node [1] can communicate with nodes [0,2,3] but not node [4], since a directed link exists between node [4] to node [0], but not node [0] to node [4]:

3. A connected un-directed graph. All nodes can communicate with each other:

4. A connected directed graph. All nodes can communicate with any other node. Though there is no link between nodes [0,3], a path between the two nodes exists via nodes [0,1,2,3].

Now let's add to our Graph class the following utility functions used to test if the graph is strongly connected:

// A recursive function to print DFS starting from v

void Graph::DFSUtil(int v, bool visited[])

{

// Mark the current node as visited and print it

visited[v] = true;

typename Graph::adjIterator A(*this, v);

for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() ) {

int w = e->w == v ? e->v : e->w;

if ( !visited[ w ] ) DFSUtil( w, visited );

}

}

// Function that returns reverse (or transpose) of this graph

Graph* Graph::getTranspose()

{

Graph<Edge>* g = new Graph<Edge>(Vcnt, digraph);

for (int v = 0; v < Vcnt; v++)

{

typename Graph::adjIterator A(*this, v);

for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() ) {

int w = e->w;

g->insert( EdgePtr( new Edge( w, v ) ) );

}

}

return g;

}

// The main function that returns true if graph is strongly connected

bool Graph::isSC()

{

// Step 1: Mark all the vertices as not visited (For first DFS)

for (int i = 0; i < Vcnt; i++) visited[i] = false;

// Step 2: Do DFS traversal starting from first vertex.

DFSUtil(0, visited);

// If DFS traversal doesn’t visit all vertices, then return false.

for (int i = 0; i < Vcnt; i++)

if (visited[i] == false) return false;

// Step 3: Create a reversed graph

Graph* gr = getTranspose();

// Step 4: Mark all the vertices as not visited (For second DFS)

for(int i = 0; i < Vcnt; i++) visited[i] = false;

// Step 5: Do DFS for reversed graph starting from first vertex.

// Staring Vertex must be same starting point of first DFS

gr->DFSUtil(0, visited);

// If all vertices are not visited in second DFS, return false

for (int i = 0; i < Vcnt; i++)

if (visited[i] == false) return false;

return true;

}

The following code listing shows how to implement each of the four examples listed above:

#include "Graph.h"

#include <iostream>

int main()

{

// Example 1: disconnected un-directed graph:

//

// 0 3

// / \ /

// 1 2 4

// nodes [3,4] disconnected from nodes [0,1,2]

Graph<Edge> g1( 5, false );

g1.insert( EdgePtr( new Edge(0, 1) ) );

g1.insert( EdgePtr( new Edge(0, 2) ) );

g1.insert( EdgePtr( new Edge(3, 4) ) );

g1.isSC() ? std::cout << "Yes\n" : std::cout << "No\n";

// Example 2: disconnected (directed) graph:

//

// 3 <- 2 <- 1 -> 0 <- 4

// eg 1 can communicate with [2,3,0] but not 4

Graph<Edge> g2( 5, true );

g2.insert( EdgePtr( new Edge(1, 0) ) );

g2.insert( EdgePtr( new Edge(4, 0) ) );

g2.insert( EdgePtr( new Edge(1, 2) ) );

g2.insert( EdgePtr( new Edge(2, 3) ) );

g2.isSC() ? std::cout << "Yes\n" : std::cout << "No\n";

// Example 3: connected (un-directed) graph:

//

// 3 <-> 2 <-> 1 <-> 0 <-> 4

// All nodes can communicate with any other node

Graph<Edge> g3( 5, false );

g3.insert( EdgePtr( new Edge(1, 0) ) );

g3.insert( EdgePtr( new Edge(4, 0) ) );

g3.insert( EdgePtr( new Edge(1, 2) ) );

g3.insert( EdgePtr( new Edge(2, 3) ) );

g3.isSC() ? std::cout << "Yes\n" :

std::cout << "No\n";

// Example 4: connected directed graph

//

// 0 -> 1 -> 2 -> 3 -> 0

//

// 4 -> 2 -> 4

// All nodes can communicate with any other node

Graph<Edge> g4( 5, true );

g4.insert( EdgePtr( new Edge(0, 1) ) );

g4.insert( EdgePtr( new Edge(1, 2) ) );

g4.insert( EdgePtr( new Edge(2, 3) ) );

g4.insert( EdgePtr( new Edge(3, 0) ) );

g4.insert( EdgePtr( new Edge(2, 4) ) );

g4.insert( EdgePtr( new Edge(4, 2) ) );

g4.isSC() ? std::cout << "Yes\n" :

std::cout << "No\n";

return 0;

}

This gives the following output to determine the connected status of each graph:

4.4 Kruskal’s Algorithm

Now let's look at a simple C++ implementation of Kruskal’s algorithm which is used for finding minimal spanning trees in networks. This algorithm employs the same Graph structure to model a network, insert and delete edges, and so forth.

Consider the following 11-node example network showing the network nodes and the weight values of the links connecting them:

This is built using multiple calls to insert as seen here:

graph.insert( EdgePtr( new Edge( 0, 1, 1.0 ) ) );

Kruskal’s algorithm works by obtaining a sorted list of the network links and then adding each least-cost link to another set while disallowing cycles. The complete code is as follows:

Graph.h

#include <vector>

#include <algorithm>

#include <memory>

// This code is from "Algorithms in C++, Third Edition,"

// by Robert Sedgewick, Addison-Wesley, 2002.

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;

struct EdgeSort

{

bool operator() ( const EdgePtr& ep1, const EdgePtr& ep2 )

{

return ep1->wt < ep2->wt;

}

};

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]; }

// Get the weighted edges

void edges( std::vector<EdgePtr>& edges )

{

for( int u = 0; u < V(); ++u )

{

DenseGRAPH<Edge>::adjIterator A(*this, u);

for ( EdgePtr e = A.beg(); !A.end(); e = A.nxt() )

{

if ( NULL != e )

{

edges.push_back( e );

}

}

}

}

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(); }

};

Main.cpp

#include "Graph.h"

#include <iostream>

// A structure to represent a subset for union-find

struct subset

{

int parent;

int rank;

};

typedef subset Subset;

// A utility function to find set of an element i

// (uses path compression technique)

int Find( Subset subsets[], int i )

{

// find root and make root as parent of i (path compression)

if (subsets[i].parent != i)

subsets[i].parent = Find(subsets, subsets[i].parent);

return subsets[i].parent;

}

// A function that does union of two sets of x and y by rank

void Union( Subset subsets[], int x, int y )

{

int xroot = Find( subsets, x );

int yroot = Find( subsets, y );

// Attach smaller rank tree under root of high rank tree

// (Union by Rank)

if ( subsets[xroot].rank < subsets[yroot].rank )

{

subsets[xroot].parent = yroot;

}

else if (subsets[xroot].rank > subsets[yroot].rank)

{

subsets[yroot].parent = xroot;

}

else

{

// If ranks are same, then make one as root and increment

// its rank by one

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

}

// The main function to construct MST using Kruskal's algorithm

void KruskalMST( DenseGRAPH<Edge>* graph, std::vector<EdgePtr>& mst )

{

const int V = graph->V();

// Sort edges in non-decreasing order of their weight

std::vector<EdgePtr> edges;

graph->edges( edges );

std::sort(edges.begin(), edges.end(), EdgeSort() );

// Allocate memory for creating V ssubsets

std::unique_ptr<subset[]> subsets( new subset[ V ]() );

// Create V subsets with single elements

for ( int v = 0; v < V; ++v )

{

subsets[v].parent = v;

subsets[v].rank = 0;

}

for ( std::vector<EdgePtr>::iterator it = edges.begin();

it != edges.end(); ++it )

{

EdgePtr edgePtr = *it;

int x = Find( subsets.get(), edgePtr->v );

int y = Find( subsets.get(), edgePtr->w );

// If including this edge does't cause cycle, include it

// in result and increment the index of result for next edge

if ( x != y )

{

mst.push_back( edgePtr );

Union( subsets.get(), x, y );

}

}

}

int main()

{

DenseGRAPH<Edge>* graph = new DenseGRAPH<Edge>( 11, true );

graph->insert( EdgePtr( new Edge( 0, 1, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 0, 2, 0.6) ) );

graph->insert( EdgePtr( new Edge( 0, 3, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 0, 4, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 0, 5, 1.1 ) ) );

graph->insert( EdgePtr( new Edge( 1, 4, 1.8 ) ) );

graph->insert( EdgePtr( new Edge( 1, 10, 1.9 ) ) );

graph->insert( EdgePtr( new Edge( 2, 3, 2.1 ) ) );

graph->insert( EdgePtr( new Edge( 2, 5, 2.3) ) );

graph->insert( EdgePtr( new Edge( 2, 6, 1.7 ) ) );

graph->insert( EdgePtr( new Edge( 3, 4, 1.7 ) ) );

graph->insert( EdgePtr( new Edge( 5, 6, 0.5 ) ) );

graph->insert( EdgePtr( new Edge( 5, 7, 0.7 ) ) );

graph->insert( EdgePtr( new Edge( 5, 8, 0.9 ) ) );

graph->insert( EdgePtr( new Edge( 5, 9, 0.9 ) ) );

graph->insert( EdgePtr( new Edge( 5, 10, 1.0 ) ) );

graph->insert( EdgePtr( new Edge( 6, 7, 1.9 ) ) );

graph->insert( EdgePtr( new Edge( 7, 8, 1.7 ) ) );

graph->insert( EdgePtr( new Edge( 8, 9, 1.6 ) ) );

graph->insert( EdgePtr( new Edge( 9, 10, 2.2 ) ) );

std::vector<EdgePtr> mst;

KruskalMST( graph, mst );

for ( std::vector<EdgePtr>::const_iterator it = mst.begin();

it != mst.end(); ++it )

{

std::cout << it->get()->v << " "

<< it->get()->w << " "

<< it->get()->wt << std::endl;

}

return 0;

}

This gives the following output:



Which in turn represents this minimal spanning tree:



Chapter Summary

To summarize this master lesson, you can now:

·Utilize a Graph class to model networks as a set of nodes and interconnecting edges

·Use Graph class methods to insert, remove and keep track of the edges and nodes in your network.

·Apply useful problem-solving algorithms for determining shortest paths, connectivity and minimal spanning trees.