Wrong mincut in preflow algorithm when a valid preflow is supplied.

[Hoyt Koepke]

First, many thanks for a great bunch of code here. It's well written, cleanly coded, and is really nice to use. Excellent work!

I've run into a bug with using the preflow algorithm for calculating the min cuts of a graph, and I'd be happy to help provide a fix. The problem is that the minCut is wrong when you supply a valid preflow to init() in which some of the edges are saturated. A simple example where this fails is the graph "source -> n1 -> n2 -> sink" with the capacity of (source, n1) = 20, (n1,n2) = 10, (n2, sink) = 20. In this case, if you supply a flow map with (source -> n1) = 20 and the rest 0, call init(flow_map), and startFirstPhase(), it incorrectly associates n1 with the sink.

The reason I would like this functionality is that I have a huge graph in which I repeatedly make changes to the capacities of a small number of edges, then recalculate the cut. I've got a simple algorithm to turn the preflow from the previous run into a valid preflow on the new graph, and this new preflow is likely close to an optimal one for the new graph -- meaning that a number of the edges are saturated.

It seems the problem is that the elevator _level is not initialized properly to account for saturated edges, and startFirstPhase() ignores any saturated edges. To try and fix this problem, I thought one could activate the nodes reachable by saturated edges. The following code added into init(flow_map&), around line 545 in preflow.h, does this:

     for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
       Value rem = (*_capacity)[e] - (*_flow)[e];
       if (_tolerance.positive(rem)) {
         Node u = _graph.target(e);
         if ((*_level)[u] == _level->maxLevel()) continue;
         _flow->set(e, (*_capacity)[e]);
         (*_excess)[u] += rem;
         if (u != _target && !_level->active(u)) {
           _level->activate(u);
         }
       }
// >>>  This part added
       else if(_tolerance.positive((*_capacity)[e])) {
         Node u = _graph.target(e);
         if (u != _target && !_level->active(u)) {
           _level->activate(u);

           OutArcIt first_e(_graph, u);
           if(first_e != INVALID) {

             std::vector<OutArcIt> iter_stack;

             iter_stack.push_back(first_e);

             while(true) {
               const OutArcIt& e = iter_stack.back();
               Node v = _graph.target(e);
               if(v != _target
                  && !_level->active(v)
                  && ((*_capacity)[e] == (*_flow)[e])
                  && _tolerance.positive((*_capacity)[e])) {

                 _level->activate(v);
                 OutArcIt next_e = OutArcIt(_graph, v);
                  if(next_e != INVALID) {
                    iter_stack.push_back(next_e);
                    continue;
                  }
               }

               while( (++iter_stack.back()) == INVALID) {
                 iter_stack.pop_back();
                 if(iter_stack.empty())
                   goto init_next_node;
               }
             }
           }
         }
       }
     init_next_node:;
     }

However, while this successfully fixes all the simple cases, something is still missing in the above code, as this still does not work on more complex graphs. It seems there is something that I don't understand about how the elevator works. What would I be missing here? Is there a quick fix, or is this problem more difficult?

Thanks!

-- Hoyt

P.S. I'm using the development branch from the repository (I think from a few weeks ago).

P.P.S. I tried to post this to lemon-devel, but it didn't apparently go through. Apologies for cross-posting if it did.

[Alpar Juttner]

Thanks for reporting this bug. I'll have a look at it at the weekend.

[Alpar Juttner]

Please have a look at the patch attached​. I hope it fixes the problem.

The problem is that the code was originally written with the assumption that you initialize with a real flow and not preflow.

In case of a flow, there is no active node at all, therefore it's enough to set the activity of the neighbors of the source where we changed the flow value.

On the other hand, if you use init() with a preflow, then any node can be active, thus all of them have to be checked.

Could you please check if this version works correctly with your bigger examples, too?

P.S: I really appreciated your detailed report and the nice example reproducing the error.

P.P.S: I have no idea why you were unable to send email to lemon-devel. You are correctly subscribed and the list server seems up and running.

[Hoyt Koepke]

Ok, got a chance to test this out and put it through the stress tests (1000s of nodes, 100% connected), and it seems to works excellently. Excellent work and thanks!

I'm not sure why I had problems with the mailing list; I will let you know if I have more problems.

[Alpar Juttner]

Bugfix [30d5f950aa5f] has been merged to all affected branches (1.1, 1.2 and main).

Thanks for the cooperation.