Comments (3)
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...
from kactl.
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?
from kactl.
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.)
from kactl.
Related Issues (20)
- In whole Geometry section, there are no epsilon. HOT 1
- Interpolation Template
- Add finite state automaton to KMP
- Add wavelet tree HOT 2
- Replace Manacher with Eertree?
- Add Half-plane intersection? HOT 2
- General Matching has unnecessary factor of 8
- Can we have Lyndon Factorization
- Faster hashmap
- Make string hashing ARM-friendly HOT 1
- Beginner-friendliness of Lazy Segment Tree
- Wrong Time Complexity for MinCostMaxFlow HOT 1
- dead link in mod mul
- Lazy segment tree is difficult to modify for other operations HOT 3
- Simplification of "rotate" implementation for splay HOT 1
- make euler walk return edge indexes by default HOT 1
- Factor.h can be hacked HOT 3
- Typedef is outdated
- outdated comment
- run tests with runtime debug flags HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kactl.