igraph-help
[Top][All Lists]

## Re: [igraph] user defined geodesics

 From: Tamas Nepusz Subject: Re: [igraph] user defined geodesics Date: Mon, 8 Feb 2010 12:55:12 +0000

```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

```

reply via email to