Re: [Boost-users] Directed graphs in Graph Library

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-04-01 15:43:43

On Mar 31, 2005, at 6:57 AM, Dimitris Xochelis wrote:
> I am very interested in the graph library, which I am planning to use 
> quite soon. My biggest concern is whether Graph Library can help me to 
> find a minimum spanning tree in an *directed* graph with weighted 
> edges. I know that for undirected graphs I can use either the 
> Kruskal's algorithm or the Prim's algorithm, that Graph Library 
> already provides. But what if I need to work with directed graphs?

We don't have any implementations of directed minimum spanning tree 
algorithms. A quick Google search came up with several references, but 
they would need to be implemented for the BGL. If you happen to 
implement one, we'll be glad to help and would love to integrate it in 
the BGL. You are not the first person who has asked for such an 
algorithm.

>
> Please note (in case it helps): The problem that I am trying to solve 
> does not require the use of weighted edges actually, I only need to 
> enforce some constrains, giving absolute priority to some (directed) 
> edges. I could just as well use Boolean flags instead of weights.

This may simplify things, but I'm not sure.

        Doug