Hi Jeremiah Willcock,
Thanks for your reply.
Another question is the vertex color property also required in undirected_dfs()? or only edge color property is enough?
Thanks.
 
Zhiyu Li
 
 
2013-06-25
lizy10b
发件人： Jeremiah Willcock
发送时间： 2013-06-25  00:44:05
收件人： lizy10b
抄送： boost-users
主题： Re: Re: [Boost-users] Confused with Depth-First-Search method,forwardor cross edge found on a undirected graph ?
On Tue, 25 Jun 2013, lizy10b wrote:
> Hi Jeremiah Willcock ,
> ?
> It seems undirected_dfs() works. I have not燾heck 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,爂))?is required when calling the undirected_dfs() .
> Thanks
It looks like what is going wrong with using directed DFS is that edges 
are examined twice (once in each direction), and so you can have forward 
edges even in a symmetric graph (which is how undirected graphs are 
treated in directed-graph algorithms in BGL).  An example is the triangle 
0 -- 1 -- 2 -- 0: starting at 0 and processing the edges out of a vertex 
in numerical order, 0 -> 1 is a tree edge, 1 -> 0 is a back edge, 1 -> 2 
is a tree edge, 2 -> 0 is a back edge, 2 -> 1 is a back edge, then 0 -> 2 
is a forward edge.  An undirected DFS would mark 2 -> 0 as a back edge 
then ignore 0 -> 2 since it is the same as 2 -> 0.  The edge colors in 
undirected_dfs are used to do this filtering-out of multiple directions 
for the same edge.
-- Jeremiah Willcock