Changeset 2340:03c71d754990 in lemon-0.x for lemon/hao_orlin.h

Timestamp:

01/11/07 22:22:39 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3132

Message:

Make Hao-Orlin epsilon-safe

File:

• lemon/hao_orlin.h (modified) (21 diffs)

lemon/hao_orlin.h

@@ -20 +20 @@
 #define LEMON_HAO_ORLIN_H
 
+#include <cassert>
+ 
+
+
 #include <vector>
 #include <queue>
+#include <list>
 #include <limits>
 
@@ -28 +33 @@
 #include <lemon/graph_adaptor.h>
 #include <lemon/iterable_maps.h>
- 
 
 /// \file
@@ -109 +113 @@
     OutResGraph* _out_res_graph;
 
-    typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
-    OutCurrentEdgeMap* _out_current_edge;  
-
     typedef RevGraphAdaptor<const Graph> RevGraph;
     RevGraph* _rev_graph;
@@ -120 +121 @@
     
     InResGraph* _in_res_graph;
-
-    typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
-    InCurrentEdgeMap* _in_current_edge;  
-
 
     typedef IterableBoolMap<Graph, Node> WakeMap;
@@ -162 +159 @@
       _graph(&graph), _capacity(&capacity), 
       _preflow(0), _source(), _target(), 
-      _out_res_graph(0), _out_current_edge(0),
-      _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
+      _out_res_graph(0), _rev_graph(0), _in_res_graph(0),
       _wake(0),_dist(0), _excess(0), _source_set(0), 
       _highest_active(), _active_nodes(), _dormant_max(), _dormant(), 
@@ -172 +168 @@
         delete _min_cut_map;
       } 
-      if (_in_current_edge) {
-        delete _in_current_edge;
-      }
       if (_in_res_graph) {
         delete _in_res_graph;
@@ -181 +174 @@
         delete _rev_graph;
       }
