Johnsons BGL implementation for undirected graphs correct?

22 Jul 2002


      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;
}