Finding all possible routes in a Graph Data Structure using Depth First Search in C++

Question

Suppose, you have a Graph, G, and what you need to do is find all possible routes from start_node to finish_node. Also, you need to print all routes in correct order. How would you do this? Discovering the nodes is not tough, its printing them in correct order and getting the distances.

template <class VertexType>
void DepthFirstSearch(Graph<VertexType> routes, VertexType from_vertex, VertexType to_vertex) 
{
    stack<VertexType> mystack;
    queue<VertexType> vertexQ;
    int total_weight = 0;
    int found_count = 0;

    /*stringstream ss;*/

    bool found = false;
    VertexType vertex;
    VertexType item;

    routes.clearMarks();

    // size_t i = 0;
    // size_t j = 0;

    mystack.push(from_vertex); // Adding Location to stack

    do 
    {   
        vertex = mystack.top(); // Get top location
        mystack.pop(); // Getting rid of top location
        if (vertex == to_vertex) // If location == destination, then stop;
        {
            found = true;
            found_count++;
        } else {
            if (!routes.isMarked(vertex)) // If route has not been traveled to
            {
                routes.markVertex(vertex); // Mark place
                routes.goToVertices(vertex, vertexQ); // Add adjacent positions
                while (!vertexQ.empty()) // While there are still positions left to test
                {

                    item = vertexQ.front(); // Get top position
                    vertexQ.pop(); // Get rid of top position from stack
                    if (!routes.isMarked(item)) // If top position is not marked,
                        mystack.push(item); // Add to-visit stack
                }
            }
        }
    } while (!mystack.empty());

    if(!found) 
    {
        std::cout << "Distance: infinity" << std::endl;
        std::cout << "Rout:" << std::endl;
        std::cout << "None" << std::endl;
    } else {
        std::cout << "Found this many times: " << found_count << std::endl;
    }
}

Ideally, if someone enters A B, then an example of the output will be:

distance: 100
A to C, 50
C to D, 40
D to B, 10


distance: 10
A to B, 10

Note that both C and D have other nodes they can go to, but their distances will not be taken into consideration even though the Depth-First Algorithm will explore them. This is a one-directional graph, with input coming from a text file.

Answer 1

You need to keep track of which vertices you've been through, and use that list as a path.

Then you have two options:

• either print out the vertices list when you found a path, and then backtrack to the next possible branch,
• or copy the path to another container, backtrack, and print out the whole liist of paths at the end

Both methods are correct, depending on what kind of processing you wish to do on the paths.

To be able to correctly backtrack, you need to know which adjacent vertices remain to be visited for each vertex on the current path. Your current algorithm forget that information by pushing all the vertices in mystack. I suggest using iterators instead of vertices in mystack, and have your graph object return such iterators from the goToVertices method.

Since I don't know if you have that class available for your graph, I'll use stack of queue instead to group vertices by level in mystack. Each queue represents a level of the tree covering the dfs.

deque<queue<VertexType> > mystack;
queue<VertexType> vertexQ;
int total_weight = 0;
int found_count = 0;

VertexType vertex;

routes.clearMarks();

// size_t i = 0;
// size_t j = 0;

vertexQ.push(from_vertex);
mystack.push_front(vertexQ); // Adding Location to stack

do 
{   
    vertexQ = mystack.front(); // Get top location
    if (vertexQ.empty()) {
        mystack.pop_front();
        mystack.front().pop();
        continue;
    }
    if (vertexQ.front() == to_vertex) // If location == destination, then stop;
    {
        // save path: loop on all the queues from mystack and print front.    
        for (stack<queue<VertexType>>::const_reverse_iterator it = mystack.rbegin();
               it != mystack.rend();  ++it){
            // save or process path vertices
            cout << it->front() << endl;
        }               
        // backtrack
        mystack.pop_front();
        mystack.front().pop();
    } else {
        if (!routes.isMarked(vertexQ.front())) // If route has not been traveled to
        {
            routes.markVertex(vertexQ.front()); // Mark place
            mystack.push_front(
                routes.goToVertices(vertexQ.front())); // Get adjacent vertices
        }
    }
} while (!mystack.empty());