Johnsons BGL implementation for undirected graphs correct?
When I use the BGL johnsons_all_pairs_shortest_paths example (source
below)on an undirected graph, some results are quite wrong.
For example, the output shows that the distance between node 1 and 6
equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26.
Is there something wrong with me or is the BGL implementation incorrect?
Any ideas?
Jan de Ruiter
//Output
0 1 2 3 4 5 6 7 8 9
0 0 99 111 123 103 107 135 105 111 123
1 -99 0 12 24 4 8 36 6 12 24
2 -111 -12 0 12 -8 -4 24 -6 0 12
3 -123 -24 -12 0 -20 -16 12 -18 -12 0
4 -103 -4 8 20 0 4 32 2 8 20
5 -107 -8 4 16 -4 0 28 -2 4 16
6 -135 -36 -24 -12 -32 -28 0 -30 -24 -12
7 -105 -6 6 18 -2 2 30 0 6 18
8 -111 -12 0 12 -8 -4 24 -6 0 12
9 -123 -24 -12 0 -20 -16 12 -18 -12 0
-------------------------------------------------------------------------
//Source
#include
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Jan, as far as I can see the distance between node 9 and node 6 equals 12 and not 2 as you are assuming. So the result is 4+4+4+12+12 = 36 which is perfectly correct. Michael On Monday 22 July 2002 10:30, Jan de Ruiter wrote:
When I use the BGL johnsons_all_pairs_shortest_paths example (source below)on an undirected graph, some results are quite wrong. For example, the output shows that the distance between node 1 and 6 equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26. Is there something wrong with me or is the BGL implementation incorrect? Any ideas?
Jan de Ruiter
//Output 0 1 2 3 4 5 6 7 8 9 0 0 99 111 123 103 107 135 105 111 123 1 -99 0 12 24 4 8 36 6 12 24 2 -111 -12 0 12 -8 -4 24 -6 0 12 3 -123 -24 -12 0 -20 -16 12 -18 -12 0 4 -103 -4 8 20 0 4 32 2 8 20 5 -107 -8 4 16 -4 0 28 -2 4 16 6 -135 -36 -24 -12 -32 -28 0 -30 -24 -12 7 -105 -6 6 18 -2 2 30 0 6 18 8 -111 -12 0 12 -8 -4 24 -6 0 12 9 -123 -24 -12 0 -20 -16 12 -18 -12 0
[snipped] - -- Dipl.-Ing. Michael Kettner, Wissenschaftlicher Mitarbeiter Institut für Verkehrswesen, Eisenbahnbau und -betrieb, Universitaet Hannover Appelstr. 9A # Tel: ++49/(0)511/762-4273 D-30167 Hannover # Fax: ++49/(0)511/762-3001 http://www.ive.uni-hannover.de # kettner@ive.uni-hannover.de -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE9PRvxkCdGnb0kVFMRAow7AJ0ejHg2pTtFMeFlz0vVvDhNN/e4ugCcD82W iDetBOFHzpvFnTRRFnWoffY= =QKvH -----END PGP SIGNATURE-----
Michael Kettner wrote:
Hi Jan,
as far as I can see the distance between node 9 and node 6 equals 12 and not 2 as you are assuming. So the result is 4+4+4+12+12 = 36 which is perfectly correct.
Michael
Hello Michael, I don't think so. Look again at the source code and you'll see that Edge(6,9) has a corresponding weight of 2. Jan de Ruiter
Hi Jan, On Mon, 22 Jul 2002, Jan de Ruiter wrote: yg-boo> When I use the BGL johnsons_all_pairs_shortest_paths example (source yg-boo> below)on an undirected graph, some results are quite wrong. yg-boo> For example, the output shows that the distance between node 1 and 6 yg-boo> equals 36. The SP however (1-4-5-8-9-6) = 4+4+4+12+2 = 26. yg-boo> Is there something wrong with me or is the BGL implementation incorrect? yg-boo> Any ideas? Yes, that is a bug in the algorithm. Thanks for bringing this to my attention. I've checked a new version with the fix into CVS. I've done a little testing, but if you wouldn't mind checking it out and also verifying that it works, I would thankful. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
Hello Jeremy, Thanks for fixing the bug. I did test your new version of Johnson's SP with my original network (121 nodes and 220 edges) and the results are 100% OK. Great library, great support! mvg Jan de Ruiter Jeremy Siek wrote:
Yes, that is a bug in the algorithm. Thanks for bringing this to my attention. I've checked a new version with the fix into CVS. I've done a little testing, but if you wouldn't mind checking it out and also verifying that it works, I would thankful.
Cheers, Jeremy
---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
participants (4)
-
jan de ruiter -
Jan de Ruiter
-
Jeremy Siek -
Michael Kettner