Hello there,
I've been using igraph (with python) some months now in my research.
First of all, thank you very much for this great piece of software.
So, right to the point: I have a performance issue and need advise on usage of the library.
I'll detail the scenario below.
Graph properties:
undirected, unweighted
number of vertices: ~1.7 million
number of edges: ~125 million
Operation being performed:
Given two samples of vertices, compute the distance between each pair (the distance is upper bounded to a fixed value, say 120).
size of sample 1 is ~100 k
size of sample 2 is ~1 k
My implementation:
for each of the 100 million pairs:
call get_shortest_paths()
take the min between 120 and the length of the list of edges in the shortest path
The issue:
each call to get_shortest_paths() takes from ~5s to ~30s
I'm clearly wasting efforts because:
- get_shortest_paths() returns the actual path between the two nodes, but I'm only interested in the distance (I need something like "get_shortest_distance")
- get_shortest_paths() processes until it reaches destination node, but since we have an upper bound, I'd suffice to use a "cutoff" value for the distance calculation
So, I'd like to know if (and how) is it possible to perform better.
Felipe