On Feb 17, 2005, at 6:31 AM, aitor wrote:
#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 ? }
// 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::pair<int, int>s. 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