
Boost Users : 
From: Dmitry (dmitry_at_[hidden])
Date: 20060306 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net