Algorithms for Network Interdiction (flow)

[Azzaare]

Here is the PR discussed in #5. Coverage should be 100%, however some cases are covered by dummy functions. Should be updated during September.

I updated the doc, though it seems to be different from LightGraphs.jl (no build.jl script), so please let me know if I have to do something more about it.

[codecov-io]

Current coverage is 100% (diff: 100%)

Merging #6 into master will not change coverage

@@           master    #6   diff @@
===================================
  Files           4    12     +8   
  Lines          78   167    +89   
  Methods         0     0          
  Messages        0     0          
  Branches        0     0          
===================================
+ Hits           78   167    +89   
  Misses          0     0          
  Partials        0     0          

Powered by Codecov. Last update 5154b11...903179b

[Azzaare]

Correcting coverage sorry ><

[CarloLucibello]

wow, this is huge, great work! Don't worry about the docs, we should use Documeter.jl for this package in the near future

[Azzaare]

Thank you @CarloLucibello. As I said in #5, I still have several algorithms to implement. And I have work for 2-4 more articles of improvement to implement here in LightGraphsExtras, so you will have a lot of PRs in the coming academic year :)

[sbromberger]

@CarloLucibello can you do a technical review? I'll merge as soon as you say it's OK.

[CarloLucibello]

this is really too big for me to review accurately in reasonable time. At a first glance I couldn't detect anything odd, and it seems the guy knows what he is doing :) Given these premises, and unless @jpfairbanks finds the time to give this a look, for me it's OK

[Azzaare]

Just to give an insight on the accuracy of the algorithms.

The one called Multilink-Attack was adapted once in C++ and twice in Julia (in NetworkFlows.jl, that I will not maintain since it is now fully integrated in JuliaGraphs with this PR). Test were done on billion of instances on the three versions and give the same results (on average per size of networks, but still ...). The output was compared with a straightforward MILP for thousands of small instances.

The second one, the BMILP is new work that will be submitted soon and is coherent with the Multilink-Attack (MLA) algorithm. Basically, we can check: MLA Lower Bound <= BMILP lower bound <= BMILP upper bound <= MLA upper bound. That is one of the test in the test file actually. It seems fine for the 10k instances I have tested so far.

Sorry for the long post. Will update the indentation thing in the PR in a minute.

[sbromberger]

I don't want to wait to merge this. Let's go ahead. This is great work, @Azzaare - thanks.

[Azzaare]

I updated the indentation, but it can be merge in my next update on the interdiction module anyway.

Thank you @sbromberger