[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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/; KDE/4.3.4; x86_64; ; )


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

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]