BGL: why is the prim algorithm only useable for undirected graphs?
Hi all, in the documentation of prim_minimum_spanning_tree is mentioned "... solving the minimum spanning tree problem for an undirected graph with weighted edges ...". In my application I use this graph type (the graph type is bidirectionalS => not directed): typedef adjacency_list<vecS,vecS,bidirectionalS,no_property,property<edge_weight_t,int>
BGraph;
This type modells the VertexListGraph and IncidenceGraph concepts, which are required by the prim function. If I call the prim_minimum_spanning_tree, I get reasonalble results. In literature, I can only find usage of Prims algorithm for undirected graphs, too. But I can see no reason, why it shouldn't work for directed graphs. Can you tell me more? Best regards Stefan Rauch
Hi Stefan, On May 13, 2004, at 7:33 AM, boost@spyderworks.de wrote:
Hi all, in the documentation of prim_minimum_spanning_tree is mentioned "... solving the minimum spanning tree problem for an undirected graph with weighted edges ...". In my application I use this graph type (the graph type is bidirectionalS => not directed):
Oops, that's your problem. bidirectionalS is a directed graph... it is a directed graph that provides access to both in_edges and out_edges, whereas directedS only provides access to out_edges. If you want an undirected graph, use undirectedS. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
boost@spyderworks.de wrote: [snip]
In literature, I can only find usage of Prims algorithm for undirected graphs, too. But I can see no reason, why it shouldn't work for directed graphs. Can you tell me more?
Let G=(V,E) be a connected undirected graph. The object Prim's algorithm creates (minimum spanning tree of G) is a free tree T=(V,E') (which by definition is an undirected connected acyclic graph) where E' is a subset of E. For T to be defined G must be connected which would mean if G was directed it would have to be strongly connected -- which amounts to the graph being undirected. Regards, Robert F. Morse
participants (4)
-
boost＠spyderworks.de -
Jeremy Siek -
Robert F. Morse