[Graph] Difference between DF search and visit / Graph Printing

[Marcus Riemer]

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

[Andrew Sutton]

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

[Marcus Riemer]

Post by Andrew Sutton

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!

Post by Andrew Sutton

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::list<leda::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);
}

[Larry Evans]

On 03/26/11 09:54, Marcus Riemer wrote:
[snip]

Post by Marcus Riemer

Post by Andrew Sutton
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.
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/utility/indent_scoped_ostreambuf.hpp

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/test/indent_scoped_ostreambuf_test.cpp

and docs are here:


http://svn.boost.org/svn/boost/sandbox/variadic_templates/libs/iostreams/doc/functions/

HTH.

-Larry

[Andrew Sutton]

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