Re: prim_minimum_spanning_tree crashes

From: Stephan Höfer (yg-boost-users_at_[hidden])
Date: 2003-08-06 10:17:28

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_at_[hidden]
>  C++ Booster (http://www.boost.org)   office phone: [phone]
> ----------------------------------------------------------------------
>
>
> Info: <http://www.boost.org>
> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
> Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/