Confused with Depth-First-Search method, forward or cross edge found on a undirected graph ?
Hi there I have a problem with the DFS method (Boost 1.53). I found when invoking the DFS method on a undirected graph, the "forward_or_cross_edge" was called more than one times. But as the document says "In an undirected graph this method is never called". http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/DFSVisitor.html I performed the test based on the file_dependencies.cpp example (examples/file_dependencies.cpp; http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/file_dependency_example....) 1) Change the graph type from "bidirectionalS" to "undirected". 2)Implement all the 8 DFS vistor "event methods" (Initialize Vertex, Start Vertex, Discover Vertex, Examine Edge, Tree Edge, Back Edge, Forward or Cross Edge, Finish Vertex) in the cycle_detector struct to print the vertex names, edge sources and targets. 3)comment out some code at the begining of the example cpp files as the topological_sort method raise exception upon the undirected graph. The results: the forward_or_cross_edge method was called five times. initialize_vertex: dax.h initialize_vertex: yow.h initialize_vertex: boz.h initialize_vertex: zow.h initialize_vertex: foo.cpp initialize_vertex: foo.o initialize_vertex: bar.cpp initialize_vertex: bar.o initialize_vertex: libfoobar.a initialize_vertex: zig.cpp initialize_vertex: zig.o initialize_vertex: zag.cpp initialize_vertex: zag.o initialize_vertex: libzigzag.a initialize_vertex: killerapp start_vertex: dax.h discover_vertex: dax.h examine_edge: dax.h --> foo.cpp tree_edge: dax.h --> foo.cpp discover_vertex: foo.cpp examine_edge: foo.cpp --> dax.h back_edge: foo.cpp --> dax.h examine_edge: foo.cpp --> zow.h tree_edge: foo.cpp --> zow.h discover_vertex: zow.h examine_edge: zow.h --> foo.cpp back_edge: zow.h --> foo.cpp finish_vertex: zow.h examine_edge: foo.cpp --> foo.o tree_edge: foo.cpp --> foo.o discover_vertex: foo.o examine_edge: foo.o --> foo.cpp back_edge: foo.o --> foo.cpp examine_edge: foo.o --> libfoobar.a tree_edge: foo.o --> libfoobar.a discover_vertex: libfoobar.a examine_edge: libfoobar.a --> foo.o back_edge: libfoobar.a --> foo.o examine_edge: libfoobar.a --> bar.o tree_edge: libfoobar.a --> bar.o discover_vertex: bar.o examine_edge: bar.o --> bar.cpp tree_edge: bar.o --> bar.cpp discover_vertex: bar.cpp examine_edge: bar.cpp --> dax.h back_edge: bar.cpp --> dax.h examine_edge: bar.cpp --> yow.h tree_edge: bar.cpp --> yow.h discover_vertex: yow.h examine_edge: yow.h --> dax.h back_edge: yow.h --> dax.h examine_edge: yow.h --> bar.cpp back_edge: yow.h --> bar.cpp examine_edge: yow.h --> zag.cpp tree_edge: yow.h --> zag.cpp discover_vertex: zag.cpp examine_edge: zag.cpp --> yow.h back_edge: zag.cpp --> yow.h examine_edge: zag.cpp --> boz.h tree_edge: zag.cpp --> boz.h discover_vertex: boz.h examine_edge: boz.h --> bar.cpp back_edge: boz.h --> bar.cpp examine_edge: boz.h --> zig.cpp tree_edge: boz.h --> zig.cpp discover_vertex: zig.cpp examine_edge: zig.cpp --> boz.h back_edge: zig.cpp --> boz.h examine_edge: zig.cpp --> zig.o tree_edge: zig.cpp --> zig.o discover_vertex: zig.o examine_edge: zig.o --> zig.cpp back_edge: zig.o --> zig.cpp examine_edge: zig.o --> libzigzag.a tree_edge: zig.o --> libzigzag.a discover_vertex: libzigzag.a examine_edge: libzigzag.a --> libfoobar.a back_edge: libzigzag.a --> libfoobar.a examine_edge: libzigzag.a --> zig.o back_edge: libzigzag.a --> zig.o examine_edge: libzigzag.a --> zag.o tree_edge: libzigzag.a --> zag.o discover_vertex: zag.o examine_edge: zag.o --> zag.cpp back_edge: zag.o --> zag.cpp examine_edge: zag.o --> libzigzag.a back_edge: zag.o --> libzigzag.a finish_vertex: zag.o examine_edge: libzigzag.a --> killerapp tree_edge: libzigzag.a --> killerapp discover_vertex: killerapp examine_edge: killerapp --> libzigzag.a back_edge: killerapp --> libzigzag.a finish_vertex: killerapp finish_vertex: libzigzag.a finish_vertex: zig.o finish_vertex: zig.cpp examine_edge: boz.h --> zag.cpp back_edge: boz.h --> zag.cpp finish_vertex: boz.h examine_edge: zag.cpp --> zag.o forward_or_cross_edge: zag.cpp --> zag.o !!!!!! finish_vertex: zag.cpp finish_vertex: yow.h examine_edge: bar.cpp --> boz.h forward_or_cross_edge: bar.cpp --> boz.h !!!!!! examine_edge: bar.cpp --> bar.o back_edge: bar.cpp --> bar.o finish_vertex: bar.cpp examine_edge: bar.o --> libfoobar.a back_edge: bar.o --> libfoobar.a finish_vertex: bar.o examine_edge: libfoobar.a --> libzigzag.a forward_or_cross_edge: libfoobar.a --> libzigzag.a !!!!!! finish_vertex: libfoobar.a finish_vertex: foo.o finish_vertex: foo.cpp examine_edge: dax.h --> bar.cpp forward_or_cross_edge: dax.h --> bar.cpp !!!!!! examine_edge: dax.h --> yow.h forward_or_cross_edge: dax.h --> yow.h !!!!!! finish_vertex: dax.h What is the problem? Thanks. Zhiyu 2013-06-24 lizy10b
On Mon, 24 Jun 2013, lizy10b wrote:
Hi there I have a problem with the DFS method (Boost 1.53). I found when invoking the DFS method on a undirected graph, the "forward_or_cross_edge" was called more than one ti mes. But as the document says "In an undirected graph this method is never called". http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/DFSVisitor.html I performed the test based on the file_dependencies.cpp example (examples/file_dependencies.cpp; http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/file_dependency_example....) 1) Change the graph type from "bidirectionalS" to "undirected". 2)Implement all the 8 DFS vistor "event methods" (Initialize Vertex, Start Vertex, Discover Vertex, Examine Edge, T ree Edge, Back Edge, Forward or Cross Edge, Finish Vertex) in the cycle_detector struct to print the vertex names, edge sources and targets. 3)comment out some code at the begining of the example cpp files as the topological_sort method raise exception upon the undirected graph.
Does undirected_dfs() do the same thing? I don't think the directed version should call forward_or_cross_edge when given an undirected graph, though. Would it be possible for you to print out the vertex->color mapping when forward_or_cross_edge is called? Also, it would be nice if you'd send your complete test program. Thanks. -- Jeremiah Willcock
Hi�there I�have�a�problem�with�the�DFS�method?Boost?.53).? I�found�when�invoking�the�DFS�method�on�a�undirected�graph,�the?forward_or_cross_edge"�was�called�more�than�one�ti mes.? But�as�the�document�says?In�an�undirected�graph�this�method�is�never�called". http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/DFSVisitor.html ? I�performed�the�test�based�on�the�file_dependencies.cpp�example ?examples/file_dependencies.cpp;�http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/file_dependency_example....) 1) Change�the�graph�type�from?bidirectionalS"�to?undirected". 2)Implement�all�the?�DFS�vistor?event�methods"?Initialize�Vertex,�Start�Vertex,�Discover�Vertex,�Examine�Edge,�T ree�Edge,�Back�Edge,�Forward�or�Cross�Edge,�Finish�Vertex) in�the cycle_detector�struct�to�print�the�vertex�names,�edge�sources�and�targets. 3)comment�out�some�code�at�the�begining�of�the�example cpp�files�as�the�topological_sort�method�raise�exception�upon�the�undirected�graph. Does undirected_dfs() do the same thing? I don't think the directed version should call forward_or_cross_edge when given an undirected graph,
Hi Jeremiah Willcock , It seems undirected_dfs() works. I have not check 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, g)) is required when calling the undirected_dfs() . Thanks Zhiyu Li 2013-06-25 lizy10b �����ˣ� Jeremiah Willcock ����ʱ�䣺 2013-06-24 23:47:20 �ռ��ˣ� boost-users ���ͣ� lizy10b ���⣺ Re: [Boost-users] Confused with Depth-First-Search method, forwardor cross edge found on a undirected graph ? On Mon, 24 Jun 2013, lizy10b wrote: though. Would it be possible for you to print out the vertex->color mapping when forward_or_cross_edge is called? Also, it would be nice if you'd send your complete test program. Thanks. -- Jeremiah Willcock
On Tue, 25 Jun 2013, lizy10b wrote:
Hi Jeremiah Willcock , It seems undirected_dfs() works. I have not check 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, g)) 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
Hi Jeremiah Willcock , ? It seems undirected_dfs() works. I have not�check 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,�g))?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
Hi Jeremiah Willcock, Thanks for your reply. Another question is the vertex color property also required in undirected_dfs()? or only edge color property is enough? Thanks. Zhiyu Li 2013-06-25 lizy10b �����ˣ� 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 graph ? On Tue, 25 Jun 2013, lizy10b wrote: 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
On Tue, 25 Jun 2013, lizy10b wrote:
Hi Jeremiah Willcock, Thanks for your reply. Another question is the vertex color property also required in undirected_dfs()? or only edge color property is enough? Thanks.
There vertex colors are required to know which vertices have already been visited; directing each edge is not enough to keep track of that. -- Jeremiah Willcock
2013-06-25
_________________________________________________________________________________________________________________________________________________________ lizy10b
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
_________________________________________________________________________________________________________________________________________________________ 发件人： 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 graph ? On Tue, 25 Jun 2013, lizy10b wrote: 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
Hi Jeremiah Willcock , ? It seems undirected_dfs() works. I have not�check 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,�g))?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
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() . 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? Thanks Zhiyu Li 2013-06-25 lizy10b �����ˣ� 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 graph ? On Tue, 25 Jun 2013, lizy10b wrote: 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
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
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
_________________________________________________________________________________________________________________________________________________________ 发件人： 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 graph ? On Tue, 25 Jun 2013, lizy10b wrote: 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
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 2013-06-26 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/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
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
_________________________________________________________________________________________________________________________________________________________ 发件人： 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 graph ? On Tue, 25 Jun 2013, lizy10b wrote: 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
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
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
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-br.... but with no result. 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. Any sugguestions will be appreciated. Thanks. Zhiyu Li Student 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: 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
_________________________________________________________________________________________________________________
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
发件人： 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: 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
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-br.... 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
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
_________________________________________________________________________________________________________________________________________________________ 发件人： 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: 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 > >
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. As for the build error of Boost.MPI with MinGW, I will redo it and save the ouput to a file. Thanks. Zhiyu Li 2013-06-28 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 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-br.... 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
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
_________________________________________________________________________________________________________________________________________________________ 发件人： 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: 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
_________________________________________________________________________________________________________________
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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-br.... 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
Hi Jeremiah Willcock I download the two breadth_first_search.hpp files from the trunk (now is R84910) and overwrite my existing files 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 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: 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-br.... 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
______________________________________________________________________________________________________________________________________________________
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
发件人： 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: 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
_________________________________________________________________________________________________________________
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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 files 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
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
___________________________________________________________________________________________________________________________________________________________ 发件人： 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: 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-br.... 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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 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 something) when execute the b2 command to build boost.mpi? Thanks Zhiyu Li 2013-06-29 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 files 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
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
___________________________________________________________________________________________________________________________________________________________ 发件人： 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: 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-br.... 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
______________________________________________________________________________________________________________________________________________________
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
发件人： 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: 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
_________________________________________________________________________________________________________________
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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 something) 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 files 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 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 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 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 VS 20 > 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-br.... 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 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 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@lists.boost.org > http://lists.boost.org/mailman/listinfo.cgi/boost-users > > _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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 Zhiyu Li 2013-06-30 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 something) 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 files 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
________________________________________________________________________________________________________________________________________________________
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 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
发件人： 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: 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 VS 20 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-br.... 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 no t be built either. What is the issue with that version? -- Jeremiah Willcock
2013-06-27
____________________________________________________________________________________________________________________________________________________ __
lizy10b
____________________________________________________________________________________________________________________________________________________ __
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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-br... 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@lists.boost.org > > http://lists.boost.org/mailman/listinfo.cgi/boost-users > > > > > _______________________________________________ > Boost-users mailing list > Boost-users@lists.boost.org > http://lists.boost.org/mailman/listinfo.cgi/boost-users > > _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
The mail server reject my post again. So I truncated some logs. Please refer to the attachment. Thanks Zhiyu Li --------------- Rejected: Sorry for missing of the attachment. Here it is. Thanks Zhiyu Li
Hi Jeremiah Willcock, Attached is the zip package of boost.mpi, pyhton, parallel_graph building and testing logs. Environment is MinGW (gcc 4.7.1) boost.mpi and parallel_graph could be built, but none of the graph_parallel could be built. Thanks Zhiyu Li 2013-07-01 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 something) 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 files 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
________________________________________________________________________________________________________________________________________________________
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 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
发件人： 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: 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 VS 20 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-br.... 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 no t be built either. What is the issue with that version? -- Jeremiah Willcock
2013-06-27
____________________________________________________________________________________________________________________________________________________ __
lizy10b
____________________________________________________________________________________________________________________________________________________ __
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
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: 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-br.... 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
______________________________________________________________________________________________________________________________________________________
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
发件人： 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: 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
_________________________________________________________________________________________________________________
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
发件人： 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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, 28 Jun 2013, lizy10b wrote:
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.
Here is the actual error (for search engines): D:\Program Files (x86)\MPICH2\include/mpicxx.h: At global scope: D:\Program Files (x86)\MPICH2\include/mpicxx.h:2469:17: error: declaration does not declare anything [-fpermissive] It appears that this is a known issue (http://trac.mpich.org/projects/mpich/ticket/1582) that the MPICH team has decided not to fix for some reason. Could you please try adding MPICH_SKIP_MPICXX as a -D flag (to define it as a macro) when building Boost.MPI? I don't remember how to do that, but it should be easy to find. Thanks. -- Jeremiah Willcock
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
___________________________________________________________________________________________________________________________________________________________ 发件人： 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: 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-br.... 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
Jeremiah Willcock -
Jeremiah Willcock -
lizy10b