Re: [Boost-bugs] [Boost C++ Libraries] #732: Johnson All-Pairs needs better "no path" information

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #732: Johnson All-Pairs needs better "no path" information
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2007-09-13 18:23:26

#732: Johnson All-Pairs needs better "no path" information
----------------------+-----------------------------------------------------
  Reporter:  dgregor  |       Owner:  dgregor 
      Type:  Bugs     |      Status:  assigned
 Milestone:           |   Component:  graph   
   Version:  None     |    Severity:  Problem 
Resolution:  None     |    Keywords:          
----------------------+-----------------------------------------------------
Changes (by dgregor):

  * owner:  doug_gregor => dgregor
  * status:  new => assigned

Old description:

> {{{
> 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][0]=0
> D[0][1]=3
> D[0][2]=-4
> D[1][0]=2147483647  <- no path between nodes '1' and '0'
> D[1][1]=0
> D[1][2]=2147483643  <- no path between nodes '1' and '2'
> D[2][0]=-2147483645 <- no path between nodes '2' and '0'
> D[2][1]=-2147483645 <- no path between nodes '2' and '1'
> D[2][2]=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/adjacency_list.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[0]));
>
>   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;
> }
>
> }}}

New description:

 {{{
 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][0]=0
 D[0][1]=3
 D[0][2]=-4
 D[1][0]=2147483647  <- no path between nodes '1' and '0'
 D[1][1]=0
 D[1][2]=2147483643  <- no path between nodes '1' and '2'
 D[2][0]=-2147483645 <- no path between nodes '2' and '0'
 D[2][1]=-2147483645 <- no path between nodes '2' and '1'
 D[2][2]=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/adjacency_list.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[0]));

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

 }}}

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/732#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.