I'm happy to announce version 2.0.0 from graph-tool!
What is new?
This sounds like a great news, i wasn't expecting this news so early.
Just one question: i see that most of the most important algorithms
(at least for me) are already there. What about shortest paths
(Dijkstra and Floyd-Warshall i.e.)?
Is it missing in the doc or you plan them for the future?
Congratulations again for your great work.
Claudio
Hi Claudio
Claudio Martella wrote:
This sounds like a great news, i wasn't expecting this news so early.
Just one question: i see that most of the most important algorithms
(at least for me) are already there. What about shortest paths
(Dijkstra and Floyd-Warshall i.e.)?
Is it missing in the doc or you plan them for the future?
Shortest paths is still not there, since I wanted to make it
configurable, with the "visitor" approach from the BGL reflected in
graph-tool. But I decided to make a release without it, otherwise I
will keep indefinitely including things. It is definitely on the
list.
Congratulations again for your great work.
Thanks!
Cheers,
Tiago
Ni!
Great news!
Congratulations, I've been using the devel version for a while and
working with the python module is a joy.
Having now full docstring documentation and examples therein makes
graph-tool very easy to learn. 
ale
Hi Claudio
Claudio Martella wrote:
This sounds like a great news, i wasn't expecting this news so early.
Just one question: i see that most of the most important algorithms
(at least for me) are already there. What about shortest paths
(Dijkstra and Floyd-Warshall i.e.)?
Is it missing in the doc or you plan them for the future?Shortest paths is still not there, since I wanted to make it
configurable, with the "visitor" approach from the BGL reflected in
graph-tool. But I decided to make a release without it, otherwise I
will keep indefinitely including things. It is definitely on the
list.
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?
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