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

[Ralf Gommers]

On Thu, Feb 18, 2021 at 2:12 PM Touqir Sajed <touqir at ualberta.ca> wrote:

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

Thanks for asking Touqir, and apologies for the slow reply. Your benchmarks
look great, so I'm +1 on adding at least one new algorithm. I replied on
the issue in more detail.

Cheers,
Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.python.org/pipermail/scipy-dev/attachments/20210301/1dcdc181/attachment-0001.html>