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

From: Alejandro Aragón (alex_aragon_at_[hidden])
Date: 2006-03-10 16:06:43

Douglas Gregor wrote:
> On Mar 6, 2006, at 12:23 AM, Alejandro Aragón wrote:
>> 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);
> 
> I think you can change this line to:
> 
>    v_new = add_vertex(get(vertex_all, *gPtr, *vi), *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);
> 
> And then change this line to:
> 
>    tie(e_new, inserted) = add_edge(source(*ei, *gPtr), target(*ei,  
> *gPtr), get(edge_all, *gPtr, *ei), *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;
> 
> boost/graph/copy.hpp uses edge_all and vertex_all; you might be able  
> to look there for more hints.
> 
> 	Doug

It works perfectly!  Thanks for the changes Doug.  I would like to go 
further with this.  I'm not an expert in c++ programming but I will try 
to make this funciton a template and I will provide a couple of 
examples.  Maybe I will see it implemented in the library some day! =)

Alejandro Aragon