
Boost Users : 
Subject: Re: [Boostusers] Confused with DepthFirstSearchmethod,forwardor cross edge found on a undirected graph ?
From: lizy10b (lizy10b_at_[hidden])
Date: 20130626 04:45:07
Hi Jeremiah Willcock,
Thanks for your reply.
As maybe there are some problems when invoke depth_first_visit() on an undirected graph, the undirected_dfs() could be a very good substitution.
So I continue to test the parallel version of the DFS function  tsin_depth_first_visit(), and the test file comes from \boost_1_53_0\libs\graph_parallel\test\distributed_dfs_test.cpp.
The test file invokes the tsin_depth_first_visit() on a distributed undirected graph, and the visitor print all events, the "forward_or_cross_edge" appears four times. So maybe there are some problems in tsin_depth_first_visit() too.
Does the parallel tsin_depth_first_visit() base on the serial depth_first_visit(), so they appear similiar problem when work with undirected graph?
My final target is to find a parallel version DFS works with undirected graph, in order to find all cycles parallelly. Could you please give me some advices on that? I am stucked.
Thank you very much.
Zhiyu Li
20130626
lizy10b
å‘ä»¶äººï¼š Jeremiah Willcock
å‘é€æ—¶é—´ï¼š 20130626 03:34:37
æ”¶ä»¶äººï¼š lizy10b
æŠ„é€ï¼š boostusers
ä¸»é¢˜ï¼š Re: Re: Re: [Boostusers] Confused with DepthFirstSearchmethod,forwardor cross edge found on a undirected graph ?
On Tue, 25 Jun 2013, lizy10b wrote:
> 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() .
If that parameter isn't in the documentation for undirected_dfs, the
argument will just be ignored.
> 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?
I believe you would want to hook tree_edge() instead of edge_relaxed().
 Jeremiah Willcock
>
> _________________________________________________________________________________________________________________________________________________________
> å‘ä»¶äººï¼š 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ç‡¾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 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