Boost logo

Boost Users :

Date view Thread view Subject view Author view

Subject: Re: [Boost-users] Confused with Depth-First-Searchmethod, forwardorcross edge found on a undirected graph ?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-07-02 09:51:22

On Sun, 30 Jun 2013, lizy10b wrote:

> Hi Jeremiah Willcock,
>  
> Thanks for your suggestion.
> I got the boost.mpi built with MinGW by adding one line to user-config.jam:
> using gcc : : : <compileflags>-DMPICH_SKIP_MPICXX ;
> Only the boost.mpi python binding built failed.
> But not all the boost.mpi examples and testing file could be built.
>  
> And using the same configuration I got the graph_parallel libraries built too.
> Unfortunately none of the examples or testing files could be built.
>  
> I will post the logs.
>  
> And I also have some problems when build the BGL Python (Problem in building the BGL Python 0.95 on Windows).
> Could you please give some advices on that?
> Thanks

I don't see an attachment (in this email or your next one). Was there
one?

-- Jeremiah Willcock

> ____________________________________________________________________________________________________________________
> lizy10b
>
> ____________________________________________________________________________________________________________________
> 发件人： Jeremiah Willcock
> 发送时间： 2013-06-29  07:35:53
> 收件人： boost-users
> 抄送：
> 主题： Re: [Boost-users] Confused with Depth-First-Searchmethod,forwardorcross edge found on a undirected graph ?
> On Sat, 29 Jun 2013, lizy10b wrote:
> > Hi Jeremiah Willcock ,
> > I have tested r84912 and r84913:
> >  
> > r84912 -- built failed (line 319)
> > Error 3 error C2668: 'boost::detail::bfs_helper' : ambiguous call to overloaded function
> > e:\boost\binary_include\include\boost-1_53\boost\graph\breadth_first_search.hpp 319 1 boost_test_1
> >  
> > r84913 -- built success
> So that is taken care of, then?  I knew you would need both patches; sorry 
> for the extra work of checking with only r84912.
> >  
> > And for the building boost.mpi with mingw, you sugguest me
> > "try adding MPICH_SKIP_MPICXX as a -D flag (to define it as a macro) when building 
> > Boost.MPI".
> > sorry, I dont fully understand, does it mean I should try to add some flag (MPICH_SKIP_MPICXX as a -D or somethin
> g) when execute the b2 command to build
> > boost.mpi?
> You need to somehow add -DMPICH_SKIP_MPICXX to your compiler flags; I 
> don't remember how to do that with Boost.Build, but you should be able to 
> look it up.
> -- Jeremiah Willcock
> > 
> > _________________________________________________________________________________________________________________
> __________________________________________
> > lizy10b
> > 
> > _________________________________________________________________________________________________________________
> __________________________________________
> > 发件人： Jeremiah Willcock
> > 发送时间： 2013-06-29  03:56:57
> > 收件人： 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
> > >  
> > > I download the two breadth_first_search.hpp files from the trunk (now is R84910) and overwrite my existing file
> s repectiviely.
> > > But unfortunately VS2010 complains about one error when try to build.
> > >  
> > >  
> > > Error 3 error C2668: 'boost::detail::bfs_helper' : ambiguous call to overloaded function
> > > e:\boost\binary_include\include\boost-1_53\boost\graph\breadth_first_search.hpp 319 1 boost_test_1
> > >  
> > >  
> > > Double click the error message will let the mouse point to Line 319
> > Could you please try the changes in r84912 and r84913?  They affect the 
> > files:
> > boost/graph/distributed/concepts.hpp
> > boost/graph/graph_traits.hpp
> > boost/graph/breadth_first_search.hpp
> > boost/graph/distributed/breadth_first_search.hpp
> > -- Jeremiah Willcock
> > > 
> > > _______________________________________________________________________________________________________________
> _________________________________________
> > ___
> > > 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 fun
> ction, A and B.
> > > >  A is in \graph\breadth_first_search.hpp for the serial version, with another definition for the parallel ver
> sion of this function (B) which is wrappe
> > d
> > > > 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 gra
> ph ?
> > > > 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_firs
> t_search.cpp) can not be compiled with VS
> > 20
> > > > 10
> > > > > on my end. It complains an unresolved external symbol "void _cdecl boost::bfs_helper....". And I found a si
> milar report on
> > > > > http://boost.2283326.n4.nabble.com/LINK-Error-while-building-PBGL-example-breadth-first-search-cpp-td379990
> 9.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 MP
> ICH2, so the parallel BGL library will no
> > t
> > > > > 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 undi
> rected 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_d
> fs()
> > > > > > 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 pri
> nt 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 similia
> r 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 cycle
> s
> > > > > > 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 u
> ndirected
> > > > > > 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/g
> raph/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 un
> directed 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 the
> re 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
> > > 
> > >
> > _______________________________________________
> > 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
>
>

Date view Thread view Subject view Author view

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