Re: [Boost-users] [BGL] graph copy after Kruskal's algorithm?

From: Alejandro Aragón (alex_aragon_at_[hidden])
Date: 2006-03-06 00:23:42

Doug Gregor wrote:
> On Feb 26, 2006, at 11:47 PM, Alejandro Aragón wrote:
>> After running Kruskal's algorithm I end up with the list of the edges
>> that form the minimum cost.  However, no new graph is created.  I need
>> the resulting graph for further computations.  How do you create a 
>> graph
>> from an existing one but only selecting the edges contained in the
>> minimum spanning tree vector?  I've seen that there are some functions
>> to accomplish this but I couldn't find any example of how to do it:
>>
>> template <class EdgeIterator, class EdgePropertyIterator>
>> adjacency_list(EdgeIterator first, EdgeIterator last,
>>                 EdgePropertyIterator ep_iter,
>>                 vertices_size_type n,
>>                 vertices_size_type m = 0,
>>                 const GraphProperty& p = GraphProperty())
>>
>> The existing graph has properties in edges and vertices that I also 
>> need
>> to keep.  Can anyone help?  Thank you all,
> 
> Unfortunately, the above constructor probably won't help. I expect 
> you'll need to write the copy routine yourself, because I don't know of 
> a function in the Graph library that does exactly what you want. The 
> simple way to do this is:
> 
> 	- Create a new, empty graph
> 	- Create a property map orig2copy that maps from the old graph's 
> vertex descriptors to the new graph's vertex descriptors
> 	- For each vertex v in the original graph, add_vertex on the new graph 
> using get(vertex_all, orig, v)  for the value of the properties, then 
> setup the correspondence orig2copy[v] = the new vertex.
> 	- For each edge e, add the edge (orig2copy[source(e, orig)], 
> orig2copy[target(e, orig)]) using get(edge_all, orig, e) for the value 
> of the properties.
> 
> Make that a generic function template with a test case and we can add 
> it into the BGL :)
> 
> 	Doug

Doug,

I tried to follow your directions but I coundn't find any concrete 
example of using the get(vertex_all,orig,v) function.  I did something 
else, but I think it is not working.  Could you give me further 
directions to code it your way?

This is what I came up with:

// minimum_spanning_graph
Graph* graph::minimum_spanning_graph(std::vector<Edge>& spanning_tree)
{
     // create an empty graph
     // the original graph has pointer gPtr
     Graph* copy = new Graph();

     // iterate over all vertices in the original graph
     Vertex v_new;
     for (tie(vi, vi_end) = vertices(*gPtr); vi != vi_end; ++vi){
        v_new = add_vertex(*copy);
        coordmap[v_new] = coordmap[*vi];
     }

     // iterate over all the edges in the list produced by algorithm
     bool inserted;
     Edge e_new;
     for (std::vector < Edge >::iterator ei = spanning_tree.begin();
         ei != spanning_tree.end(); ++ei) {
        tie(e_new,inserted) = add_edge(source(*ei,*gPtr),target(*ei,*gPtr),*copy);
        weightmap[e_new] = weightmap[*ei];
        anglemap[e_new] = anglemap[*ei];
     }

     std::cout<<"Number of edges in original graph = 
"<<num_edges(*gPtr)<<std::endl;
     std::cout<<"Number of edges in minimum spanning graph 
="<<num_edges(*copy)<<std::endl;

     return copy;

}