I'm happy to announce version 2.0.0 from graph-tool!

What is new?

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