Check for path in a directed graph
Check for existence of a path from "start" node to "end" node in a directed graph.
/*
* CheckPathExistsFromStartToEnd.cpp
*
* Created on: May 07, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class GraphNode {
public :
enum State {NotVisited, Visited};
GraphNode(int d): data(d) {}
~GraphNode() {
vector<GraphNode *>::iterator it;
for (it = adjacentNodes.begin(); it < adjacentNodes.end(); it++) {
delete (*it);
}
}
void addNode(GraphNode *node) {
adjacentNodes.push_back(node);
}
vector<GraphNode *> adjacentNodes;
State state;
int data;
};
/**
* Collection of interconnected nodes
*/
class Graph {
public:
void addNode(GraphNode *node) {
nodes.push_back(node);
}
vector<GraphNode *> nodes;
};
/**
* Print each node and its adjacent nodes (directed)
*/
void printGraph(Graph *graph) {
if (graph == NULL){
return;
}
vector<GraphNode *>::iterator it1;
for (it1 = graph->nodes.begin(); it1 < graph->nodes.end(); it1++) {
cout << "Node: " << (*it1)->data << " --> adjacent: ";
vector<GraphNode *>::iterator it2;
for (it2 = (*it1)->adjacentNodes.begin();
it2 < (*it1)->adjacentNodes.end(); it2++) {
cout << (*it2)->data << " " ;
}
cout << endl;
}
}
/**
* Create a directed graph
*/
Graph *createGraph() {
GraphNode *n0 = new GraphNode(0);
GraphNode *n1 = new GraphNode(1);
GraphNode *n2 = new GraphNode(2);
GraphNode *n3 = new GraphNode(3);
GraphNode *n4 = new GraphNode(4);
GraphNode *n5 = new GraphNode(5);
GraphNode *n6 = new GraphNode(6);
GraphNode *n7 = new GraphNode(7);
GraphNode *n8 = new GraphNode(8);
n0->addNode(n1);
n0->addNode(n2);
n0->addNode(n3);
n1->addNode(n2);
n1->addNode(n4);
n3->addNode(n2);
n3->addNode(n6);
n4->addNode(n5);
n5->addNode(n7);
n5->addNode(n8);
n6->addNode(n5);
n6->addNode(n7);
Graph *graph = new Graph();
graph->addNode(n0);
graph->addNode(n1);
graph->addNode(n2);
graph->addNode(n3);
graph->addNode(n4);
graph->addNode(n5);
graph->addNode(n6);
graph->addNode(n7);
graph->addNode(n8);
return graph;
}
/**
* Essentially a Breadth First Search (BFS) algorithm
*/
bool doesPathExist(Graph *graph, GraphNode *start, GraphNode *end) {
if (graph == NULL)
return false;
vector<GraphNode *>::iterator it;
// To begin with mark all nodes as "Not Visited"
for (it = graph->nodes.begin(); it < graph->nodes.end(); it++) {
(*it)->state = GraphNode::NotVisited;
}
queue<GraphNode *> nodesQueue;
// First enqueue the start node
nodesQueue.push(start);
/* Dequeue the node from the queue and examine it
* if queue is empty, every node in the graph has been examined and the
* desired node was not found */
while(! nodesQueue.empty()) {
GraphNode *node = nodesQueue.front();
nodesQueue.pop();
if (node != NULL) {
//if node is found return true
if (node == end)
return true;
vector<GraphNode *>::iterator it1;
for (it1 = node->adjacentNodes.begin(); it1 < node->adjacentNodes.end(); it1++) {
//enqueue adjacent nodes that have not been visited yet
if ((*it1)->state == GraphNode::NotVisited) {
nodesQueue.push(*it1);
}
}
//Mark current node as visited
node->state = GraphNode::Visited;
}
}
return false;
}
/**
* Test the code
*/
int main() {
Graph *graph = createGraph();
printGraph(graph);
GraphNode *start = graph->nodes[2];
GraphNode *end = graph->nodes[3];
cout << endl;
cout << "Path: from node " << start->data << " to " << end->data <<
" exists: "<< (doesPathExist(graph, start, end) ? "Yes" : "No") << endl;
start = graph->nodes[3];
end = graph->nodes[8];
cout << "Path: from node " << start->data << " to " << end->data <<
" exists: "<< (doesPathExist(graph, start, end) ? "Yes" : "No") << endl;
}