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 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

On Feb 18, 2005, at 9:56 AM, aitor wrote: [snip]

(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 ?

If you use Prim's algorithm instead of Kruskal's algorithms, you actually get the tree built within a property map (the property map will go from vertices to their predecessors in the tree, leading back to the source). Doug