prim_minimum_spanning_tree crashes
Hello, I try to use prim_minimum_spanning_tree to find rings in subgraphs doing the following: typedef subgraph< adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> > Graph; /... building Graph g with some vertices and edges for(int i=0; i<7; ++i) { add_vertex(g); LAMath::Vec3_f tVec((float)i, (float)(6-i), .0); put(vertex_point_t(), g, i, tVec); } property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g); Edge e; bool inserted; tie(e, inserted) = add_edge(0, 1, g); weightmap[e] = 1; tie(e, inserted) = add_edge(1, 2, g); weightmap[e] = 1; tie(e, inserted) = add_edge(2, 3, g); .../ Graph tSubGraph = g.create_subgraph(); add_vertex(1, tSubGraph); add_vertex(3, tSubGraph); add_vertex(4, tSubGraph); add_vertex(6, tSubGraph); std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(tSubGraph)); prim_minimum_spanning_tree(tSubGraph, &p[0]); After having created the graph g, I call the create_subgraph member function to get an induced subgraph of it. Trying to use the prim_minimum_spanning_tree function it crashes in dijkstra_dispatch1 by trying to delete the local variable std::vector<D> distance_map(n). Is there something missing in my code which leads to that crash? It works for the root graph but not for any new created subgraph. Help would be appreciated. Thanks in advance Stephan
----- Original Message ----- From: "Stephan Höfer" <yg-boost-users@gmane.org>
Graph tSubGraph = g.create_subgraph();
Ah ha! You want: Graph& tSubGraph = g.create_subgraph(); The root graph actually allocates a new child in its own memory space in create_subgraph(), and then gives you a reference to the subgraph. What's happening here is that subgraph is getting double-freed. Yes, we should do something to protect against this. Doug
Apologies if this is a duplicate, the original one I sent didn't show up in my inbox nor on the yahoogroups page so I thought I'd better send it again. I am wrapping a class with an operator()(int, int) which I'd like to make available in Python as a subscript operator, but haven't been able to find any documentation on this nor guess the appropriate .def Is this possible and if so can anyone help? Regards, Chris.
Thank you for the hint. I've overseen that. But beside that there must be another mistake, because it crashes again after that slight change of the code. Douglas Gregor schrieb:
----- Original Message ----- From: "Stephan Höfer" <yg-boost-users@gmane.org>
Graph tSubGraph = g.create_subgraph();
Ah ha! You want:
Graph& tSubGraph = g.create_subgraph();
The root graph actually allocates a new child in its own memory space in create_subgraph(), and then gives you a reference to the subgraph. What's happening here is that subgraph is getting double-freed. Yes, we should do something to protect against this.
Doug
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
I haven't been following the thread, but if you post a small (less than one page) but complete example program that exhibits the crash I'd be willing to take a look. Cheers, Jeremy On Tuesday, August 5, 2003, at 02:21 AM, Stephan Höfer wrote:
Thank you for the hint. I've overseen that. But beside that there must be another mistake, because it crashes again after that slight change of the code.
the original graph looks like that 0--1--2--3 | | | | 7--6--5--4 the subgraph looks like that 0--1--2 | | 6--5 typedef boost::property<boost::vertex_color_t, boost::default_color_type, boost::property< boost::vertex_predecessor_t, vertex_descriptor > > VertexProperty; typedef boost::property<boost::edge_color_t, boost::default_color_type, boost::property<boost::edge_weight_t, int, boost::property<boost::edge_index_t, int > > > EdgeProperty; typedef boost::subgraph< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty > > Graph; void main() { Graph g(7); boost::property_map<Graph, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g); Edge e; bool inserted; boost::tie(e, inserted) = boost::add_edge(0, 1, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(1, 2, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(2, 3, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(4, 5, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(5, 2, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(5, 6, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(6, 1, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(6, 7, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(7, 0, g); weightmap[e] = 1; Graph& tSubGraph = g.create_subgraph(); add_vertex(0,tSubGraph); add_vertex(1,tSubGraph); add_vertex(2,tSubGraph); add_vertex(5,tSubGraph); add_vertex(6,tSubGraph); std::vector < boost::graph_traits < Graph >::vertex_descriptor> p(boost::num_vertices(tSubGraph)); boost::prim_minimum_spanning_tree(tSubGraph, &p[0]); } The crash happens after having added for instance the 6th point of the Graph g to the subgraph. Before it worked. Jeremy Siek schrieb:
I haven't been following the thread, but if you post a small (less than one page) but complete example program that exhibits the crash I'd be willing to take a look.
Cheers, Jeremy
On Tuesday, August 5, 2003, at 02:21 AM, Stephan Höfer wrote:
Thank you for the hint. I've overseen that. But beside that there must be another mistake, because it crashes again after that slight change of the code.
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Hi Stephan, What you've posted is not a complete program (it is missing at least the #include's). Please post a complete program. Thanks, Jeremy P.S. Sorry to be pedantic about this, but I've wasted a lot of time in the past trying to reconstruct complete programs from incomplete programs. On Wed, 6 Aug 2003, Stephan [iso-8859-1] Höfer wrote: yg-boo> the original graph looks like that yg-boo> yg-boo> 0--1--2--3 yg-boo> | | | | yg-boo> 7--6--5--4 yg-boo> yg-boo> the subgraph looks like that yg-boo> 0--1--2 yg-boo> | | yg-boo> 6--5 yg-boo> yg-boo> typedef boost::property<boost::vertex_color_t, boost::default_color_type, yg-boo> boost::property< boost::vertex_predecessor_t, vertex_descriptor > > yg-boo> VertexProperty; yg-boo> yg-boo> typedef boost::property<boost::edge_color_t, boost::default_color_type, yg-boo> boost::property<boost::edge_weight_t, int, yg-boo> boost::property<boost::edge_index_t, int > > > EdgeProperty; yg-boo> yg-boo> typedef boost::subgraph< boost::adjacency_list<boost::vecS, boost::vecS, yg-boo> boost::undirectedS, yg-boo> VertexProperty, EdgeProperty > > Graph; yg-boo> yg-boo> void main() yg-boo> { yg-boo> Graph g(7); yg-boo> yg-boo> boost::property_map<Graph, boost::edge_weight_t>::type weightmap = yg-boo> boost::get(boost::edge_weight, g); yg-boo> Edge e; bool inserted; yg-boo> yg-boo> boost::tie(e, inserted) = boost::add_edge(0, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(1, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(2, 3, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(4, 5, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 6, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 7, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(7, 0, g); weightmap[e] = 1; yg-boo> yg-boo> Graph& tSubGraph = g.create_subgraph(); yg-boo> yg-boo> add_vertex(0,tSubGraph); add_vertex(1,tSubGraph); add_vertex(2,tSubGraph); yg-boo> add_vertex(5,tSubGraph); add_vertex(6,tSubGraph); yg-boo> yg-boo> std::vector < boost::graph_traits < Graph >::vertex_descriptor> yg-boo> p(boost::num_vertices(tSubGraph)); yg-boo> boost::prim_minimum_spanning_tree(tSubGraph, &p[0]); yg-boo> } yg-boo> yg-boo> The crash happens after having added for instance the 6th point of the Graph yg-boo> g to the subgraph. Before it worked. yg-boo> ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Now I've completed the program. Some BGL includes were missing and two typedefs. I was able to compile this little program with the VC++ .net compiler. It crashes as described after adding the vertex 6 to the subgraph. Even for other vertices this happend. #include <boost/config.hpp> // put this first to suppress some VC++ warnings #include <boost/utility.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> #include <boost/graph/subgraph.hpp> typedef boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::undirectedS >::vertex_descriptor vertex_descriptor; typedef boost::property<boost::vertex_color_t, boost::default_color_type, boost::property< boost::vertex_predecessor_t, vertex_descriptor > > VertexProperty; typedef boost::property<boost::edge_color_t, boost::default_color_type, boost::property<boost::edge_weight_t, int, boost::property<boost::edge_index_t, int > > > EdgeProperty; typedef boost::subgraph< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty > > Graph; typedef boost::graph_traits < Graph >::edge_descriptor Edge; int main(void) { Graph g(7); boost::property_map<Graph, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g); Edge e; bool inserted; boost::tie(e, inserted) = boost::add_edge(0, 1, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(1, 2, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(2, 3, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(4, 5, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(5, 2, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(5, 6, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(6, 1, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(6, 7, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(7, 0, g); weightmap[e] = 1; Graph& tSubGraph = g.create_subgraph(); boost::add_vertex(0,tSubGraph);boost::add_vertex(1,tSubGraph); boost::add_vertex(2,tSubGraph);boost::add_vertex(5,tSubGraph); boost::add_vertex(6,tSubGraph); std::vector < boost::graph_traits < Graph >::vertex_descriptor> p(boost::num_vertices(tSubGraph)); boost::prim_minimum_spanning_tree(tSubGraph, &p[0]); } Cheers, Stephan Jeremy Siek schrieb:
Hi Stephan,
What you've posted is not a complete program (it is missing at least the #include's). Please post a complete program.
Thanks, Jeremy
P.S. Sorry to be pedantic about this, but I've wasted a lot of time in the past trying to reconstruct complete programs from incomplete programs.
On Wed, 6 Aug 2003, Stephan [iso-8859-1] Höfer wrote: yg-boo> the original graph looks like that yg-boo> yg-boo> 0--1--2--3 yg-boo> | | | | yg-boo> 7--6--5--4 yg-boo> yg-boo> the subgraph looks like that yg-boo> 0--1--2 yg-boo> | | yg-boo> 6--5 yg-boo> yg-boo> typedef boost::property<boost::vertex_color_t, boost::default_color_type, yg-boo> boost::property< boost::vertex_predecessor_t, vertex_descriptor > > yg-boo> VertexProperty; yg-boo> yg-boo> typedef boost::property<boost::edge_color_t, boost::default_color_type, yg-boo> boost::property<boost::edge_weight_t, int, yg-boo> boost::property<boost::edge_index_t, int > > > EdgeProperty; yg-boo> yg-boo> typedef boost::subgraph< boost::adjacency_list<boost::vecS, boost::vecS, yg-boo> boost::undirectedS, yg-boo> VertexProperty, EdgeProperty > > Graph; yg-boo> yg-boo> void main() yg-boo> { yg-boo> Graph g(7); yg-boo> yg-boo> boost::property_map<Graph, boost::edge_weight_t>::type weightmap = yg-boo> boost::get(boost::edge_weight, g); yg-boo> Edge e; bool inserted; yg-boo> yg-boo> boost::tie(e, inserted) = boost::add_edge(0, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(1, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(2, 3, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(4, 5, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 6, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 7, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(7, 0, g); weightmap[e] = 1; yg-boo> yg-boo> Graph& tSubGraph = g.create_subgraph(); yg-boo> yg-boo> add_vertex(0,tSubGraph); add_vertex(1,tSubGraph); add_vertex(2,tSubGraph); yg-boo> add_vertex(5,tSubGraph); add_vertex(6,tSubGraph); yg-boo> yg-boo> std::vector < boost::graph_traits < Graph >::vertex_descriptor> yg-boo> p(boost::num_vertices(tSubGraph)); yg-boo> boost::prim_minimum_spanning_tree(tSubGraph, &p[0]); yg-boo> } yg-boo> yg-boo> The crash happens after having added for instance the 6th point of the Graph yg-boo> g to the subgraph. Before it worked. yg-boo>
---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Hi Stephan, There was a bug in the subgraph implementation. The vertex_index property map for the subgraph was returning the global indices instead of the local indices, which caused havoc when it tried to use the global indices to lookup in a local property map. I've checked in the fix to subgraph.hpp into CVS. On Wed, 6 Aug 2003, Stephan [iso-8859-1] Höfer wrote: yg-boo> yg-boo> int main(void) yg-boo> { yg-boo> Graph g(7); Also note that the above should be "8" instead of "7". yg-boo> boost::property_map<Graph, boost::edge_weight_t>::type weightmap = yg-boo> boost::get(boost::edge_weight, g); yg-boo> Edge e; bool inserted; yg-boo> yg-boo> boost::tie(e, inserted) = boost::add_edge(0, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(1, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(2, 3, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(4, 5, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 2, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(5, 6, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 1, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(6, 7, g); weightmap[e] = 1; yg-boo> boost::tie(e, inserted) = boost::add_edge(7, 0, g); weightmap[e] = 1; Best Regards, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
participants (4)
-
Christopher Dawson -
Douglas Gregor -
Jeremy Siek -
Stephan Höfer