-      if (_out_current_edge) {
-        delete _out_current_edge;
-      }
       if (_out_res_graph) {
         delete _out_res_graph;
@@ -206 +196 @@
   private:
     
-    template <typename ResGraph, typename EdgeMap>
-    void findMinCut(const Node& target, bool out, 
-                    ResGraph& res_graph, EdgeMap& current_edge) {
+    template <typename ResGraph>
+    void findMinCut(const Node& target, bool out, ResGraph& res_graph) {
+      typedef typename Graph::Node Node;
       typedef typename ResGraph::Edge ResEdge;
       typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
@@ -220 +210 @@
         (*_excess)[it] = 0;
         (*_source_set)[it] = false;
-
-        res_graph.firstOut(current_edge[it], it);
-      }
+      }
+
+      _dormant[0].push_front(_source);
+      (*_source_set)[_source] = true;
+      _dormant_max = 0;
+      (*_wake)[_source] = false;
+
+      _level_size[0] = 1;
+      _level_size[1] = _node_num - 1;
 
       _target = target;
@@ -229 +225 @@
       for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
         Value delta = res_graph.rescap(it);
-        if (!_tolerance.positive(delta)) continue;
-        
-        (*_excess)[res_graph.source(it)] -= delta;
+        (*_excess)[_source] -= delta;
         res_graph.augment(it, delta);
         Node a = res_graph.target(it);
-        if (!_tolerance.positive((*_excess)[a]) && 
-            (*_wake)[a] && a != _target) {
+        if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
           _active_nodes[(*_dist)[a]].push_front(a);
           if (_highest_active < (*_dist)[a]) {
@@ -244 +237 @@
       }
 
-      _dormant[0].push_front(_source);
-      (*_source_set)[_source] = true;
-      _dormant_max = 0;
-      (*_wake)[_source] = false;
-
-      _level_size[0] = 1;
-      _level_size[1] = _node_num - 1;
 
       do {
         Node n;
         while ((n = findActiveNode()) != INVALID) {
-          ResEdge e;
-          while (_tolerance.positive((*_excess)[n]) && 
-                 (e = findAdmissibleEdge(n, res_graph, current_edge)) 
-                 != INVALID){
-            Value delta;
-            if ((*_excess)[n] < res_graph.rescap(e)) {
+          for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
+            Node a = res_graph.target(e);
+            if ((*_dist)[a] >= (*_dist)[n] || !(*_wake)[a]) continue;
+            Value delta = res_graph.rescap(e);
+            if (_tolerance.positive((*_excess)[n] - delta)) {
+              (*_excess)[n] -= delta;
+            } else {
               delta = (*_excess)[n];
-            } else {
-              delta = res_graph.rescap(e);
-              res_graph.nextOut(current_edge[n]);
+              (*_excess)[n] = 0;
             }
-            if (!_tolerance.positive(delta)) continue;
             res_graph.augment(e, delta);
-            (*_excess)[res_graph.source(e)] -= delta;
-            Node a = res_graph.target(e);
-            if (!_tolerance.positive((*_excess)[a]) && a != _target) {
+            if ((*_excess)[a] == 0 && a != _target) {
               _active_nodes[(*_dist)[a]].push_front(a);
             }
             (*_excess)[a] += delta;
+            if ((*_excess)[n] == 0) break;
           }
-          if (_tolerance.positive((*_excess)[n])) {
-            relabel(n, res_graph, current_edge);
+          if ((*_excess)[n] != 0) {
+            relabel(n, res_graph);
           }
         }
@@ -298 +281 @@
     }
 
-    template <typename ResGraph, typename EdgeMap>
-    void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
+    template <typename ResGraph>
+    void relabel(const Node& n, ResGraph& res_graph) {
       typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
 
@@ -312 +295 @@
           }
         }
-        --_highest_active;
+        --_highest_active;
       } else {  
         int new_dist = _node_num;
@@ -332 +315 @@
           _active_nodes[_highest_active].push_front(n);
           ++_level_size[(*_dist)[n]];
-          res_graph.firstOut(current_edge[n], n);
         }
       }
@@ -373 +355 @@
       if (wake_was_empty){
         for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
-          if (_tolerance.positive((*_excess)[it])) {
-            if ((*_wake)[it] && it != _target) {
-              _active_nodes[(*_dist)[it]].push_front(it);
-            }
-            if (_highest_active < (*_dist)[it]) {
-              _highest_active = (*_dist)[it];               
+          if ((*_excess)[it] != 0 && it != _target) {
+            _active_nodes[(*_dist)[it]].push_front(it);
+            if (_highest_active < (*_dist)[it]) {
+              _highest_active = (*_dist)[it];               
             }
           }
@@ -384 +364 @@
       }
 
-      for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
-        if (!(*_source_set)[res_graph.target(e)]) {
-          Value delta = res_graph.rescap(e);
-          if (!_tolerance.positive(delta)) continue;
-          res_graph.augment(e, delta);
-          (*_excess)[res_graph.source(e)] -= delta;
-          Node a = res_graph.target(e);
-          if (!_tolerance.positive((*_excess)[a]) && 
-              (*_wake)[a] && a != _target) {
-            _active_nodes[(*_dist)[a]].push_front(a);
-            if (_highest_active < (*_dist)[a]) {
-              _highest_active = (*_dist)[a];
-            }
+      Node n = old_target;
+      for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e){
+        Node a = res_graph.target(e);
+        if (!(*_wake)[a]) continue;
+        Value delta = res_graph.rescap(e);
+        res_graph.augment(e, delta);
+        (*_excess)[n] -= delta;
+        if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
+          _active_nodes[(*_dist)[a]].push_front(a);
+          if (_highest_active < (*_dist)[a]) {
+            _highest_active = (*_dist)[a];
           }
-          (*_excess)[a] += delta;
-        }
+        }
+        (*_excess)[a] += delta;
       }
       
       return true;
     }
-    
+
     Node findActiveNode() {
       while (_highest_active > 0 && _active_nodes[_highest_active].empty()){ 
@@ -413 +391 @@
         _active_nodes[_highest_active].pop_front();
         return n;
-      } else {
-        return INVALID;
-      }
-    }
-
-    template <typename ResGraph, typename EdgeMap>
-    typename ResGraph::Edge findAdmissibleEdge(const Node& n, 
-                                               ResGraph& res_graph, 
-                                               EdgeMap& current_edge) {
-      typedef typename ResGraph::Edge ResEdge;
-      ResEdge e = current_edge[n];
-      while (e != INVALID && 
-             ((*_dist)[n] <= (*_dist)[res_graph.target(e)] || 
-              !(*_wake)[res_graph.target(e)])) {
-        res_graph.nextOut(e);
-      }
-      if (e != INVALID) {
-        current_edge[n] = e;    
-        return e;
       } else {
         return INVALID;
@@ -513 +472 @@
         _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
       }
-      if (!_out_current_edge) {
-        _out_current_edge = new OutCurrentEdgeMap(*_graph);
-      }
       if (!_rev_graph) {
         _rev_graph = new RevGraph(*_graph);
@@ -521 +477 @@
       if (!_in_res_graph) {
         _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
-      }
-      if (!_in_current_edge) {
-        _in_current_edge = new InCurrentEdgeMap(*_graph);
       }
       if (!_min_cut_map) {
@@ -556 +509 @@
     /// for the push-relabel algorithm.
     void calculateOut(const Node& target) {
-      findMinCut(target, true, *_out_res_graph, *_out_current_edge);
+      findMinCut(target, true, *_out_res_graph);
     }
 
@@ -584 +537 @@
     /// target for the push-relabel algorithm.
     void calculateIn(const Node& target) {
-      findMinCut(target, false, *_in_res_graph, *_in_current_edge);
+      findMinCut(target, false, *_in_res_graph);
     }