[BGL] graph copy after Kruskal's algorithm?
Hi all, 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, A.Aragon
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 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; }
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
On Mar 6, 2006, at 12:23 AM, Alejandro Aragón wrote:
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);
I think you can change this line to: v_new = add_vertex(get(vertex_all, *gPtr, *vi), *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);
And then change this line to: tie(e_new, inserted) = add_edge(source(*ei, *gPtr), target(*ei, *gPtr), get(edge_all, *gPtr, *ei), *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;
boost/graph/copy.hpp uses edge_all and vertex_all; you might be able to look there for more hints. Doug
Douglas Gregor wrote:
On Mar 6, 2006, at 12:23 AM, Alejandro Aragón wrote:
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);
I think you can change this line to:
v_new = add_vertex(get(vertex_all, *gPtr, *vi), *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);
And then change this line to:
tie(e_new, inserted) = add_edge(source(*ei, *gPtr), target(*ei, *gPtr), get(edge_all, *gPtr, *ei), *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;
boost/graph/copy.hpp uses edge_all and vertex_all; you might be able to look there for more hints.
Doug
It works perfectly! Thanks for the changes Doug. I would like to go further with this. I'm not an expert in c++ programming but I will try to make this funciton a template and I will provide a couple of examples. Maybe I will see it implemented in the library some day! =) Alejandro Aragon
On Mar 10, 2006, at 4:06 PM, Alejandro Aragón wrote:
It works perfectly! Thanks for the changes Doug. I would like to go further with this. I'm not an expert in c++ programming but I will try to make this funciton a template and I will provide a couple of examples. Maybe I will see it implemented in the library some day! =)
Great! If you manage to clean it up and submit it, we'd love to add it into the BGL. Doug
participants (4)
-
Alejandro Aragón -
Dmitry -
Doug Gregor -
Douglas Gregor