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

Subject: Re: [Boost-users] Confused with Depth-First-Search method, forwardor cross edge found on a undirected graph ?
From: lizy10b (lizy10b_at_[hidden])
Date: 2013-06-24 12:29:50

Hi Jeremiah Willcock ,

It seems undirected_dfs() works. I have not check the result according to the graph, but at least there is no forward edge or cross edge output.
Attached is the revised cpp file using undirected_dfs() .
My question is why edge_color_map(get(edge_color, g))  is required when calling the undirected_dfs() .
Thanks

Zhiyu Li


2013-06-25 



lizy10b 



·¢¼þÈË£º Jeremiah Willcock 
·¢ËÍʱ¼ä£º 2013-06-24  23:47:20 
ÊÕ¼þÈË£º boost-users 
³­ËÍ£º lizy10b 
Ö÷Ì⣺ Re: [Boost-users] Confused with Depth-First-Search method, forwardor cross edge found on a undirected graph ? 
 
On Mon, 24 Jun 2013, lizy10b wrote:
> Hi there
> I have a problem with the DFS method?Boost?.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? 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