[igraph] All Pairs Shortest Path Problem

[s1520964]

Hi,

I am working with python-igraph and I need to compute graph (graph is  
disconnected and weighted) measures 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 is faster.

Are there possibilities to get the apsp (all-pairs-shortest-path)  
matrix as a (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?


Kind regards,
Jan Eberhardt