Boost C++ Libraries: Ticket #3257: boost/graph/prim_minimum_spanning_tree doesn't handle complete graph well

attachment set

anonymous — Fri, 10 Jul 2009 10:42:28 GMT

attachment → mstree_prim.cpp

component changed; owner set

Jeremiah Willcock — Fri, 10 Jul 2009 15:02:48 GMT

owner set to Andrew Sutton
component None → graph

Are you using an actual undirected graph (one with undirectedS), or a directed graph with each edge put in twice? If the latter, the algorithm will consider the edges to be completely separate and may not handle that properly. The documentation does not explicitly say what happens with parallel edges, so that might need to be fixed.

anonymous — Fri, 10 Jul 2009 15:11:29 GMT

Replying to jewillco:

Are you using an actual undirected graph (one with undirectedS), or a directed graph with each edge put in twice? If the latter, the algorithm will consider the edges to be completely separate and may not handle that properly. The documentation does not explicitly say what happens with parallel edges, so that might need to be fixed.

In the example in the attached .cpp, it's "undirectedS", when listing edges and their weights, it doesn't handle it well if you have both "(a, b)" and "(b, a)". In these cases, is it smart enough to check if the given info are "consistant" and keep only one copy?

Jeremiah Willcock — Fri, 10 Jul 2009 15:16:10 GMT

You appear to be getting the spanning tree from the parent map, which is the correct way to do it. How can a single vertex appear in more than one tree since it only has one parent?

Jeremiah Willcock — Fri, 10 Jul 2009 15:17:38 GMT

BTW, please add your name and email address to your preferences as stated at https://svn.boost.org/trac/boost/wiki so you get email replies to your comments.

Mon, 13 Jul 2009 09:36:17 GMT

I'm not sure about "spanning tree from the parent map", why is it the "correct way"? The two "spanning trees" do NOT share any vertex in the example.

Jeremiah Willcock — Tue, 04 Aug 2009 16:21:20 GMT

How do you get two separate spanning trees? How do the vertices and edges relate between them? Does either cover the entire input graph?

Li.Long@… — Wed, 05 Aug 2009 08:01:26 GMT

Replying to jewillco:

How do you get two separate spanning trees? How do the vertices and edges relate between them? Does either cover the entire input graph?

The two separate spanning trees do cover the entire input graph, but they cover different edges of the "correct" spanning tree. If you run the examples, it's pretty easy to see. The example input tree contains only 6 nodes, small enough to eye-ball it.

status changed; resolution set

Jeremiah Willcock — Tue, 24 Nov 2009 22:35:59 GMT

status new → closed
resolution → wontfix

I get an output that has a cycle in the parent map. Changing the graph to directedS (leaving in the duplicated edges) works fine. I added a note to the documentation (in r57914) about parallel edges; I do not believe there is an easy way to fix it using the Boost.Graph implementation of Prim's algorithm, so I am closing the bug.