[SciPy-Dev] Faster maximum flow algorithm for scipy.sparse.csgraph

[Touqir Sajed]

Dear Scipy developers,

This is a continuation of https://github.com/scipy/scipy/issues/13402 . The
current implementation of scipy.sparse.csgraph uses Edmond's Karp algorithm
which is not quite good in terms of theoretical time complexity but despite
of this, the implementation is optimized enough to outperform several other
superior (theoretical complexity) algorithms as shown here :
https://github.com/scipy/scipy/pull/10566#issuecomment-552615594 . Later I
carried out benchmarks (
https://github.com/scipy/scipy/issues/13402#issuecomment-767909167 )
showing that indeed scipy's Edmond-Karp implementation can be significantly
beaten with optimized implementations. My original concern was
Edmond-Karp's theoretical complexity which limits its performance in some
cases (highly dense graphs).  So, having another algorithm in scipy with a
better theoretical complexity along with proven superior empirical
performance makes sense. Only the algorithms here :
https://github.com/touqir14/MaxFlow have been shown to significantly
outperform scipy's Edmond-Karp. I think it would be good to port one or
several of these implementations into scipy. Having solely cython ports
will probably be easier to maintain. One thing to ponder here is how much
of a complex implementation should we allow if we decide to add new max
flow algorithms to scipy.

Let me know your thoughts.

Cheers,
Touqir
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.python.org/pipermail/scipy-dev/attachments/20210218/ca80be4d/attachment.html>