Hello,
i'm working with a (huge) undirected graph, with severeal internal
properties in both vertices and edges, including weights. At one point, i
compute the minumim spanning tree of the graph. The question is simple: how
can i create another graph (a tree, so a directed graph) from the original
undirected graph plus the list of edges conforming the mst ? And how can i
do it _efficiently_ (considering that the original graph will be huge) ?
Consider this seudo-code:
#include
#include
#include
#include
#include
typedef adjacency_list <
boost::listS,
boost::vecS,
boost::undirectedS,
VertexProperties,
EdgeProperties> UGraph;
typedef adjacency_list <
boost::listS,
boost::vecS,
boost::directedS,
VertexProperties,
EdgeProperties> MSTree;
void createGraph() {
UGraph g;
add_vertices();
add_edges();
compute_edges_weights();
vector mst_edges(num_vertices(g));
kruskal_minimum_spanning_tree(g, back_inserter(mst_edges));
// At this point i want to create another graph of type MSTree from
// g and mst_edges. How can i do it efficiently ?
}
thank you in advance
aitor
