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

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

**[igraph] All Pairs Shortest Path Problem**,
*Jan Eberhardt* **<=**