Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ?

Subject: Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ?
From: lizy10b (lizy10b_at_[hidden])
Date: 2013-06-28 02:22:01

Hi Jeremiah Willcock,

Attached is the build log of boost.mpi with mingw (zip format).
Successful output libraries are: 
libboost_python-mgw47-d-1_53.dll
libboost_python-mgw47-d-1_53.dll.a
libboost_serialization-mgw47-d-1_53.dll
libboost_serialization-mgw47-d-1_53.dll.a

No boost.mpi library output.

My environment is Win7 x64, Python 2.66 x86 (binary), MPICH2 1.32p1 x86 (binary),
gcc 4.7.1 from CodeBlocks with MinGW x86 (binary).

It lools like there is some codes in mpicxx.h which are incompatible to boost.mpi building process.

Thanks

Zhiyu Li

2013-06-28 



lizy10b 



发件人： Jeremiah Willcock 
发送时间： 2013-06-28  00:54:20 
收件人： boost-users 
抄送： 
主题： Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ? 
 
On Fri, 28 Jun 2013, lizy10b wrote:
>  Hi Jeremiah Willcock,
> Good news, the parallal version BFS example (\graph_parallel\example\breadth_first_search.cpp) could be built now.
> I followed your suggestion to locate the boost::detail::bfs_helper(), there are two declarartions of this function, A and B.
>  A is in \graph\breadth_first_search.hpp for the serial version, with another definition for the parallel version of this function (B) which is wrapped
> inside a macro (#ifdef BOOST_GRAPH_USE_MPI... #endif).
> And the delcaration of B is in \graph\distributed\breadth_first_search.hpp.
> I just comment out the delcaration of B and copy it to overwrite the definition inside the above macro.
> and append "* = 0" at the end of the last parameter just like function A.
> And then the example cpp built successfully.
Could you please see if r84909 in the trunk (just committed) works without 
needing any extra changes?  I added the "= 0" there but didn't do any of 
the other changes you mention.
> As for the build error of Boost.MPI with MinGW, I will redo it and save the ouput to a file.
Thanks.
-- Jeremiah Willcock
> 
> _________________________________________________________________________________________________________________________________________________________
> lizy10b
> 
> _________________________________________________________________________________________________________________________________________________________
> 发件人： Jeremiah Willcock
> 发送时间： 2013-06-27  22:47:02
> 收件人： boost-users
> 抄送：
> 主题： Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ?
> 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 VS20
> 10
> > 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. but 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 mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

> 
>
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users