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

suppose, have graph, g, , need find all possible routes start_node finish_node. also, need print routes in correct order. how this? discovering nodes not tough, printing them in correct order , getting 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 = 0;     // size_t j = 0;      mystack.push(from_vertex); // adding location stack           {            vertex = mystack.top(); // top location         mystack.pop(); // getting rid of top location         if (vertex == to_vertex) // if location == destination, stop;         {             found = true;             found_count++;         } else {             if (!routes.ismarked(vertex)) // if route has not been traveled             {                 routes.markvertex(vertex); // mark place                 routes.gotovertices(vertex, vertexq); // add adjacent positions                 while (!vertexq.empty()) // while there still positions left test                 {                      item = vertexq.front(); // top position                     vertexq.pop(); // rid of top position stack                     if (!routes.ismarked(item)) // if top position 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 many times: " << found_count << std::endl;     } } 

ideally, if enters a b, example of output be:

distance: 100 c, 50 c d, 40 d b, 10   distance: 10 b, 10 

note both c , d have other nodes can go to, distances not taken consideration though depth-first algorithm explore them. one-directional graph, input coming text file.

you need keep track of vertices you've been through, , use list path.

then have 2 options:

• either print out vertices list when found path, , backtrack next possible branch,
• or copy path container, backtrack, , print out whole liist of paths @ end

both methods correct, depending on kind of processing wish on paths.

to able correctly backtrack, need know adjacent vertices remain visited each vertex on current path. current algorithm forget information pushing vertices in mystack. suggest using iterators instead of vertices in mystack, , have graph object return such iterators gotovertices method.

since don't know if have class available graph, i'll use stack of queue instead group vertices level in mystack. each queue represents level of tree covering dfs.

deque<queue<vertextype> > mystack; queue<vertextype> vertexq; int total_weight = 0; int found_count = 0;  vertextype vertex;  routes.clearmarks();  // size_t = 0; // size_t j = 0;  vertexq.push(from_vertex); mystack.push_front(vertexq); // adding location stack   {        vertexq = mystack.front(); // top location     if (vertexq.empty()) {         mystack.pop_front();         mystack.front().pop();         continue;     }     if (vertexq.front() == to_vertex) // if location == destination, stop;     {         // save path: loop on queues mystack , print front.             (stack<queue<vertextype>>::const_reverse_iterator = mystack.rbegin();                != 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         {             routes.markvertex(vertexq.front()); // mark place             mystack.push_front(                 routes.gotovertices(vertexq.front())); // adjacent vertices         }     } } while (!mystack.empty());