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 <boost/config.hpp> #include <fstream> #include <iostream> #include <vector> #include <iomanip> #include <boost/property_map.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graphviz.hpp> #include <boost/graph/johnson_all_pairs_shortest.hpp> int main() { using namespace boost; typedef adjacency_list<vecS, vecS, undirectedS, no_property, property< edge_weight_t, int, property< edge_weight2_t, int > > > Graph; const int V = 10; typedef std::pair < int, int >Edge; Edge edge_array[] = { Edge(0,1), Edge(1,2), Edge(2,3), Edge(1,4), Edge(2,5), Edge(3,6), Edge(4,5), Edge(5,6), Edge(4,7), Edge(5,8), Edge(6,9), Edge(7,8), Edge(8,9) }; const std::size_t E = sizeof(edge_array) / sizeof(Edge); Graph g(edge_array, edge_array + E, V); property_map < Graph, edge_weight_t >::type w = get(edge_weight, g); int weights[] = { 99, 12, 12, 4, 99, 12, 4, 99, 2, 4, 2, 99, 12 }; int *wp = weights; graph_traits < Graph >::edge_iterator e, e_end; for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) w[*e] = *wp++; std::vector < int >d(V, std::numeric_limits < int >::max()); int D[V][V]; johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0])); std::cout << std::setw(5) <<" "; for (int k = 0; k < 10; ++k) std::cout << std::setw(5) << k ; std::cout << std::endl; for (int i = 0; i < 10; ++i) { std::cout <<std::setw(5) << i ; for (int j = 0; j < 10; ++j) { std::cout << std::setw(5) << D[i][j] ; } std::cout << std::endl; } return 0; }
-----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