Sorting's blog

Recovering edge flow from Push-relabel
By Sorting, history, 18 months ago, In English

Is it possible to recover the flow for each edge after running the Push-relabel algorithm on a graph?

It seems like some inside cycles of flow can exist after running the algorithm.

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

»
18 months ago, # |
  Vote: I like it +36 Vote: I do not like it

There is some optimization for the push-relabel algorithm which only guarantees the answer to be preflow, not actual flows. To recover the solution, you should run flow decomposition or just get rid of this optimization. I think flow decomposition can be slow, so you should just generally don't have this optimization.

Here is the implementation without that optimization.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    I was just reading through the implementation, and read a comment in it that said basic_string is bad for this specific use-case. Any idea why that might be the case (I've never faced any issue with using basic_string for graphs — weighted or unweighted)?

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

      Well, it did something unbelievable, but I don't remember what it was. I think you can look up for C++ documentation to guess what it is.

      → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    What's the complexity without the optimization? I'm thinking of just using Dinic instead.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Complexity remains same: $$$O(V^2 \sqrt E)$$$. Even without the optimization, HLPP is still fast enough empirically.

      → Reply