
Boost Users : 
Subject: Re: [Boostusers] Confused with DepthFirstSearch method, forwardor cross edge found on a undirected graph ?
From: lizy10b (lizy10b_at_[hidden])
Date: 20130625 06:29:16
Hi Jeremiah Willcock,
Can I use the predecessor_map in undirected_dfs() like in dijkstra_shortest_paths()?
undirected_dfs(g, predecessor_map(&p[0]).root_vertex(vertex_descriptor(0)).visitor(vis)
.edge_color_map(get(edge_color, g)).vertex_color_map(get(vertex_color, g)));
It does not work on my end, all elements in predecessor remain 0 after invoke the undirected_dfs() .
In the last section (Extending Algorithms with Visitors) of http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/quick_tour.html,
an example shows how to write a predecessor_map using visitor,
and the "event point" is edge_relaxed().
But as the undirected_dfs document shows there is no edge_relaxed() for DFS.
So is there any way to save predecessors in DFS?
For example an edge (u,v) and start at vertex u
When the discover_vertex(Vertex, Graph&) is invoked at vertex v, then inside the discover_vertex() how could I know the previous discovered vertex is u?
Thanks
Zhiyu Li
20130625
lizy10b
·¢¼þÈË£º Jeremiah Willcock
·¢ËÍÊ±¼ä£º 20130625 00:44:05
ÊÕ¼þÈË£º lizy10b
³ËÍ£º boostusers
Ö÷Ìâ£º Re: Re: [Boostusers] Confused with DepthFirstSearch 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 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
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 directedgraph 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 filteringout of multiple directions
for the same edge.
 Jeremiah Willcock
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net