[Top][All Lists]

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

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


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


reply via email to

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