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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-02-27 09:59:16

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