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

From: aitor (aitors2005_at_[hidden])
Date: 2005-02-18 09:56:58

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