[Boost-users] Creating a mst graph from another, undirected one

17 Feb 2005

      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 <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

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<graph_traits<UGraph>::edge_descriptor> 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