Custom Query (545 matches)

The bfs and dfs processedMap() and reachedMap() functions set wrong member variable.

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.

I run the configure scripts using Intel C++ compiler version 10.1 like this:

./configure --enable-demo --enable-benchmark CXX=/usr/local/intel/cc/10.1/bin/icpc

The scripts sets CXXFLAGS in a wrong way as it sets all the GCC specific -Wxyz flags are also set. The correct setting should probably be

CXXFLAGS=-g -O2

This bug exists in [bb40b6db0a58].