[Top][All Lists]

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

[igraph] All Pairs Shortest Path Problem

From: Jan Eberhardt
Subject: [igraph] All Pairs Shortest Path Problem
Date: Tue, 10 Nov 2015 13:36:50 +0000
User-agent: Horde Application Framework 5


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;

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

reply via email to

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