[Boost-users] vertex structure

From: bayer.tomas_at_[hidden]
Date: 2007-11-24 18:48:49

Hello,

I have the problem with the vertex structure definition. I don´t know, how
to create graph with variable vertices count without vertices renaming.

Source graph: (n=5 vertices)
Edges { E(130, 27), E(1, 83), E(1, 204), E(27, 1), E(27, 130), E(83, 204),
E(204, 130)};

To find minimal spannig tree using Prim leeds to vertices renaming <0,n-1>.
Renamed graph:
Edges { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 0), E(3, 4), E(4, 0)}.

But it is very uncomfortable. How could I use original vertices number in
graph definition?

Thanks

Tomas

My source code:

#include <boost/config.hpp>

#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)
{
int num=5;

Graph g(num);

boost::property_map<Graph, boost::edge_weight_t>::type weightmap =
boost::get(boost::edge_weight, g);
Edge e; bool inserted;

//Here I would like to use original vertices numbers
boost::tie(e, inserted) = boost::add_edge(0, 2, g); weightmap[e] = 1;
boost::tie(e, inserted) = boost::add_edge(1, 3, g); weightmap[e] = 1;
boost::tie(e, inserted) = boost::add_edge(1, 4, g); weightmap[e] = 1;
boost::tie(e, inserted) = boost::add_edge(2, 1, g); weightmap[e] = 1;
boost::tie(e, inserted) = boost::add_edge(2, 0, 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, 0, g); weightmap[e] = 1;

std::vector < boost::graph_traits < Graph >::vertex_descriptor >
    p(num_vertices(g));

boost::prim_minimum_spanning_tree(g, &p[0]);
 for (std::size_t i = 0; i != p.size(); ++i)
    if (p[i] != i)
      std::cout << "parent[" << i << "] = " << p[i] << std::endl;
    else
      std::cout << "parent[" << i << "] = no parent" << std::endl;

}