Retrieving distances from shortest_distance

graph-tool
1

Hi and happy new year graph coders!

The shortest_distance function implements the Floyd's algorithm. I am
carefully following the example provided by the docs
<https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.shortest_distance&gt;
but the function doesn't return the expected result.

Here is my trivial try:

# -------------------
import graph_tool as gt
from graph_tool.topology import shortest_distance
import numpy as np

wedges=[(2, 0, 6.0), (0, 3, 7.0), (0, 2, 2.0)]
print(wedges)

# Définition of the weighted graph
g= gt.Graph(directed=True)
weight = g.new_edge_property("double")
g.add_edge_list(np.array(wedges), eprops=[weight])

# Floyd call
dist=shortest_distance(g, dense=True)

# I'm expecting the vector distance from vertex 2
print(dist[g.vertex(2)])

# -------------------

outputting :

# -------------------
[(2, 0, 6.0), (0, 3, 7.0), (0, 2, 2.0)]
array([ 1, 2147483647, 0, 2], dtype=int32)
# -------------------

This not the correct distance vector from the 2-indexed node nor the correct
predecessor vector. And I don't understand why I get an int32 vector since
the weights have double type.

Can somebody please correct my code in order to get the correct distances?

Pascal

2

You need to actually pass the weights to the function:

    dist = shortest_distance(g, weights=weight, dense=True)

Best,
Tiago

3

Thanks for your answer, now, i get the correct distances, nice!

I was benchmarking some Floyd APSP source-code.

Some results (in seconds) on a random graph with 800 nodes and abouts 10000
edges:

Networkx : 82.66
Python with array : 38.97
Numpy from Networkx : 1.67 (no predecessors calculation)
graph-tool : 0.91
Scipy (Cython) : 0.50
Pure C code : 0.35

Below the code I used for Graph-tool test:

# -------------------
import graph_tool as gt
from graph_tool.topology import shortest_distance
import numpy as np
from random import randrange

def random_edges(n, density, max_weight=100):
    M=n*(n-1)//2
    m=int(density*M)
    edges=set()
    wedges=[]
    while len(edges)<m:
        L=(randrange(n),randrange(n))
        if L[0]!=L[1] and L not in edges:
            w=float(randrange(max_weight))
            wedges.append(L+(w,))
            edges.add(L)
    return wedges

n=800
density=0.33

wedges=random_edges(n, density)

start=clock()

g= gt.Graph(directed=True)
weight = g.new_edge_property("double")
g.add_edge_list(np.array(wedges), eprops=[weight])
dist = shortest_distance(g, weights=weight, dense=True)

end=clock()
print("graph-tool \t: %.2f" %(end-start))
# -------------------

4

Hi TiagoI'm curious about Graph Tool performance. Does the method implement
*parallel* Floyd algorithm? Are multicore automatically detected?Thanks for
your answerPascal

attachment.html (447 Bytes)

5

No, Floyd-Warshall is implemented serially.