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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-02-17 20:43:06

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