igraph-help
[Top][All Lists]

## Re: [igraph] All Pairs Shortest Path Problem

 From: Tamas Nepusz Subject: Re: [igraph] All Pairs Shortest Path Problem Date: Wed, 11 Nov 2015 10:08:51 +0100

```Hello Jan,

> Are there possibilities to get the apsp (all-pairs-shortest-path) matrix as
> a (i.e. numpy) array?
No, unfortunately not - if I wanted to do this, I would have to make
the glue code between igraph and Python (i.e. the C source of the
python-igraph module) to be dependent on numpy's C source, and I'd
rather avoid that.

> 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?
The Python interpreter contains a global interpreter lock (GIL) that
prevents multiple threads from running Python code at the same time,
so that's probably not an option either. You could try the
multiprocessing module, which distributes the work between multiple
Python processes, but I doubt that's going to improve things a lot as
there is a certain overhead associated to the usage of multiple
processes (for instance, the graph itself has to be copied to all the
processes).

> I tried to program a python extension module to get the sum of distances
> between all pairs for the unweighted case, by doing:
This is probably your best bet. However, judging from your C code, you
basically need the total number of connected vertex pairs and the
total path length of all the connected vertex pairs. The total number
of connected vertex pairs can be calculated in an easier way by
decomposing the graph into connected components first (using
igraph_decompose(), or Graph.decompose() from Python), and then
summing |V|*(|V|-1)/2 for all the connected components (where |V| is
the number of vertices in the connected component). This might also
make the calculation of the SSSP sum faster because the matrices for
which you have to take the sum also become smaller (if your graph
consists of many connected components of roughly equal size).

> For the weighted case, I dont know how to extract an igraph_vector_t with
> the edge weights from a graph.
It depends on whether your graph was constructed from C or Python. If
you work purely in C, you need to attach an attribute handler first -
this tells igraph how to store the attributes purely using C data
structures. See
http://igraph.org/c/doc/igraph-Attributes.html#idm470944161648 for
aware that the Python interface attaches its own attribute handler to
igraph (to make it possible to use arbitrary Python objects as
attribute values), so the best way is to "call back" to the Python
layer and ask Python to retrieve the attributes. For instance, if you
have a PyObject* that represents your graph, you can use

es = PyObject_GetAttrString(graph, "es");

to get the edge sequence of your graph, then call

PyMapping_GetItemString(vs, "weight")

to get a Python list containing the edge weights (which you then have
to turn to C floats using PyList_GetItem, PyNumber_Float and
PyFloat_AsDouble. I know this is a bit tedious, but this is the only
way to avoid depending on how exactly the Python interface stores the
attributes.

You can take a look at igraphmodule/convert.c in the source code of
the Python interface to get an idea of how the Python interface
converts between Python data structures and their C counterparts; for
instance, it contains a function named
igraphmodule_PyObject_to_vector_t that shows how the Python interface
attempts to convert an arbitrary Python object to an igraph_vector_t:

https://github.com/igraph/python-igraph/blob/master/src/convert.c#L793

All the best,
Tamas

```