shortest_path_all pairs in Cython through Floyd Warshall

[nathanncohen]

Everything is explained there :

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Component: graph theory

Author: David Coudert

Branch/Commit: 12d4018

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/7676

[embray]

comment:6

According to https://ask.sagemath.org/question/44823/sage-floyd-algorithm-in-cython/ SciPy already includes an implementation of this that is quite fast, and should probably be used over any implementation in Sage.

[vipul79321]

comment:7

If nobody else is currently working on this can I go ahead and implement shortest_path_all pair using Floyd warshall algorithm ?

[dcoudert]

comment:8

The first step is to survey the many algorithms we already have with data structures and specific conditions (e.g., weighted, multi edges, loops, etc.).

[vipul79321]

comment:9

I have surveyed all the algorithm and data structure sage has. All pair shortest path works only for an unweighted graph. Although we can use boost interface for this purpose. But I think sage should have its own implementation of Floyd Warshall algorithmhttps://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm for a weighted graph with positive or negative edge weights(but with no negative cycles).

[dcoudert]

comment:10

I don't think sage should have it's own implementation if the one of Boost is fast enough.
You can give it a try, but I'm not sure you can produce something faster than 'Floyd-Warshall_Boost'.

Note that we already have a (slow) Python implementation 'Floyd-Warshall-Python' for weighted graphs, and a Cython implementation 'Floyd-Warshall-Cython' but for unweighted graphs only.

[vipul79321]

comment:11

Thanks for your helpful suggestion. I will look into it.

[dcoudert]

comment:12

I added the Floyd-Warshall implementation of SciPy. It's working well but it's not as fast as expected. In fact, most of the time is wasted in turning the graph to a Numpy array and then turning the results to required dict of dicts.

sage: D = digraphs.RandomDirectedGNP(30, .33)
sage: for u, v in D.edges(labels=False):
....:     D.set_edge_label(u, v, randrange(100))
sage: %time _ = D.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-Warshall_Boost')
CPU times: user 6.44 ms, sys: 517 µs, total: 6.96 ms
Wall time: 6.56 ms
sage: %time _ = D.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-Warshall_SciPy')
CPU times: user 30.2 ms, sys: 1.85 ms, total: 32 ms
Wall time: 30.6 ms

sage: D = digraphs.RandomDirectedGNP(300, .33)
sage: for u, v in D.edges(labels=False):
....:     D.set_edge_label(u, v, randrange(100))
sage: %time _ = D.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-Warshall_Boost')
CPU times: user 2.73 s, sys: 18.6 ms, total: 2.75 s
Wall time: 2.76 s
sage: %time _ = D.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-Warshall_SciPy')
CPU times: user 1.95 s, sys: 61.6 ms, total: 2.01 s
Wall time: 2.13 s

---

New commits:

12d4018

trac #7676: Floyd-Warshall with SciPy

[dcoudert]

Branch: public/graphs/7676_floyd_scipy

[dcoudert]

Author: David Coudert

[dcoudert]

Commit: 12d4018

[dimpase]

comment:13

So scipy thinks of graphs as matrices, there no special format/backend?

[dcoudert]

comment:14

When you look at the code of scipy (for instance, https://github.com/scipy/scipy/blob/master/scipy/sparse/csgraph/_shortest_path.pyx), the input parameter is always

    csgraph : array, matrix, or sparse matrix, 2 dimensions
        The N x N array of distances representing the input graph.

You can also check method validate_graph in https://github.com/scipy/scipy/blob/master/scipy/sparse/csgraph/_validation.py. It may convert from one matrix format to another.

[dcoudert]

comment:15

So now the question is whether we finalize this ticket or move it to wontfix. Both options are OK for me.

[dimpase]

comment:16

let us merge it

[dimpase]

Reviewer: Dima Pasechnik

[dcoudert]

comment:18

Thanks.

[vbraun]

Changed branch from public/graphs/7676_floyd_scipy to 12d4018