Re: [Boost-users] Confused with Depth-First-Search method, forward or cross edge found on a undirected graph ?

Subject: Re: [Boost-users] Confused with Depth-First-Search method, forward or cross edge found on a undirected graph ?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-06-24 11:47:16

On Mon, 24 Jun 2013, lizy10b wrote:

> Hi there
> I have a problem with the DFS method (Boost 1.53). 
> I found when invoking the DFS method on a undirected graph, the "forward_or_cross_edge" was called more than one ti
> mes. 
> But as the document says "In an undirected graph this method is never called".
> http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/DFSVisitor.html
>  
> I performed the test based on the file_dependencies.cpp example
>  (examples/file_dependencies.cpp; http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/file_dependency_example.html)
> 1)
> Change the graph type from "bidirectionalS" to "undirected".
> 2)Implement all the 8 DFS vistor "event methods" (Initialize Vertex, Start Vertex, Discover Vertex, Examine Edge, T
> ree Edge, Back Edge, Forward or Cross Edge, Finish Vertex)
> in the cycle_detector struct to print the vertex names, edge sources and targets.
> 3)comment out some code at the begining of the example
> cpp files as the topological_sort method raise exception upon the undirected graph.

Does undirected_dfs() do the same thing?  I don't think the directed 
version should call forward_or_cross_edge when given an undirected graph, 
though.  Would it be possible for you to print out the vertex->color 
mapping when forward_or_cross_edge is called?  Also, it would be nice if 
you'd send your complete test program.  Thanks.

-- Jeremiah Willcock