[Boost-users] boost/graph - induced subgraph

From: Matthew Galati (magh_at_[hidden])
Date: 2004-03-22 15:15:15

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_at_[hidden], magal11_at_[hidden]
http://sagan.ie.lehigh.edu/mgalati/