Re: [Boost-users] [Graph] Difference between DF search and visit / Graph Printing

Subject: Re: [Boost-users] [Graph] Difference between DF search and visit / Graph Printing
From: Marcus Riemer (Marcus_at_[hidden])
Date: 2011-03-26 10:54:18

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