[igraph] All Pairs Shortest Path Problem

[Jan Eberhardt]

Hi,

I am working with python-igraph and I need to compute graph measures  
(my graph is disconnected and weighted) that need the sum of the  
distance between all vertices (avoiding inf) (not averaged).

My current approach is to get the whole matrix via m =  
g.shortest_paths(), converting it to numpy (costly) and doing my "own  
computation". This seems faster than doing it all in pure python,  
because the convert to numpy is slow, but the computation afterwards  
is faster.

Are there possibilities to get the apsp (all-pairs-shortest-path)  
matrix as a (i.e. numpy) array?

The other possibility would be to parallelize multiple sssp  
(single-source-shortest-path) runs to get the apsp matrix, is this  
possible from within python?

I tried to program a python extension module to get the sum of  
distances between all pairs for the unweighted case, by doing:

static void sssp_sum(const igraph_t *g, double *sum, long *count) {
    (*sum) = 0.0;
    (*count) = 0;
    igraph_integer_t vc =  igraph_vcount((igraph_t *)g);
    igraph_integer_t ec =  igraph_ecount((igraph_t *)g);
    igraph_matrix_t matrix;
    igraph_matrix_init(&matrix, vc, vc);
    //igraph_shortest_paths(g, &matrix, igraph_vss_all(),  
igraph_vss_all(), IGRAPH_ALL);
    igraph_shortest_paths_dijkstra(g, &matrix, igraph_vss_all(),  
igraph_vss_all(), NULL, IGRAPH_ALL);
    long int i, j;
    igraph_real_t elem;
    for (i=0; i<(long int)vc; i++) { for (j=0; j<(long int)vc; j++) {
       elem = igraph_matrix_e(&matrix, i, j);
       if (0 < elem && elem != IGRAPH_INFINITY) {
            (*count) += 1;
            (*sum) += elem;
            }
       }
    }
    igraph_matrix_destroy(&matrix);
}

For the weighted case, I dont know how to extract an igraph_vector_t  
with the edge weights from a graph.

Is there an explicit c-code example that shows how to exctract an  
weights igraph_vector_t from a graph?

This would help me a lot.

Kind regards,
Jan Eberhardt