 # Boost :

From: Andrea Olgiati (andrea.olgiati_at_[hidden])
Date: 2005-06-21 03:09:01

Hi,

The Johnson's SP algorithm as implemented in the BGL does not easily
provide a way to determine whether two vertices are do have a path
between them. I include below a simplified version of the example
provided with the BGL.
Running it I get the output below:
D=0
D=3
D=-4
D=2147483647 <- no path between nodes '1' and '0'
D=0
D=2147483643 <- no path between nodes '1' and '2'
D=-2147483645 <- no path between nodes '2' and '0'
D=-2147483645 <- no path between nodes '2' and '1'
D=0

That is, there isn't one single value that represents lack of
connectivity - one has to pick a value close enough to 'inf' and
discriminate with that.
Shouldn't 'inf' (however represented) describe lack of connectivity?
(To get around this problem, at the moment I run a transitive closure
before JSP and use the result of that to determine whether two vertices
are connected).

Does this make sense or am I missing something?

Thanks,
Andrea

#include <boost/property_map.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <iostream>

int main()
{
using namespace boost;
typedef adjacency_list<vecS, vecS, directedS, no_property,
property< edge_weight_t, int, property< edge_weight2_t, int > > >
Graph;
const int V = 3;
typedef std::pair < int, int >Edge;
Edge edge_array[] =
{ Edge(0, 1), Edge(0, 2) };
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[] = { 3, -4 };
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));

std::cout << " ";
std::cout << std::endl;
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
std::cout << "D[" << i << "][" << j << "]=" << D[i][j] <<
std::endl;
return 0;
}