Блог пользователя Sorting

Recovering edge flow from Push-relabel
Автор Sorting, история, 22 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    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)?

    → Ответить
    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      → Ответить