Use sparse matrix in push_relabel

JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs

Other

36 stars 11 forks source link

Use sparse matrix in push_relabel #42

Closed eddieschoute closed 3 years ago

eddieschoute commented 3 years ago

The push_relabel function creates a dense zeros matrix. This is very inefficient for sparse graphs. In my benchmarks, the zeros call took 30 seconds, afterwards it doesn't even show up any more. The total runtime for maximum_flow also improves by a factor 10x.

matbesancon commented 3 years ago

Makes sense yup, thanks for the PR