Re: [Boost-users] graph: Min Spanning Tree (advanced start)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2003-11-12 21:04:52

Hi Matthew,

Yes, that is, as long as that initial list of edges forms a tree.

Here's my guess as how to do it for prim's minimum spanning tree.

You'll have to directly call breadth_first_visit, redoing all the
initialization work done in dijkstra and prim (prim calls dijkstra, which
then calls bfs).

You'll need to initialize the predecessor map to reflect the starting
tree, and also you'll want to set the color of the nodes in the starting
tree to black. Then you'll have to color the nodes adjacent to nodes in
the tree (that aren't in the tree) gray and stick them in the priority
queue... that is, all except for one of the nodes adjacent to the tree
(pick an arbitrary one). That node will be your starting node for the bfs.

In you're using Kruskal's it is a different story... I'll look at that
later if you need it.

Cheers,
Jeremy

On Wednesday, November 12, 2003, at 11:24 AM, Matthew Galati wrote:

> Is there a way to give an advanced start to solve Min Spanning Tree
> using boost/graph? That is, I have a list of edges in my graph that
> must be in the Min Spanning Tree (i.e., their cost is -M, for very big
> M).
>
> Since algorithms for MST are greedy, I assume this can be done - but
> is their an easy way to interface to boost/graph's MST algorithms?
>
> Thanks for any help.
> Matt
>
> --
> 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