boost/graph - induced subgraph
Is it possible to find the minimum spanning tree of an induced subgraph? vector< graph_traits<Graph>::vertex_descriptor > vd; typedef subgraph< Graph > SubGraph; SubGraph & inducedG = subG.create_subgraph(vd.begin(), vd.end()); Here is the example I am looking at: induced verts: 1 2 3 4 5 7 Original Graph: 0 <--> 1 2 5 7 1 <--> 0 3 5 7 2 <--> 0 3 4 5 3 <--> 2 1 4 5 4 <--> 2 3 5 6 5 <--> 0 1 2 3 4 6 7 6 <--> 4 5 7 7 <--> 0 1 5 6 Induced Graph: 1 <--> 3 5 7 2 <--> 3 4 5 3 <--> 2 1 4 5 4 <--> 2 3 5 5 <--> 1 2 3 4 7 7 <--> 1 5 So, the "create_subgraph" seems to be working fine. But, when I run kruskals with: vector<graph_traits < SubGraph >::edge_descriptor> spanning_tree; kruskal_minimum_spanning_tree(inducedG, back_inserter(spanning_tree)); for (vei = spanning_tree.begin(); vei != spanning_tree.end(); ++vei) { pair<int,int> ij = incident(*vei, inducedG); int edge_index = e_index[*vei]; cout << "e_index: " << edge_index << " : " << ij.first << " " << ij.second << endl; I get a spanning tree of just 4 edges (while the subgraph has 6 vertices). Also, how does the edge_index of the subgraph correspond to the original graph? For example, edge (4,1) is not in the original graph, but it shows up in my spanning tree. Spanning Tree: e_index: 3 : 2 0 e_index: 7 : 4 0 e_index: 4 : 3 1 e_index: 8 : 4 1 Thanks, Matthew -- Matthew Galati ISE Lehigh University IBM Service Parts Solutions 610.758.4042 (Office) 610.882.0779 (Home) magh@lehigh.edu, magal11@us.ibm.com http://sagan.ie.lehigh.edu/mgalati/
Hello boost users I have just started looking in to the boost libs and the extra good stuff they offer. The only problem is that I am having problems installing and building the libs on my MAC OS X system. if there is some tips about how I should be doing this I promise I will ask better questions in the future. thanks regards Michael J Short IBM Sweden Student master in advanced realtime systems
On Mar 22, 2004, at 5:12 PM, Michael Short wrote:
The only problem is that I am having problems installing and building the libs on my MAC OS X system.
What kind of problems? What version of OS X? I built boost 1.31.0 on OS X 10.3.2. I think the regex library gave me some problems, but I believe everything else built OK. I just followed the directions here: http://www.boost.org/more/getting_started.html -jim
Hi Matthew, If you post a small but complete C++ program I'll take a closer look. Cheers, Jeremy On Mar 23, 2004, at 7:15 AM, Matthew Galati wrote:
Is it possible to find the minimum spanning tree of an induced subgraph?
vector< graph_traits<Graph>::vertex_descriptor > vd; typedef subgraph< Graph > SubGraph; SubGraph & inducedG = subG.create_subgraph(vd.begin(), vd.end());
Here is the example I am looking at:
induced verts: 1 2 3 4 5 7
Original Graph: 0 <--> 1 2 5 7 1 <--> 0 3 5 7 2 <--> 0 3 4 5 3 <--> 2 1 4 5 4 <--> 2 3 5 6 5 <--> 0 1 2 3 4 6 7 6 <--> 4 5 7 7 <--> 0 1 5 6
Induced Graph: 1 <--> 3 5 7 2 <--> 3 4 5 3 <--> 2 1 4 5 4 <--> 2 3 5 5 <--> 1 2 3 4 7 7 <--> 1 5
So, the "create_subgraph" seems to be working fine. But, when I run kruskals with:
vector<graph_traits < SubGraph >::edge_descriptor> spanning_tree; kruskal_minimum_spanning_tree(inducedG, back_inserter(spanning_tree));
for (vei = spanning_tree.begin(); vei != spanning_tree.end(); ++vei) { pair<int,int> ij = incident(*vei, inducedG); int edge_index = e_index[*vei]; cout << "e_index: " << edge_index << " : " << ij.first << " " << ij.second << endl;
I get a spanning tree of just 4 edges (while the subgraph has 6 vertices). Also, how does the edge_index of the subgraph correspond to the original graph? For example, edge (4,1) is not in the original graph, but it shows up in my spanning tree.
Spanning Tree: e_index: 3 : 2 0 e_index: 7 : 4 0 e_index: 4 : 3 1 e_index: 8 : 4 1
Thanks, Matthew
-- Matthew Galati ISE Lehigh University IBM Service Parts Solutions 610.758.4042 (Office) 610.882.0779 (Home) magh@lehigh.edu, magal11@us.ibm.com http://sagan.ie.lehigh.edu/mgalati/
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
James Mastro -
Jeremy Siek -
Matthew Galati -
Michael Short