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@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs