Re: [igraph] user defined geodesics

[Tamas Nepusz]

Hi,

> Below is an example of a way to do this, but it is orders of magnitude
> slower than igraph_average_path_length.
The reason might be that igraph_average_path_length uses a simple breadth first 
search (as there are no edge weights), which has a complexity of O(|V|*|E|), 
while igraph_shortest_paths_dijkstra (that you will really need because of the 
edge weights) from every vertex as a source is O(|V|*|E| log |E|), where |V| is 
the number of vertices and |E| is the number of edges. So there is an extra 
factor of log|E| in the complexity, and I guess you cannot really do better 
than that. I cannot really see any parts in your code that seem to be highly 
inefficient.

> I find I can gain a few percent in efficiency by iterating over blocks of 
> vertices.
It is reasonable because a call to igraph_shortest_paths_dijkstra starts by 
setting up a "lazy adjacency list" data structure, as adjacency lists are more 
suitable for shortest path calculations in this case than the default igraph 
representation (which is an indexed edge list). This data structure is 
destroyed at the end of igraph_shortest_paths_dijsktra, so it has to be 
re-created when calling it the next time.

You might gain some performance by noting that in case of undirected paths, the 
path from A to B is the same as the path from B to A, so it is enough to 
calculate the shortest paths from a vertex to other vertices having an index 
_larger_ than the vertex itself. However, this won't improve an order of 
magnitude as Dijkstra's algorithm sometimes finds shortest paths to vertices 
not in the target set as well as a "side effect", if those vertices are close 
to the source and the target vertices are not.

-- 
Tamas