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
#include
#include
#include
#include
typedef boost::adjacency_list_traits< boost::vecS, boost::vecS,
boost::undirectedS >::vertex_descriptor vertex_descriptor;
typedef boost::property >
VertexProperty;
typedef boost::property > > EdgeProperty;
typedef boost::subgraph< boost::adjacency_list > Graph;
typedef boost::graph_traits < Graph >::edge_descriptor Edge;
int main(void)
{
int num=5;
Graph g(num);
boost::property_map::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;
}
