igraph-help
[Top][All Lists]

## Re: [igraph] user defined geodesics

 From: John Lapeyre Subject: Re: [igraph] user defined geodesics Date: Thu, 11 Feb 2010 22:13:21 +0100 User-agent: KMail/1.12.4 (Linux/2.6.31.9; KDE/4.3.4; x86_64; ; )

```Hi,

Thankyou for the detailed reply!

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

Yes, that makes sense.

>> I find I can gain a few percent in efficiency by iterating over blocks of
>> vertices.
Here are some results: using igraph_average_path_length vs the
code in my previous post, with all weights=1.

For blocksize=1, I used igraph_vs_1; for all others igraph_vs_seq.
Data set: Prepared by Mark Newman
http://www-personal.umich.edu/~mejn/netdata/cond-mat.zip (but change
weights to 1)
there are 16726 vertices
there are 47594 edges

igraph_average_path_length  17s
blocksize  1000 vs:  119s   ratio 119/17 = 7.0
blocksize   500  vs: 114s   ratio 114/17 = 6.7
blocksize   100  vs: 107s   ratio 107/17 = 6.3
blocksize    50  vs: 107s   ratio 107/17 = 6.3
blocksize    1  vs:  158s   ratio 158/17 = 9.3

It looks like the optimum size is 50 to 100. I don't
have time to look more closely. Maybe its cache-related.
I changed my mind, the complexity is worth using blocks!

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

It looks like I would have to modify igraph_average_path_length, because it
only supports using all the vertices as target vertices. In fact, if I
understand,Dijkstra's algorithm correctly, its not possible to use only a
subset of the
vertices as target vertices. I could not think of one, anyway. If I have ids,
idx > idy > idz
then the geodesic from idy to idz might go through idx.

--John

```

reply via email to