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