[boost] [Boost-bugs] [ boost-Bugs-1567811 ] Johnson All-Pairs needs better "no path" information

From: SourceForge.net (noreply_at_[hidden])
Date: 2006-09-29 11:19:34

Bugs item #1567811, was opened at 2006-09-29 11:19
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1567811&group_id=7586

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: graph
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Douglas Gregor (dgregor)
Assigned to: Douglas Gregor (dgregor)
Summary: Johnson All-Pairs needs better "no path" information

Initial Comment:
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;
}

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=107586&aid=1567811&group_id=7586

-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys -- and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Boost-bugs mailing list
Boost-bugs_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs