|
Boost Users : |
Subject: Re: [Boost-users] Confused with Depth-First-Searchmethod, forwardorcross edge found on a undirected graph ?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-06-27 10:46:22
On Thu, 27 Jun 2013, lizy10b wrote:
> Hi Jeremiah Willcock,
> Thanks for your reply.
> Sad to say the pararallel version BFS example file (\boost_1_53_0_\libs\graph_parallel\example\breadth_first_search.cpp)Â can not be compiled with VS2010
> on my end. It complains an unresolved external symbol "void _cdecl boost::bfs_helper....". And I found a similar report on
> http://boost.2283326.n4.nabble.com/LINK-Error-while-building-PBGL-example-breadth-first-search-cpp-td3799909.html.%c2%a0but with no result.
Is it boost::bfs_helper or boost::detail::bfs_helper? Are there any
symbols in the object file for breadth_first_search that are defined and
demangle to names involving bfs_helper?
> I also tried to build the boost with MinGW, but it seems the Boost.MPI cannot be compiled correctly upon MPICH2, so the parallel BGL library will not
> be built either.Â
What is the issue with that version?
-- Jeremiah Willcock
> Â
> 2013-06-27
>
> _________________________________________________________________________________________________________________________________________________________
> lizy10b
>
> _________________________________________________________________________________________________________________________________________________________
> åä»¶äººï¼ Jeremiah Willcock
> åéæ¶é´ï¼ 2013-06-26 22:54:58
> æ¶ä»¶äººï¼ lizy10b
> æéï¼ boost-users
> 主é¢ï¼ Re: Re: Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ?
> 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
> >Â >Â
> >Â >
> >Â
> >
>
>
Boost-users 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