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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list graph-tool@forked.de http://lists.forked.de/mailman/listinfo/graph-tool
