Retrieving distances from shortest_distance
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> 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 -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 02.01.19 um 12:40 schrieb elastica:
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?
You need to actually pass the weights to the function: dist = shortest_distance(g, weights=weight, dense=True) Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
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)) # ------------------- -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Hi TiagoI'm curious about Graph Tool performance. Does the method implement *parallel* Floyd algorithm? Are multicore automatically detected?Thanks for your answerPascal -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 04.01.19 um 22:28 schrieb elastica:
Hi Tiago I'm curious about Graph Tool performance. Does the
shortest_distance
method implement *parallel* Floyd algorithm? Are multicore automatically detected? Thanks for your answer Pascal
No, Floyd-Warshall is implemented serially. -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
elastica -
Tiago de Paula Peixoto