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

On Feb 17, 2005, at 6:31 AM, aitor wrote:

#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 ? }

// Build the vertices with: MSTree mst(num_vertices(g); // Since both graphs use VertexListS=vecS, we can mega-cheat and build the graph like this: for (int i = 0; i < mst_edges.size(); ++i) add_edge(source(mst_edges[i], g), target(mst_edges[i], g), mst); There is another way that may be _slightly_ more efficient (especially if you want to use OutEdgeListS=vecS for the MST graph), but it takes a little too long for me to type out as code. The idea is to use the iterator constructor of adjacency_list and pass it some iterator adaptors that turn edge descriptors into std::pairs. For instance, you would build the mst graph like this: MSTree mst(make_edge_iterator(mst_edges.begin(), g, get(vertex_index, g)), make_edge_iterator(mst_edges.end(), g, get(vertex_index, g)), n); make_edge_iterator would have to create an iterator adaptor that turns an edge_descriptor e into std::make_pair(get(vertex_index, source(e, g)), get(vertex_index, target(e, g))). You could probably use the transform_iterator adaptor in the Iterator Adaptors library to do this really easily, but I'm wrapping up a marathon debugging session and can't write it at the moment :) Doug