Re: [igraph] user defined geodesics

[John Lapeyre]

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