Boost logo

Boost Users :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-03-22 17:31:58


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_at_[hidden], magal11_at_[hidden]
> http://sagan.ie.lehigh.edu/mgalati/
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net