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 more information. If your graph comes from Python, then you have to be 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 _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
