[graph-tool] speed of all_neighbours

Howmahgee nhalmagyi at gmail.com
Sun Feb 11 19:41:14 CET 2018

I am new to graphtool but super excited by what I have implemented so far. I
have a question however about the speed of the all_neighbors method.

>From trying it on various machines, it seems that it takes around 0.01s for
v.all_neighbors() where v is an arbitrary vertex. I have tried this on a 4
node graph and a 2M node graph getting the same result. Has anyone else
found the same thing? It seems to me to be particularly slow. Storing a
graph as an adjacency list in a hashtable should have microsecond look up
time, I assumed graph-tool stored the graph in such a way but I haven't yet
come across the place where the architecture it is described.

At any rate, am I doing something wrong or is 0.01s the expected look up

I am trying to build a list of "friends of friends" on a graph of around 2M
nodes 200M edges, so if all_neighbors takes 0.01s, then to get "friends of
friends" takes about 1s for each node....which prohibits traversing the
graph in this way in a reasonable time


Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/

More information about the graph-tool mailing list