search

JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs
Other
36 stars 11 forks source link

handling floating point errors #31

Open etiennedeg opened 4 years ago

etiennedeg commented 4 years ago

I don't know how to use Trait. This code should pass the tests for both integers and floats

codecov[bot] commented 4 years ago

Codecov Report

Merging #31 into master will increase coverage by 32.61%. The diff coverage is 100%.

Impacted file tree graph

@@             Coverage Diff             @@
##           master      #31       +/-   ##
===========================================
+ Coverage   65.65%   98.26%   +32.61%     
===========================================
  Files          10       10               
  Lines         428      289      -139     
===========================================
+ Hits          281      284        +3     
+ Misses        147        5      -142
Impacted Files Coverage Δ
src/dinic.jl 100% <100%> (+43.18%) :arrow_up:
src/maximum_flow.jl 78.26% <100%> (+10.07%) :arrow_up:
src/push_relabel.jl 100% <100%> (+55.93%) :arrow_up:
src/mincut.jl 100% <0%> (+7.69%) :arrow_up:
src/multiroute_flow.jl 100% <0%> (+9.52%) :arrow_up:
src/ext_multiroute_flow.jl 100% <0%> (+20%) :arrow_up:
src/kishimoto.jl 100% <0%> (+22.22%) :arrow_up:
src/boykov_kolmogorov.jl 100% <0%> (+31.7%) :arrow_up:
... and 3 more

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 016dfd5...fe2aeff. Read the comment docs.

etiennedeg commented 4 years ago

I also run into an infinite loop with Dinic's algorithm. For other algorithms, this should be fine, I see no comparisons between floats

coveralls commented 4 years ago

Coverage Status

Coverage increased (+34.004%) to 99.659% when pulling 60f2f8a3cd0847b2fa4b617c01d2c85543e46e3d on etienneINSA:floatingPoint into 016dfd5c1b3bb7c77b94dbfd30046bc806832e8f on JuliaGraphs:master.

matbesancon commented 4 years ago

I also run into an infinite loop with Dinic's algorithm.

Did you fix this in this PR or is it still in progress?

etiennedeg commented 4 years ago

I also run into an infinite loop with Dinic's algorithm.

Did you fix this in this PR or is it still in progress?

Yes, this is fixed with the new commit

etiennedeg commented 4 years ago

I forgot the sqrt for the epsilon tolerance. This should be ok, except if we want to adapt the tolerance depending on the norm of the capacity matrix

matbesancon commented 4 years ago

@etienneINSA what's the status on this?

etiennedeg commented 4 years ago

Sorry for the delay, I think this can be merged, if you agree on the fact that we need a separate function to compare the excess against 0