igraph-help
[Top][All Lists]

[igraph] user defined geodesics

 From: John Lapeyre Subject: [igraph] user defined geodesics Date: Sat, 6 Feb 2010 14:40:54 +0100 User-agent: KMail/1.12.4 (Linux/2.6.32.5; KDE/4.3.4; x86_64; ; )

Hello,

Does someone have advice on user *efficient* defined geodesics? For example
I want to compute an average geodesic with a different definition,

(1/d_av^-1) = C \sum (1/d_ij)

ie the inverse of average geodesic is proportional to the
sum of the inverses of the geodesics. Or an example would
be average geodesic with edge weights.

Below is an example of a way to do this, but it is orders of magnitude
slower than igraph_average_path_length. Note that I use igraph_vs_1 as an
interator:
I find I can gain a few percent in efficiency by iterating over blocks of
vertices. But I dont think its worth the code complexity. This is more or less
what is called Johnsons algorithm, except I assume  all weights w satisfy
0 <= w <= 1, so i immediately use dijkstra's algorithm.

Average of geodesics with edge weights:
-----
igraph_vector_t weights;
igraph_matrix_t shortest_paths;
igraph_vs_t source_vertices;

nv = igraph_vcount(graph);

for(i=0;i<nv;i++) { // loop over source vertices
igraph_vs_1(&source_vertices,i); // set iterator to the single vtx with
ind i
// find shortest paths to all vertices from vertex i
igraph_shortest_paths_dijkstra(graph, &shortest_paths, source_vertices,
&weights, IGRAPH_ALL );
for(j=0;j<nv;j++) { // loop over all target vertices
path_length =  MATRIX(shortest_paths,0,j); // only one row (row 0) in
matrix
if (path_length >= HUGE_VAL or isnan(path_length) )
path_length = nv; // longest possible path is nv (assume weights <= 1)
sum += path_length;
}
}
-----

I looked at the internal routines, but currently don't understand the code.
(its undocumented, but I could figure it out with some work)
I wonder if my problem  is more algorithmic or due to the implementation.

Thanks,
John