1.1 --- a/lemon/graph_adaptor.h Thu Jan 11 21:20:57 2007 +0000
1.2 +++ b/lemon/graph_adaptor.h Thu Jan 11 21:22:39 2007 +0000
1.3 @@ -1450,7 +1450,7 @@
1.4 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1.5
1.6 bool operator[](const typename Graph::Edge& e) const {
1.7 - return tolerance.less((*flow)[e], (*capacity)[e]);
1.8 + return tolerance.positive((*capacity)[e] - (*flow)[e]);
1.9 }
1.10 };
1.11
1.12 @@ -1473,7 +1473,7 @@
1.13 void setCapacity(const CapacityMap& _capacity) { capacity = &_capacity; }
1.14 void setFlow(const FlowMap& _flow) { flow = &_flow; }
1.15 bool operator[](const typename Graph::Edge& e) const {
1.16 - return tolerance.less(0, Number((*flow)[e]));
1.17 + return tolerance.positive((*flow)[e]);
1.18 }
1.19 };
1.20
2.1 --- a/lemon/hao_orlin.h Thu Jan 11 21:20:57 2007 +0000
2.2 +++ b/lemon/hao_orlin.h Thu Jan 11 21:22:39 2007 +0000
2.3 @@ -19,15 +19,19 @@
2.4 #ifndef LEMON_HAO_ORLIN_H
2.5 #define LEMON_HAO_ORLIN_H
2.6
2.7 +#include <cassert>
2.8 +
2.9 +
2.10 +
2.11 #include <vector>
2.12 #include <queue>
2.13 +#include <list>
2.14 #include <limits>
2.15
2.16 #include <lemon/maps.h>
2.17 #include <lemon/graph_utils.h>
2.18 #include <lemon/graph_adaptor.h>
2.19 #include <lemon/iterable_maps.h>
2.20 -
2.21
2.22 /// \file
2.23 /// \ingroup flowalgs
2.24 @@ -108,9 +112,6 @@
2.25
2.26 OutResGraph* _out_res_graph;
2.27
2.28 - typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
2.29 - OutCurrentEdgeMap* _out_current_edge;
2.30 -
2.31 typedef RevGraphAdaptor<const Graph> RevGraph;
2.32 RevGraph* _rev_graph;
2.33
2.34 @@ -120,10 +121,6 @@
2.35
2.36 InResGraph* _in_res_graph;
2.37
2.38 - typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
2.39 - InCurrentEdgeMap* _in_current_edge;
2.40 -
2.41 -
2.42 typedef IterableBoolMap<Graph, Node> WakeMap;
2.43 WakeMap* _wake;
2.44
2.45 @@ -161,8 +158,7 @@
2.46 const Tolerance& tolerance = Tolerance()) :
2.47 _graph(&graph), _capacity(&capacity),
2.48 _preflow(0), _source(), _target(),
2.49 - _out_res_graph(0), _out_current_edge(0),
2.50 - _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
2.51 + _out_res_graph(0), _rev_graph(0), _in_res_graph(0),
2.52 _wake(0),_dist(0), _excess(0), _source_set(0),
2.53 _highest_active(), _active_nodes(), _dormant_max(), _dormant(),
2.54 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
2.55 @@ -171,18 +167,12 @@
2.56 if (_min_cut_map) {
2.57 delete _min_cut_map;
2.58 }
2.59 - if (_in_current_edge) {
2.60 - delete _in_current_edge;
2.61 - }
2.62 if (_in_res_graph) {
2.63 delete _in_res_graph;
2.64 }
2.65 if (_rev_graph) {
2.66 delete _rev_graph;
2.67 }
2.68 - if (_out_current_edge) {
2.69 - delete _out_current_edge;
2.70 - }
2.71 if (_out_res_graph) {
2.72 delete _out_res_graph;
2.73 }
2.74 @@ -205,9 +195,9 @@
2.75
2.76 private:
2.77
2.78 - template <typename ResGraph, typename EdgeMap>
2.79 - void findMinCut(const Node& target, bool out,
2.80 - ResGraph& res_graph, EdgeMap& current_edge) {
2.81 + template <typename ResGraph>
2.82 + void findMinCut(const Node& target, bool out, ResGraph& res_graph) {
2.83 + typedef typename Graph::Node Node;
2.84 typedef typename ResGraph::Edge ResEdge;
2.85 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
2.86
2.87 @@ -219,28 +209,6 @@
2.88 (*_dist)[it] = 1;
2.89 (*_excess)[it] = 0;
2.90 (*_source_set)[it] = false;
2.91 -
2.92 - res_graph.firstOut(current_edge[it], it);
2.93 - }
2.94 -
2.95 - _target = target;
2.96 - (*_dist)[target] = 0;
2.97 -
2.98 - for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
2.99 - Value delta = res_graph.rescap(it);
2.100 - if (!_tolerance.positive(delta)) continue;
2.101 -
2.102 - (*_excess)[res_graph.source(it)] -= delta;
2.103 - res_graph.augment(it, delta);
2.104 - Node a = res_graph.target(it);
2.105 - if (!_tolerance.positive((*_excess)[a]) &&
2.106 - (*_wake)[a] && a != _target) {
2.107 - _active_nodes[(*_dist)[a]].push_front(a);
2.108 - if (_highest_active < (*_dist)[a]) {
2.109 - _highest_active = (*_dist)[a];
2.110 - }
2.111 - }
2.112 - (*_excess)[a] += delta;
2.113 }
2.114
2.115 _dormant[0].push_front(_source);
2.116 @@ -251,31 +219,46 @@
2.117 _level_size[0] = 1;
2.118 _level_size[1] = _node_num - 1;
2.119
2.120 + _target = target;
2.121 + (*_dist)[target] = 0;
2.122 +
2.123 + for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
2.124 + Value delta = res_graph.rescap(it);
2.125 + (*_excess)[_source] -= delta;
2.126 + res_graph.augment(it, delta);
2.127 + Node a = res_graph.target(it);
2.128 + if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
2.129 + _active_nodes[(*_dist)[a]].push_front(a);
2.130 + if (_highest_active < (*_dist)[a]) {
2.131 + _highest_active = (*_dist)[a];
2.132 + }
2.133 + }
2.134 + (*_excess)[a] += delta;
2.135 + }
2.136 +
2.137 +
2.138 do {
2.139 Node n;
2.140 while ((n = findActiveNode()) != INVALID) {
2.141 - ResEdge e;
2.142 - while (_tolerance.positive((*_excess)[n]) &&
2.143 - (e = findAdmissibleEdge(n, res_graph, current_edge))
2.144 - != INVALID){
2.145 - Value delta;
2.146 - if ((*_excess)[n] < res_graph.rescap(e)) {
2.147 + for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
2.148 + Node a = res_graph.target(e);
2.149 + if ((*_dist)[a] >= (*_dist)[n] || !(*_wake)[a]) continue;
2.150 + Value delta = res_graph.rescap(e);
2.151 + if (_tolerance.positive((*_excess)[n] - delta)) {
2.152 + (*_excess)[n] -= delta;
2.153 + } else {
2.154 delta = (*_excess)[n];
2.155 - } else {
2.156 - delta = res_graph.rescap(e);
2.157 - res_graph.nextOut(current_edge[n]);
2.158 + (*_excess)[n] = 0;
2.159 }
2.160 - if (!_tolerance.positive(delta)) continue;
2.161 res_graph.augment(e, delta);
2.162 - (*_excess)[res_graph.source(e)] -= delta;
2.163 - Node a = res_graph.target(e);
2.164 - if (!_tolerance.positive((*_excess)[a]) && a != _target) {
2.165 + if ((*_excess)[a] == 0 && a != _target) {
2.166 _active_nodes[(*_dist)[a]].push_front(a);
2.167 }
2.168 (*_excess)[a] += delta;
2.169 + if ((*_excess)[n] == 0) break;
2.170 }
2.171 - if (_tolerance.positive((*_excess)[n])) {
2.172 - relabel(n, res_graph, current_edge);
2.173 + if ((*_excess)[n] != 0) {
2.174 + relabel(n, res_graph);
2.175 }
2.176 }
2.177
2.178 @@ -297,8 +280,8 @@
2.179 } while (selectNewSink(res_graph));
2.180 }
2.181
2.182 - template <typename ResGraph, typename EdgeMap>
2.183 - void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
2.184 + template <typename ResGraph>
2.185 + void relabel(const Node& n, ResGraph& res_graph) {
2.186 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
2.187
2.188 int k = (*_dist)[n];
2.189 @@ -311,7 +294,7 @@
2.190 --_level_size[(*_dist)[it]];
2.191 }
2.192 }
2.193 - --_highest_active;
2.194 + --_highest_active;
2.195 } else {
2.196 int new_dist = _node_num;
2.197 for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
2.198 @@ -331,7 +314,6 @@
2.199 _highest_active = (*_dist)[n];
2.200 _active_nodes[_highest_active].push_front(n);
2.201 ++_level_size[(*_dist)[n]];
2.202 - res_graph.firstOut(current_edge[n], n);
2.203 }
2.204 }
2.205 }
2.206 @@ -372,38 +354,34 @@
2.207
2.208 if (wake_was_empty){
2.209 for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
2.210 - if (_tolerance.positive((*_excess)[it])) {
2.211 - if ((*_wake)[it] && it != _target) {
2.212 - _active_nodes[(*_dist)[it]].push_front(it);
2.213 - }
2.214 - if (_highest_active < (*_dist)[it]) {
2.215 - _highest_active = (*_dist)[it];
2.216 + if ((*_excess)[it] != 0 && it != _target) {
2.217 + _active_nodes[(*_dist)[it]].push_front(it);
2.218 + if (_highest_active < (*_dist)[it]) {
2.219 + _highest_active = (*_dist)[it];
2.220 }
2.221 }
2.222 }
2.223 }
2.224
2.225 - for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
2.226 - if (!(*_source_set)[res_graph.target(e)]) {
2.227 - Value delta = res_graph.rescap(e);
2.228 - if (!_tolerance.positive(delta)) continue;
2.229 - res_graph.augment(e, delta);
2.230 - (*_excess)[res_graph.source(e)] -= delta;
2.231 - Node a = res_graph.target(e);
2.232 - if (!_tolerance.positive((*_excess)[a]) &&
2.233 - (*_wake)[a] && a != _target) {
2.234 - _active_nodes[(*_dist)[a]].push_front(a);
2.235 - if (_highest_active < (*_dist)[a]) {
2.236 - _highest_active = (*_dist)[a];
2.237 - }
2.238 + Node n = old_target;
2.239 + for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e){
2.240 + Node a = res_graph.target(e);
2.241 + if (!(*_wake)[a]) continue;
2.242 + Value delta = res_graph.rescap(e);
2.243 + res_graph.augment(e, delta);
2.244 + (*_excess)[n] -= delta;
2.245 + if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
2.246 + _active_nodes[(*_dist)[a]].push_front(a);
2.247 + if (_highest_active < (*_dist)[a]) {
2.248 + _highest_active = (*_dist)[a];
2.249 }
2.250 - (*_excess)[a] += delta;
2.251 - }
2.252 + }
2.253 + (*_excess)[a] += delta;
2.254 }
2.255
2.256 return true;
2.257 }
2.258 -
2.259 +
2.260 Node findActiveNode() {
2.261 while (_highest_active > 0 && _active_nodes[_highest_active].empty()){
2.262 --_highest_active;
2.263 @@ -417,25 +395,6 @@
2.264 }
2.265 }
2.266
2.267 - template <typename ResGraph, typename EdgeMap>
2.268 - typename ResGraph::Edge findAdmissibleEdge(const Node& n,
2.269 - ResGraph& res_graph,
2.270 - EdgeMap& current_edge) {
2.271 - typedef typename ResGraph::Edge ResEdge;
2.272 - ResEdge e = current_edge[n];
2.273 - while (e != INVALID &&
2.274 - ((*_dist)[n] <= (*_dist)[res_graph.target(e)] ||
2.275 - !(*_wake)[res_graph.target(e)])) {
2.276 - res_graph.nextOut(e);
2.277 - }
2.278 - if (e != INVALID) {
2.279 - current_edge[n] = e;
2.280 - return e;
2.281 - } else {
2.282 - return INVALID;
2.283 - }
2.284 - }
2.285 -
2.286 Value cutValue(bool out) {
2.287 Value value = 0;
2.288 if (out) {
2.289 @@ -512,18 +471,12 @@
2.290 if (!_out_res_graph) {
2.291 _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
2.292 }
2.293 - if (!_out_current_edge) {
2.294 - _out_current_edge = new OutCurrentEdgeMap(*_graph);
2.295 - }
2.296 if (!_rev_graph) {
2.297 _rev_graph = new RevGraph(*_graph);
2.298 }
2.299 if (!_in_res_graph) {
2.300 _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
2.301 }
2.302 - if (!_in_current_edge) {
2.303 - _in_current_edge = new InCurrentEdgeMap(*_graph);
2.304 - }
2.305 if (!_min_cut_map) {
2.306 _min_cut_map = new MinCutMap(*_graph);
2.307 }
2.308 @@ -555,7 +508,7 @@
2.309 /// and minimal out-degree). The \c target is the initial target
2.310 /// for the push-relabel algorithm.
2.311 void calculateOut(const Node& target) {
2.312 - findMinCut(target, true, *_out_res_graph, *_out_current_edge);
2.313 + findMinCut(target, true, *_out_res_graph);
2.314 }
2.315
2.316 /// \brief Calculates a minimum cut with \f$ source \f$ on the
2.317 @@ -583,7 +536,7 @@
2.318 /// The \c target is the initial
2.319 /// target for the push-relabel algorithm.
2.320 void calculateIn(const Node& target) {
2.321 - findMinCut(target, false, *_in_res_graph, *_in_current_edge);
2.322 + findMinCut(target, false, *_in_res_graph);
2.323 }
2.324
2.325 /// \brief Runs the algorithm.