Creating a mst graph from another, undirected one
Hello, i'm working with a (huge) undirected graph, with severeal internal properties in both vertices and edges, including weights. At one point, i compute the minumim spanning tree of the graph. The question is simple: how can i create another graph (a tree, so a directed graph) from the original undirected graph plus the list of edges conforming the mst ? And how can i do it _efficiently_ (considering that the original graph will be huge) ? Consider this seudo-code: #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp> typedef adjacency_list < boost::listS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> UGraph; typedef adjacency_list < boost::listS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties> MSTree; void createGraph() { UGraph g; add_vertices(); add_edges(); compute_edges_weights(); vector<graph_traits<UGraph>::edge_descriptor> mst_edges(num_vertices(g)); kruskal_minimum_spanning_tree(g, back_inserter(mst_edges)); // At this point i want to create another graph of type MSTree from // g and mst_edges. How can i do it efficiently ? } thank you in advance aitor
On Feb 17, 2005, at 6:31 AM, aitor wrote:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/property_map.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp>
typedef adjacency_list < boost::listS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> UGraph;
typedef adjacency_list < boost::listS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties> MSTree;
void createGraph() {
UGraph g;
add_vertices(); add_edges(); compute_edges_weights();
vector<graph_traits<UGraph>::edge_descriptor> mst_edges(num_vertices(g)); kruskal_minimum_spanning_tree(g, back_inserter(mst_edges));
// At this point i want to create another graph of type MSTree from // g and mst_edges. How can i do it efficiently ? }
// Build the vertices with: MSTree mst(num_vertices(g); // Since both graphs use VertexListS=vecS, we can mega-cheat and build the graph like this: for (int i = 0; i < mst_edges.size(); ++i) add_edge(source(mst_edges[i], g), target(mst_edges[i], g), mst); There is another way that may be _slightly_ more efficient (especially if you want to use OutEdgeListS=vecS for the MST graph), but it takes a little too long for me to type out as code. The idea is to use the iterator constructor of adjacency_list and pass it some iterator adaptors that turn edge descriptors into std::pair<int, int>s. For instance, you would build the mst graph like this: MSTree mst(make_edge_iterator(mst_edges.begin(), g, get(vertex_index, g)), make_edge_iterator(mst_edges.end(), g, get(vertex_index, g)), n); make_edge_iterator would have to create an iterator adaptor that turns an edge_descriptor e into std::make_pair(get(vertex_index, source(e, g)), get(vertex_index, target(e, g))). You could probably use the transform_iterator adaptor in the Iterator Adaptors library to do this really easily, but I'm wrapping up a marathon debugging session and can't write it at the moment :) Doug
Hi, first of all, thank you for your quick answer. However, i have yet some questions :) Thu, Feb 17, 2005 egunean, Doug Gregor-k zera esan zuen :
On Feb 17, 2005, at 6:31 AM, aitor wrote:
typedef adjacency_list < boost::listS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> UGraph;
typedef adjacency_list < boost::listS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties> MSTree;
void createGraph() {
UGraph g;
add_vertices(); add_edges(); compute_edges_weights();
vector<graph_traits<UGraph>::edge_descriptor> mst_edges(num_vertices(g)); kruskal_minimum_spanning_tree(g, back_inserter(mst_edges));
// At this point i want to create another graph of type MSTree from // g and mst_edges. How can i do it efficiently ? }
// Build the vertices with: MSTree mst(num_vertices(g);
// Since both graphs use VertexListS=vecS, we can mega-cheat and build the graph like this: for (int i = 0; i < mst_edges.size(); ++i) add_edge(source(mst_edges[i], g), target(mst_edges[i], g), mst);
Ok. But the problem is that, as that the original graph isn't directed, neither are the edges. So, i can't determine wether source(mst_edges[i],g) is the "father" or the "son" of the edge in the mst tree. regards aitor
Hello again, Fri, Feb 18, 2005 egunean, aitor-k zera esan zuen :
Hi,
Ok. But the problem is that, as that the original graph isn't directed, neither are the edges. So, i can't determine wether source(mst_edges[i],g) is the "father" or the "son" of the edge in the mst tree.
Instead of "father os son of the edge" i wanted to say "father or son of the vertex", sorry for the typo. Let me clarify my point. Suppose this graph: [vertex_number]:[vertex_name] {[adjacent_vertices]+} 0:a {b,c,d} 1:b {a} 2:c {a,d} 3:d {a} the mst_edges vector gets: (0,1),(3,2),(0,2) but if i build the mst the way you indicate, it gives me this graph: 0:a 3:d / \ / 1:b 2:c which is not a tree, instead of: 0:a / \ 1:b 2:c | 3:d that is what i want. Note that the problem is the edge (3,2) in the mst_vertices vector; it should be (2,3) in the directed graph. Any ideas ? regards aitor
On Feb 18, 2005, at 9:56 AM, aitor wrote: [snip]
(0,1),(3,2),(0,2)
but if i build the mst the way you indicate, it gives me this graph:
0:a 3:d / \ / 1:b 2:c
which is not a tree, instead of:
0:a / \ 1:b 2:c | 3:d
that is what i want. Note that the problem is the edge (3,2) in the mst_vertices vector; it should be (2,3) in the directed graph. Any ideas ?
If you use Prim's algorithm instead of Kruskal's algorithms, you actually get the tree built within a property map (the property map will go from vertices to their predecessors in the tree, leading back to the source). Doug
Fri, Feb 18, 2005 egunean, Doug Gregor-k zera esan zuen :
On Feb 18, 2005, at 9:56 AM, aitor wrote: [snip]
(0,1),(3,2),(0,2)
but if i build the mst the way you indicate, it gives me this graph:
0:a 3:d / \ / 1:b 2:c
which is not a tree, instead of:
0:a / \ 1:b 2:c | 3:d
that is what i want. Note that the problem is the edge (3,2) in the mst_vertices vector; it should be (2,3) in the directed graph. Any ideas ?
If you use Prim's algorithm instead of Kruskal's algorithms, you actually get the tree built within a property map (the property map will go from vertices to their predecessors in the tree, leading back to the source).
Yes, that made the trick. Thank you ! aitor
participants (6)
-
aitor -
Doug Gregor