JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs
Other
36 stars 11 forks source link

Significant improvement to mincost_flow #23

Closed ndinsmore closed 5 years ago

ndinsmore commented 5 years ago

Fixed mincost_flow to have much better performance.. around 10000x faster for cases with 500 nodes. Changed mincost_flow arguments to be more consistent with traditional problems ie. primary demand is for nodal values. edge_demands can be set with keyword argument

Depreciates baseline edge_demand arguments.

Below is the benchmarking I did.

image

codecov[bot] commented 5 years ago

Codecov Report

Merging #23 into master will decrease coverage by 1.33%. The diff coverage is 50%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #23      +/-   ##
==========================================
- Coverage   66.98%   65.65%   -1.34%     
==========================================
  Files          10       10              
  Lines         418      428      +10     
==========================================
+ Hits          280      281       +1     
- Misses        138      147       +9
Impacted Files Coverage Δ
src/mincost.jl 50% <50%> (-15.39%) :arrow_down:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update eff807b...d3b2543. Read the comment docs.

codecov[bot] commented 5 years ago

Codecov Report

Merging #23 into master will decrease coverage by 1.33%. The diff coverage is 50%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #23      +/-   ##
==========================================
- Coverage   66.98%   65.65%   -1.34%     
==========================================
  Files          10       10              
  Lines         418      428      +10     
==========================================
+ Hits          280      281       +1     
- Misses        138      147       +9
Impacted Files Coverage Δ
src/mincost.jl 50% <50%> (-15.39%) :arrow_down:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update eff807b...78c9cb3. Read the comment docs.

coveralls commented 5 years ago

Coverage Status

Coverage decreased (-34.3%) to 65.654% when pulling d3b2543fcf2a47d4b308761313ab7aca3ae6680b on ndinsmore:mincost_flow_fix into eff807b2197fbf665bbb7178624ef4d4f64fb7d7 on JuliaGraphs:master.

ndinsmore commented 5 years ago

Review of the coverage shows that the lines were clearly hit and missed by the sampling. I can add more tests that would torture the function if needed.

matbesancon commented 5 years ago

hi @ndinsmore, thanks for the work and the benchmarks added. Codecov is a bit tricky, if you want to add more tests that would cover more cases of the functions that would be helpful. If this gets too cumbersome we will just not consider the cov information

ndinsmore commented 5 years ago

@matbesancon I think that I have made all the changes that you requested.

matbesancon commented 5 years ago

great, thanks again, I'll review everything tomorrow

matbesancon commented 5 years ago

thanks @ndinsmore!