Benchmark from https://github.com/scipy/scipy/pull/14358

Benchmark

Code

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow
import maxflow
import numpy as np, scipy, timeit, functools
from tabulate import tabulate

def maxflow_dinic(graph):
    solver = maxflow.Solver()
    solver.load_graph(graph, 'dinic')
    solver.solve('dinic', 0, 999)

def maxflow_edmonds_karp(graph):
    solver = maxflow.Solver()
    solver.load_graph(graph, 'edmonds_karp')
    solver.solve('edmonds_karp', 0, 999)

def scipy_edmonds_karp(graph):
    maximum_flow(graph, 0, 999, method='edmonds_karp')

def scipy_dinic(graph):
    maximum_flow(graph, 0, 999, method='dinic')

p_m = u" \u00B1 "
mu = u" \u03BC "
sigma = u" \u03C3 "
results = []
densities = [0.1, 0.3, 0.5, 0.9]
for density in densities:
    result = [density]
    result.append('Dinic')
    A = (scipy.sparse.rand(1000, 1000, density, format='csr')*100).astype(np.uint32)
    t = timeit.Timer(functools.partial(scipy_dinic, A))
    times = t.repeat(5, 1)
    result.append(str(np.mean(times).round(3))   p_m   str(np.std(times).round(3)))

    t = timeit.Timer(functools.partial(maxflow_dinic, A))
    times = t.repeat(5, 1)
    result.append(str(np.mean(times).round(3))   p_m   str(np.std(times).round(3)))
    results.append(result)

    result = [density]
    result.append('Edmonds Karp')
    t = timeit.Timer(functools.partial(scipy_edmonds_karp, A))
    times = t.repeat(5, 1)
    result.append(str(np.mean(times).round(3))   p_m   str(np.std(times).round(3)))

    t = timeit.Timer(functools.partial(maxflow_edmonds_karp, A))
    times = t.repeat(5, 1)
    result.append(str(np.mean(times).round(3))   p_m   str(np.std(times).round(3)))
    results.append(result)

print(tabulate(results, headers=[
    'Density', 'Algorithm',
    mu   p_m   sigma   '  (SciPy)',
    mu   p_m   sigma   ' (MaxFlow)'],
    tablefmt='github'), end="\n\n")

Results

Density	Algorithm	μ ± σ (SciPy)	μ ± σ (MaxFlow)
0.1	Dinic	0.042 ± 0.002	0.015 ± 0.0
0.1	Edmonds Karp	0.057 ± 0.001	0.073 ± 0.0
0.3	Dinic	0.129 ± 0.002	0.066 ± 0.004
0.3	Edmonds Karp	0.201 ± 0.004	0.607 ± 0.003
0.5	Dinic	0.193 ± 0.002	0.096 ± 0.002
0.5	Edmonds Karp	0.43 ± 0.003	1.656 ± 0.002
0.9	Dinic	0.225 ± 0.001	0.099 ± 0.006
0.9	Edmonds Karp	0.977 ± 0.005	3.004 ± 0.036

MaxFlow in the above table refers to https://github.com/touqir14/MaxFlow The code has also been ported from the above repository. The improvement in SciPy ranges from ~1.35x to ~4.34x.

czgdp1807/scipy_dinic_algorithm.md