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