boost/graph/prim_minimum_spanning_tree doesn't handle complete graph well

[Li.Long@…]

prim_minimum_spanning_tree handles "undirected" graph. But when you have a complete graph w/ positive weights, and you specify each edge twice, instead of once, the return results are different. An example is attached. Compile with:

g++ -DSPECIFY_ONCE -I...where-boost-is-installed... mstree_prim.cpp

gives correct answer, while

g++ -I...where-boost-is-installed... mstree_prim.cpp

gives incorrect answer (two spanning trees).

[Jeremiah Willcock]

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]

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]

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]

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.

[Li Long <Li.Long@…>]

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]

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@…]

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.

[Jeremiah Willcock]

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.