Claudio Martella wrote:
I perfectly understand your decision. I have a question on this issue. I see that the distance_histogram basically calculates all-pairs shortest paths (ASSP) as it returns all the shortest distances. So some sort of ASSP is already implemented. Is it possible to access it already? Do you have any workaround suggestion for me?
The distance_histogram() function uses BFS/Dijkstra internally in C++, but unfortunately this is not exposed yet in the python interface. If you want to calculate ASSP now with graph-tool you have basically two options: 1 - Do it in python. This is relatively simple, if you want to do it naively: def dist_from_source(g, source): dist = g.new_vertex_property("int") dist.a = -1 dist[source] = 0 queue = [source] while len(queue) > 0: v = queue[0] del queue[0] for w in v.out_neighbours(): if dist[w] == -1: dist[w] = dist[v] + 1 queue.append(w) return dist If edges are weighted, you can use a priority queue instead. 2 - Call APSP directly form boost, with the inline() function. This is fast. def APSP(g): dists = g.new_vertex_property("vector<int>") for v in g.vertices(): dists[v] = [0]*g.num_vertices() weights = g.new_edge_property("int") weights.a = 1 inline("""floyd_warshall_all_pairs_shortest_paths(g, dists, weight_map(weights));""", ["g", "dists", "weights"], support_code="#include <boost/graph/floyd_warshall_shortest.hpp>") return dists Yes, you can do that. :-) I hope this helps. Cheers, Tiago