Instantly share code, notes, and snippets.

# czgdp1807/scipy_dinic_algorithm.md

Created August 18, 2022 20:26
Show Gist options
• Save czgdp1807/05c77fcb417bc9e94edfa5a74e9d2f97 to your computer and use it in GitHub Desktop.

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.solve('dinic', 0, 999)

def maxflow_edmonds_karp(graph):
solver = maxflow.Solver()
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)

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