[Boost-users] Buggy Prim's minimum spanning tree example

From: Olivier Delalleau (delallea_at_[hidden])
Date: 2006-02-17 16:28:22

Hello,

I have a problem with the example for Prim's minimum spanning tree that
can be found here:
http://www.boost.org/libs/graph/example/prim-example.cpp

The problem is that when compiled in 32 bits but run on a 64 bits
computer, and modified with different edges and weights, it does not
work anymore.
The modified version that exhibits this behaviour is here:
http://www.iro.umontreal.ca/~delallea/tmp/prim-example-fail.cpp
It is a simplified version (I removed some compiler-specific code for
MSVC) where I replaced the edges and weights by a real-life example I
have to solve.

Here is the output on a 64 bits computer:
-> g++ prim-example-fail.cpp
-> ./a.out
parent[0] = no parent
parent[1] = 9
parent[2] = 19
parent[3] = 4
parent[4] = 0
parent[5] = 26
parent[6] = 27
parent[7] = 4
parent[8] = 0
parent[9] = 3
parent[10] = 0
parent[11] = 0
parent[12] = 6
parent[13] = 12
parent[14] = 17
parent[15] = 28
parent[16] = 4
parent[17] = 15
parent[18] = 1
parent[19] = 24
parent[20] = 12
parent[21] = 10
parent[22] = 5
parent[23] = 1
parent[24] = 22
parent[25] = 0
parent[26] = 4
parent[27] = 7
parent[28] = 13
parent[29] = 4

And when compiled in 32 bits with the -m32 option of g++:
-> g++ -m32 prim-example-fail.cpp
-> ./a.out
parent[0] = no parent
parent[1] = no parent
parent[2] = no parent
parent[3] = no parent
parent[4] = no parent
parent[5] = no parent
parent[6] = no parent
parent[7] = no parent
parent[8] = no parent
parent[9] = no parent
parent[10] = no parent
parent[11] = no parent
parent[12] = no parent
parent[13] = no parent
parent[14] = no parent
parent[15] = no parent
parent[16] = no parent
parent[17] = no parent
parent[18] = no parent
parent[19] = no parent
parent[20] = no parent
parent[21] = no parent
parent[22] = no parent
parent[23] = no parent
parent[24] = no parent
parent[25] = no parent
parent[26] = no parent
parent[27] = no parent
parent[28] = no parent
parent[29] = no parent

I don't know if the problems comes from a faulty example or from the
Boost Prim's spanning tree algorithm. Unfortunately I find the graph
library quite difficult to understand and this example is the only basis
I have to work from.

Thanks for any help,

Olivier