[Graph] Difference between DF search and visit / Graph Printing
Hi there! I am struggling a little understanding the difference between the DF search and visit. I thought that the DF visit would revisit "back" nodes while the DF search would not. But as I just found out that does seem to be the difference. What I want: I would like to print all following nodes for every node of a acylic graph. Lets say I have this very simple graph, I hope spaces are preserved: -> Long \ Begin / -> End \ -> -> Short / I would like to print that graph in the following Fashion: Begin .Long ..End .Short ..End I don't mind the exact order of "Long" and "Short", as long as they are both printed. So far I did this by implementing the following dfs_visitor<> [0]. I then apply the visitor with a call to boost::depth_first_visit() and my graph. However, the problem is, that the "End" node is only visited, and therefore printed, once. Of course I could roll out the DF visit myself, but as I will be demonstrating this at my unversity, I would prefer a clean solution. So what am I probably missing to print the graph in the fasion I want it? [0] http://pastebin.com/u43TtU7F
I am struggling a little understanding the difference between the DF search and visit. I thought that the DF visit would revisit "back" nodes while the DF search would not. But as I just found out that does seem to be the difference.
Depth-first visit will only visit vertices that reachable for the start vertex. Depth-first search will visit all vertices in the graph.
I then apply the visitor with a call to boost::depth_first_visit() and my graph. However, the problem is, that the "End" node is only visited, and therefore printed, once.
DFS is guaranteed to visit each node exactly once.
So what am I probably missing to print the graph in the fasion I want it?
Are you trying to print all paths from the root of the tree to leaves? That's a little bit harder problem, I think. Andrew
I am struggling a little understanding the difference between the DF search and visit. I thought that the DF visit would revisit "back" nodes while the DF search would not. But as I just found out that does seem to be the difference.
Depth-first visit will only visit vertices that reachable for the start vertex. Depth-first search will visit all vertices in the graph. Ah, thanks!
So what am I probably missing to print the graph in the fasion I want it?
Are you trying to print all paths from the root of the tree to leaves? That's a little bit harder problem, I think. Its actually quite easy to solve recursively. I have just done it for LEDA and I guess porting the code to boost is a snap. Basicly I just couldn't believe that I have to roll out my own solution.
As a reference here is what I mocked up for LEDA: void LedaPrecedenceDiagram::recursivePrint(VertexDescriptor entry, int depth) { // Apply depth for (int i = 0; i < depth; i++ ) { std::cout << "."; } // Print name and depth std::cout << mGraph[entry]->getName() << " (" << mGraph[entry]->getDuration() << ")" << std::endl; // Retrieve all out edges for the current entry leda::listleda::edge outEdges = mGraph.out_edges(entry); EdgeDescriptor edge; forall(edge, outEdges) { recursivePrint(mGraph.target(edge), depth + 1); } } void LedaPrecedenceDiagram::printFollowingEntriesImplementation(const std::string& name) { //! @todo Does LEDA provide a built in solution recursivePrint(getVertexByName(name), 0); }
On 03/26/11 09:54, Marcus Riemer wrote: [snip]
Are you trying to print all paths from the root of the tree to leaves? That's a little bit harder problem, I think. Its actually quite easy to solve recursively. I have just done it for LEDA and I guess porting the code to boost is a snap. Basicly I just couldn't believe that I have to roll out my own solution.
As a reference here is what I mocked up for LEDA: void LedaPrecedenceDiagram::recursivePrint(VertexDescriptor entry, int depth) { // Apply depth for (int i = 0; i < depth; i++ ) { std::cout << "."; }
// Print name and depth std::cout << mGraph[entry]->getName() << " (" << mGraph[entry]->getDuration() << ")" << std::endl;
Marcus, You might find: http://svn.boost.org/svn/boost/sandbox/variadic_templates/boost/iostreams/ut... as a replacement for '// Apply depth'. The depth is stored in a derived streambuf and incremented and decremented with the indent_buf_in and indent_buf_out iomanipulators; hence, you don't have to pass the depth as an argument. A demo is here: http://svn.boost.org/svn/boost/sandbox/variadic_templates/libs/iostreams/tes... and docs are here: http://svn.boost.org/svn/boost/sandbox/variadic_templates/libs/iostreams/doc... HTH. -Larry
Its actually quite easy to solve recursively. I have just done it for LEDA and I guess porting the code to boost is a snap. Basicly I just couldn't believe that I have to roll out my own solution.
I see. You're right. Like I said, the BGL's DFS guarantees that each vertex is visited exactly once, regardless of the structure of the graph (acyclic or not). Its not terribly surprising that you'd have to write your own solution. I don't think that this application was ever considered a use case for the BGL's DFS suite. The algorithm is simple enough to write. It might be worth noting pointing out that the mockup you showed won't for graphs with cycles. Applying this to a graph with a single vertex and loop edge will result in infinite recursion. Andrew
participants (3)
-
Andrew Sutton -
Larry Evans -
Marcus Riemer