On Wed, 26 Jun 2013, lizy10b wrote:
>
> 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?
It looks like it's similar to the directed DFS, so it would likely return
the same results.
> 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.
It doesn't look like there is one, but you can use breadth-first search to
find cycles as well. Would that work for you?
-- Jeremiah Willcock
>
> ____________________________________________________________________________________________________________________
> lizy10b
>
> ____________________________________________________________________________________________________________________
> 发件人： Jeremiah Willcock
> 发送时间： 2013-06-26 03:34:37
> 收件人： lizy10b
> 抄送： boost-users
> 主题： Re: Re: Re: [Boost-users] Confused with Depth-First-Searchmethod,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/q
> uick_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
> > 发送时间： 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 g
> raph ?
> > 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
> >
> >
>
>