Warriors_Cats's blog

Dinic's algorithm for max flow using dynamic trees
By Warriors_Cats, history, 4 years ago, In English

Hello, everyone! Can someone explain me how to merely implement Dinic's algorithm for maximum flow using the linear logarithmic behaviour provided by dynamic trees such as link/cut trees described by Tarjan and Sleator. Despite the fact that I have seeked for the so called O(VElogV) version of Dinic's algorithm, however I didn't manage to find any appropriate implementation for it. Here are some suggestive articles I have recently found: https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cc.gatech.edu/~rpeng/18434_S15/blockingFlows.pdf&ved=2ahUKEwiDi676jK_rAhUPxosKHX3YAyMQFjABegQIARAB&usg=AOvVaw3AI1kk_L7dXi9oF8yheGsd and https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.arl.wustl.edu/~jst/cse/542/text/sec19.pdf&ved=2ahUKEwiFobDfia_rAhVN_CoKHYIrC-YQFjAAegQIAhAB&usg=AOvVaw30d3vyyxayE8XX1bZsEFZq. Thanks a lot in advance for any suggestion or link!

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +14 Vote: I do not like it

I have a related question, maybe someone has looked into it. How much (if at all) faster is this dynamic tree Dinic faster than regular Dinic, on reasonably sized (not necessarily "nice") inputs? Dinic is famous for its $$$O(V^2 E)$$$ upper bound not meaning much.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Even though the running time for reasonably sized inputs doesn't differ that much between these two versions of Dinic, I am more interested to see how link/cut tree data structure is actually involved into the process of tracing blocking flows.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    Not much faster: dynamic trees need height about >500 to get performance gains.

    Issue with blocking flow based algorithms is there are data that breaks all of them. Push-relabel type algorithms also have such adversarial cases, but the performance differences aren't as big.

    If you want a really fast code, hipr is the best that I know of. It used to be at http://www.avglab.com/andrew/soft.html, but that seems down at the moment. You can pull it out of this wrapper for clique-dense subgraph detection (main is densest.cpp). The code is very robust, and seems to take under a second for any graphs with < 10^6 edges that I've thrown at it.

    On the other hand, the main code file hi_pr.c is 900+ lines, so not exactly the easiest to incorporate into a header/template. So as added incentive, I'll mail a cookie to anyone who successfully uses it in a CF Global Round for a problem that's not supposed to be solved by flow (something like the max-flow solution to IOI`13 E Robots)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you're looking for a fast PR implementation that's more suited for CP: There is this short one from KACTL. Additionally, my personal codebook contains PR codes for various problems such as bipartite matching or min-cost-max-flow. These should be as fast as hi_pr.c while being much easier to use.

      With regards to worst case inputs: For directed graphs, there is the infamous ak.c generator on which PR needs quadratic time (around 3 seconds for $$$|V|=40'000$$$, $$$|E|=60'000$$$ with my code on my machine).

      ak.c
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can confirm that it takes noticeable time for 10,000, and the 10x bigger version takes about 1.5 minutes.

        Wow this changes a lot of things: we gave up benchmarking more recent numerical based algorithms for mincost flows mostly because how fast HIPR was... maybe time to revisit that instead.

        → Reply