On Thu, Feb 18, 2021 at 2:12 PM Touqir Sajed <touqir@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