From: Dmitry (dmitry_at_[hidden])
Date: 2006-03-06 08:15:25
Alejandro Aragón wrote:
> 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;
>
> }
I gues that:
get(vertex_all, copy, v).m_value = get(vertex_all, orig, v) .m_value
exacly is what are you looking for, but it doesn't looks too generic((
--dima