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
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