Hi list, 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? 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. Thanks in advance, Jim Xochellis This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the system manager. This message contains confidential information and is intended only for the individual named. If you are not the named addressee you should not disseminate, distribute or copy this e-mail.
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
participants (2)
-
Dimitris Xochelis
-
Doug Gregor