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