Re: [Boost-users] Creating a mst graph from another, undirected one

From: aitor (aitors2005_at_[hidden])
Date: 2005-02-18 06:44:41

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