Restructure flow algorithms

[Chillee]

Restructure flow algorithms

[simonlindholm]

EdmondsKarp: Runs in O(VE^2) time. Strictly inferior to Dinic's in runtime. Fairly short.

Yeah, the only reason this exists is code size. I've seen people at KTH use quite a lot. Not sure we should remove it if everything else is longer, though its slowness does scare me a bit every time I use it.

Add Dinic's. This gives us a bunch of nice provable guarantees on certain kinds of graphs, a much more understandable/traditional augmenting-paths flow algorithm, with even stronger guarantees if scaling is added.

I think we should probably do this, though it's annoying that it doesn't actually help in practice... (until it does, I guess.) Does "(my guess is about 3x faster?)" refer to comparison with Dinic's? Can we speed the Dinic's up? How does code size compare?

Also remove DFSMatching since I think it's pretty useless.

We shouldn't:

• it's short
• it's easier to use than general flow algorithms
• it's sufficed for most matching problems that I've encountered
• the particular way in which it creates a matching can be exploited, either for incremental matching (#33, https://code.google.com/codejam/contest/6314486/dashboard#s=p0 ), or for max-weight matching where w[i, j] = W[i] for all edges (i, j) (sort by decreasing W, do matching in that order).

Add global relabeling to the current HLPP implementation. This will give us the fastest possible flow implementation in general.

I skipped this before because it didn't make a big difference in my tests (maybe I got the heuristic wrong, or I my test cases were bad, I don't remember any details), and it added quite a bit of code size (while the gap heuristic only added 4 lines). But we could consider it...

The linked discussion is interesting, I certainly need to check out dacin21's mentioned bug with isolated source node...

[Chillee]

I skipped this before because it didn't make a big difference in my tests (maybe I got the heuristic wrong, or I my test cases were bad, I don't remember any details), and it added quite a bit of code size (while the gap heuristic only added 4 lines). But we could consider it...

Perhaps... I'll try and benchmark it.

Yeah, the only reason this exists is code size. I've seen people at KTH use quite a lot. Not sure we should remove it if everything else is longer, though its slowness does scare me a bit every time I use it.

I think Dinic's can be written in not significantly more code. I suspect people gravitate towards this one because the next step up is 15 lines and double the number of characters.

Also remove DFSMatching since I think it's pretty useless.

I suppose that's fair... perhaps we could write about how it can be extended to those problems you mentioned?

[simonlindholm]

I suppose that's fair... perhaps we could write about how it can be extended to those problems you mentioned?

We should probably do something about incremental matching (see linked issue), but for the sort-then-match-in-that-order technique I don't think that warrants mention in the description, since it doesn't require modification of the code, just the caller. (And there isn't space to KACTL teach you everything there is to know about matching/flow.)