1.1 --- a/lemon/hao_orlin.h Fri Sep 29 11:26:29 2006 +0000
1.2 +++ b/lemon/hao_orlin.h Fri Sep 29 11:36:30 2006 +0000
1.3 @@ -1,7 +1,9 @@
1.4 /* -*- C++ -*-
1.5 - * lemon/hao_orlin.h - Part of LEMON, a generic C++ optimization library
1.6 *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * This file is a part of LEMON, a generic C++ optimization library
1.9 + *
1.10 + * Copyright (C) 2003-2006
1.11 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.13 *
1.14 * Permission to use, modify and distribute this software is granted
1.15 @@ -29,30 +31,44 @@
1.16
1.17 /// \file
1.18 /// \ingroup flowalgs
1.19 -/// Implementation of the Hao-Orlin algorithms class for testing network
1.20 +/// \brief Implementation of the Hao-Orlin algorithm.
1.21 +///
1.22 +/// Implementation of the HaoOrlin algorithms class for testing network
1.23 /// reliability.
1.24
1.25 namespace lemon {
1.26
1.27 - /// \addtogroup flowalgs
1.28 - /// @{
1.29 -
1.30 - /// %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
1.31 + /// \ingroup flowalgs
1.32 + ///
1.33 + /// \brief %Hao-Orlin algorithm for calculate minimum cut in directed graphs.
1.34 ///
1.35 /// Hao-Orlin calculates the minimum cut in directed graphs. It
1.36 - /// separates the nodes of the graph into two disjoint sets and the
1.37 - /// summary of the edge capacities go from the first set to the
1.38 - /// second set is the minimum. The algorithm is a modified
1.39 - /// push-relabel preflow algorithm and it calculates the minimum cat
1.40 - /// in \f$ O(n^3) \f$ time. The purpose of such algorithm is testing
1.41 - /// network reliability. For sparse undirected graph you can use the
1.42 - /// algorithm of Nagamochi and Ibraki which solves the undirected
1.43 - /// problem in \f$ O(n^3) \f$ time.
1.44 + /// separates the nodes of the graph into two disjoint sets,
1.45 + /// \f$ V_{out} \f$ and \f$ V_{in} \f$. This separation is the minimum
1.46 + /// cut if the summary of the edge capacities which source is in
1.47 + /// \f$ V_{out} \f$ and the target is in \f$ V_{in} \f$ is the
1.48 + /// minimum. The algorithm is a modified push-relabel preflow
1.49 + /// algorithm and it calculates the minimum cut in \f$ O(n^3) \f$
1.50 + /// time. The purpose of such algorithm is testing network
1.51 + /// reliability. For sparse undirected graph you can use the
1.52 + /// algorithm of Nagamochi and Ibaraki which solves the undirected
1.53 + /// problem in \f$ O(ne + n^2 \log(n)) \f$ time and it is implemented in the
1.54 + /// MinCut algorithm class.
1.55 + ///
1.56 + /// \param _Graph is the graph type of the algorithm.
1.57 + /// \param _CapacityMap is an edge map of capacities which should
1.58 + /// be any numreric type. The default type is _Graph::EdgeMap<int>.
1.59 + /// \param _Tolerance is the handler of the inexact computation. The
1.60 + /// default type for it is Tolerance<typename CapacityMap::Value>.
1.61 ///
1.62 /// \author Attila Bernath and Balazs Dezso
1.63 +#ifdef DOXYGEN
1.64 + template <typename _Graph, typename _CapacityMap, typename _Tolerance>
1.65 +#else
1.66 template <typename _Graph,
1.67 typename _CapacityMap = typename _Graph::template EdgeMap<int>,
1.68 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
1.69 +#endif
1.70 class HaoOrlin {
1.71 protected:
1.72
1.73 @@ -70,6 +86,7 @@
1.74 typedef typename Graph::InEdgeIt InEdgeIt;
1.75
1.76 const Graph* _graph;
1.77 +
1.78 const CapacityMap* _capacity;
1.79
1.80 typedef typename Graph::template EdgeMap<Value> FlowMap;
1.81 @@ -80,18 +97,25 @@
1.82 int _node_num;
1.83
1.84 typedef ResGraphAdaptor<const Graph, Value, CapacityMap,
1.85 - FlowMap, Tolerance> ResGraph;
1.86 - typedef typename ResGraph::Node ResNode;
1.87 - typedef typename ResGraph::NodeIt ResNodeIt;
1.88 - typedef typename ResGraph::EdgeIt ResEdgeIt;
1.89 - typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.90 - typedef typename ResGraph::Edge ResEdge;
1.91 - typedef typename ResGraph::InEdgeIt ResInEdgeIt;
1.92 + FlowMap, Tolerance> OutResGraph;
1.93 + typedef typename OutResGraph::Edge OutResEdge;
1.94 +
1.95 + OutResGraph* _out_res_graph;
1.96
1.97 - ResGraph* _res_graph;
1.98 + typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
1.99 + OutCurrentEdgeMap* _out_current_edge;
1.100
1.101 - typedef typename Graph::template NodeMap<ResEdge> CurrentArcMap;
1.102 - CurrentArcMap* _current_arc;
1.103 + typedef RevGraphAdaptor<const Graph> RevGraph;
1.104 + RevGraph* _rev_graph;
1.105 +
1.106 + typedef ResGraphAdaptor<const RevGraph, Value, CapacityMap,
1.107 + FlowMap, Tolerance> InResGraph;
1.108 + typedef typename InResGraph::Edge InResEdge;
1.109 +
1.110 + InResGraph* _in_res_graph;
1.111 +
1.112 + typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
1.113 + InCurrentEdgeMap* _in_current_edge;
1.114
1.115
1.116 typedef IterableBoolMap<Graph, Node> WakeMap;
1.117 @@ -124,23 +148,37 @@
1.118
1.119 public:
1.120
1.121 + /// \brief Constructor
1.122 + ///
1.123 + /// Constructor of the algorithm class.
1.124 HaoOrlin(const Graph& graph, const CapacityMap& capacity,
1.125 const Tolerance& tolerance = Tolerance()) :
1.126 _graph(&graph), _capacity(&capacity),
1.127 - _preflow(0), _source(), _target(), _res_graph(0), _current_arc(0),
1.128 + _preflow(0), _source(), _target(),
1.129 + _out_res_graph(0), _out_current_edge(0),
1.130 + _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
1.131 _wake(0),_dist(0), _excess(0), _source_set(0),
1.132 _highest_active(), _active_nodes(), _dormant_max(), _dormant(),
1.133 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
1.134
1.135 ~HaoOrlin() {
1.136 - if (_res_graph) {
1.137 - delete _res_graph;
1.138 - }
1.139 if (_min_cut_map) {
1.140 delete _min_cut_map;
1.141 }
1.142 - if (_current_arc) {
1.143 - delete _current_arc;
1.144 + if (_in_current_edge) {
1.145 + delete _in_current_edge;
1.146 + }
1.147 + if (_in_res_graph) {
1.148 + delete _in_res_graph;
1.149 + }
1.150 + if (_rev_graph) {
1.151 + delete _rev_graph;
1.152 + }
1.153 + if (_out_current_edge) {
1.154 + delete _out_current_edge;
1.155 + }
1.156 + if (_out_res_graph) {
1.157 + delete _out_res_graph;
1.158 }
1.159 if (_source_set) {
1.160 delete _source_set;
1.161 @@ -161,8 +199,103 @@
1.162
1.163 private:
1.164
1.165 - void relabel(Node i) {
1.166 - int k = (*_dist)[i];
1.167 + template <typename ResGraph, typename EdgeMap>
1.168 + void findMinCut(const Node& target, bool out,
1.169 + ResGraph& res_graph, EdgeMap& current_edge) {
1.170 + typedef typename ResGraph::Edge ResEdge;
1.171 + typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.172 +
1.173 + for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
1.174 + (*_preflow)[it] = 0;
1.175 + }
1.176 + for (NodeIt it(*_graph); it != INVALID; ++it) {
1.177 + (*_wake)[it] = true;
1.178 + (*_dist)[it] = 1;
1.179 + (*_excess)[it] = 0;
1.180 + (*_source_set)[it] = false;
1.181 +
1.182 + res_graph.firstOut(current_edge[it], it);
1.183 + }
1.184 +
1.185 + _target = target;
1.186 + (*_dist)[target] = 0;
1.187 +
1.188 + for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
1.189 + Value delta = res_graph.rescap(it);
1.190 + if (!_tolerance.positive(delta)) continue;
1.191 +
1.192 + (*_excess)[res_graph.source(it)] -= delta;
1.193 + res_graph.augment(it, delta);
1.194 + Node a = res_graph.target(it);
1.195 + if (!_tolerance.positive((*_excess)[a]) &&
1.196 + (*_wake)[a] && a != _target) {
1.197 + _active_nodes[(*_dist)[a]].push_front(a);
1.198 + if (_highest_active < (*_dist)[a]) {
1.199 + _highest_active = (*_dist)[a];
1.200 + }
1.201 + }
1.202 + (*_excess)[a] += delta;
1.203 + }
1.204 +
1.205 + _dormant[0].push_front(_source);
1.206 + (*_source_set)[_source] = true;
1.207 + _dormant_max = 0;
1.208 + (*_wake)[_source] = false;
1.209 +
1.210 + _level_size[0] = 1;
1.211 + _level_size[1] = _node_num - 1;
1.212 +
1.213 + do {
1.214 + Node n;
1.215 + while ((n = findActiveNode()) != INVALID) {
1.216 + ResEdge e;
1.217 + while (_tolerance.positive((*_excess)[n]) &&
1.218 + (e = findAdmissibleEdge(n, res_graph, current_edge))
1.219 + != INVALID){
1.220 + Value delta;
1.221 + if ((*_excess)[n] < res_graph.rescap(e)) {
1.222 + delta = (*_excess)[n];
1.223 + } else {
1.224 + delta = res_graph.rescap(e);
1.225 + res_graph.nextOut(current_edge[n]);
1.226 + }
1.227 + if (!_tolerance.positive(delta)) continue;
1.228 + res_graph.augment(e, delta);
1.229 + (*_excess)[res_graph.source(e)] -= delta;
1.230 + Node a = res_graph.target(e);
1.231 + if (!_tolerance.positive((*_excess)[a]) && a != _target) {
1.232 + _active_nodes[(*_dist)[a]].push_front(a);
1.233 + }
1.234 + (*_excess)[a] += delta;
1.235 + }
1.236 + if (_tolerance.positive((*_excess)[n])) {
1.237 + relabel(n, res_graph, current_edge);
1.238 + }
1.239 + }
1.240 +
1.241 + Value current_value = cutValue(out);
1.242 + if (_min_cut > current_value){
1.243 + if (out) {
1.244 + for (NodeIt it(*_graph); it != INVALID; ++it) {
1.245 + _min_cut_map->set(it, !(*_wake)[it]);
1.246 + }
1.247 + } else {
1.248 + for (NodeIt it(*_graph); it != INVALID; ++it) {
1.249 + _min_cut_map->set(it, (*_wake)[it]);
1.250 + }
1.251 + }
1.252 +
1.253 + _min_cut = current_value;
1.254 + }
1.255 +
1.256 + } while (selectNewSink(res_graph));
1.257 + }
1.258 +
1.259 + template <typename ResGraph, typename EdgeMap>
1.260 + void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
1.261 + typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.262 +
1.263 + int k = (*_dist)[n];
1.264 if (_level_size[k] == 1) {
1.265 ++_dormant_max;
1.266 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.267 @@ -173,39 +306,34 @@
1.268 }
1.269 }
1.270 --_highest_active;
1.271 - } else {
1.272 - ResOutEdgeIt e(*_res_graph, i);
1.273 - while (e != INVALID && !(*_wake)[_res_graph->target(e)]) {
1.274 - ++e;
1.275 - }
1.276 -
1.277 - if (e == INVALID){
1.278 + } else {
1.279 + int new_dist = _node_num;
1.280 + for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
1.281 + Node t = res_graph.target(e);
1.282 + if ((*_wake)[t] && new_dist > (*_dist)[t]) {
1.283 + new_dist = (*_dist)[t];
1.284 + }
1.285 + }
1.286 + if (new_dist == _node_num) {
1.287 ++_dormant_max;
1.288 - (*_wake)[i] = false;
1.289 - _dormant[_dormant_max].push_front(i);
1.290 - --_level_size[(*_dist)[i]];
1.291 - } else{
1.292 - Node j = _res_graph->target(e);
1.293 - int new_dist = (*_dist)[j];
1.294 - ++e;
1.295 - while (e != INVALID){
1.296 - Node j = _res_graph->target(e);
1.297 - if ((*_wake)[j] && new_dist > (*_dist)[j]) {
1.298 - new_dist = (*_dist)[j];
1.299 - }
1.300 - ++e;
1.301 - }
1.302 - --_level_size[(*_dist)[i]];
1.303 - (*_dist)[i] = new_dist + 1;
1.304 - _highest_active = (*_dist)[i];
1.305 - _active_nodes[_highest_active].push_front(i);
1.306 - ++_level_size[(*_dist)[i]];
1.307 - _res_graph->firstOut((*_current_arc)[i], i);
1.308 + (*_wake)[n] = false;
1.309 + _dormant[_dormant_max].push_front(n);
1.310 + --_level_size[(*_dist)[n]];
1.311 + } else {
1.312 + --_level_size[(*_dist)[n]];
1.313 + (*_dist)[n] = new_dist + 1;
1.314 + _highest_active = (*_dist)[n];
1.315 + _active_nodes[_highest_active].push_front(n);
1.316 + ++_level_size[(*_dist)[n]];
1.317 + res_graph.firstOut(current_edge[n], n);
1.318 }
1.319 }
1.320 }
1.321
1.322 - bool selectNewSink(){
1.323 + template <typename ResGraph>
1.324 + bool selectNewSink(ResGraph& res_graph) {
1.325 + typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.326 +
1.327 Node old_target = _target;
1.328 (*_wake)[_target] = false;
1.329 --_level_size[(*_dist)[_target]];
1.330 @@ -249,9 +377,21 @@
1.331 }
1.332 }
1.333
1.334 - for (ResOutEdgeIt e(*_res_graph, old_target); e!=INVALID; ++e){
1.335 - if (!(*_source_set)[_res_graph->target(e)]){
1.336 - push(e, _res_graph->rescap(e));
1.337 + for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
1.338 + if (!(*_source_set)[res_graph.target(e)]) {
1.339 + Value delta = res_graph.rescap(e);
1.340 + if (!_tolerance.positive(delta)) continue;
1.341 + res_graph.augment(e, delta);
1.342 + (*_excess)[res_graph.source(e)] -= delta;
1.343 + Node a = res_graph.target(e);
1.344 + if (!_tolerance.positive((*_excess)[a]) &&
1.345 + (*_wake)[a] && a != _target) {
1.346 + _active_nodes[(*_dist)[a]].push_front(a);
1.347 + if (_highest_active < (*_dist)[a]) {
1.348 + _highest_active = (*_dist)[a];
1.349 + }
1.350 + }
1.351 + (*_excess)[a] += delta;
1.352 }
1.353 }
1.354
1.355 @@ -271,54 +411,64 @@
1.356 }
1.357 }
1.358
1.359 - ResEdge findAdmissibleEdge(const Node& n){
1.360 - ResEdge e = (*_current_arc)[n];
1.361 + template <typename ResGraph, typename EdgeMap>
1.362 + typename ResGraph::Edge findAdmissibleEdge(const Node& n,
1.363 + ResGraph& res_graph,
1.364 + EdgeMap& current_edge) {
1.365 + typedef typename ResGraph::Edge ResEdge;
1.366 + ResEdge e = current_edge[n];
1.367 while (e != INVALID &&
1.368 - ((*_dist)[n] <= (*_dist)[_res_graph->target(e)] ||
1.369 - !(*_wake)[_res_graph->target(e)])) {
1.370 - _res_graph->nextOut(e);
1.371 + ((*_dist)[n] <= (*_dist)[res_graph.target(e)] ||
1.372 + !(*_wake)[res_graph.target(e)])) {
1.373 + res_graph.nextOut(e);
1.374 }
1.375 if (e != INVALID) {
1.376 - (*_current_arc)[n] = e;
1.377 + current_edge[n] = e;
1.378 return e;
1.379 } else {
1.380 return INVALID;
1.381 }
1.382 }
1.383
1.384 - void push(ResEdge& e,const Value& delta){
1.385 - _res_graph->augment(e, delta);
1.386 - if (!_tolerance.positive(delta)) return;
1.387 -
1.388 - (*_excess)[_res_graph->source(e)] -= delta;
1.389 - Node a = _res_graph->target(e);
1.390 - if (!_tolerance.positive((*_excess)[a]) && (*_wake)[a] && a != _target) {
1.391 - _active_nodes[(*_dist)[a]].push_front(a);
1.392 - if (_highest_active < (*_dist)[a]) {
1.393 - _highest_active = (*_dist)[a];
1.394 + Value cutValue(bool out) {
1.395 + Value value = 0;
1.396 + if (out) {
1.397 + for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
1.398 + for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {
1.399 + if (!(*_wake)[_graph->source(e)]){
1.400 + value += (*_capacity)[e];
1.401 + }
1.402 + }
1.403 + }
1.404 + } else {
1.405 + for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
1.406 + for (OutEdgeIt e(*_graph, it); e != INVALID; ++e) {
1.407 + if (!(*_wake)[_graph->target(e)]){
1.408 + value += (*_capacity)[e];
1.409 + }
1.410 + }
1.411 }
1.412 }
1.413 - (*_excess)[a] += delta;
1.414 + return value;
1.415 }
1.416 -
1.417 - Value cutValue() {
1.418 - Value value = 0;
1.419 - for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
1.420 - for (InEdgeIt e(*_graph, it); e != INVALID; ++e) {
1.421 - if (!(*_wake)[_graph->source(e)]){
1.422 - value += (*_capacity)[e];
1.423 - }
1.424 - }
1.425 - }
1.426 - return value;
1.427 - }
1.428 +
1.429
1.430 public:
1.431
1.432 + /// \name Execution control
1.433 + /// The simplest way to execute the algorithm is to use
1.434 + /// one of the member functions called \c run(...).
1.435 + /// \n
1.436 + /// If you need more control on the execution,
1.437 + /// first you must call \ref init(), then the \ref calculateIn() or
1.438 + /// \ref calculateIn() functions.
1.439 +
1.440 + /// @{
1.441 +
1.442 /// \brief Initializes the internal data structures.
1.443 ///
1.444 /// Initializes the internal data structures. It creates
1.445 - /// the maps, residual graph adaptor and some bucket structures
1.446 + /// the maps, residual graph adaptors and some bucket structures
1.447 /// for the algorithm.
1.448 void init() {
1.449 init(NodeIt(*_graph));
1.450 @@ -353,25 +503,34 @@
1.451 if (!_source_set) {
1.452 _source_set = new SourceSetMap(*_graph);
1.453 }
1.454 - if (!_current_arc) {
1.455 - _current_arc = new CurrentArcMap(*_graph);
1.456 + if (!_out_res_graph) {
1.457 + _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
1.458 + }
1.459 + if (!_out_current_edge) {
1.460 + _out_current_edge = new OutCurrentEdgeMap(*_graph);
1.461 + }
1.462 + if (!_rev_graph) {
1.463 + _rev_graph = new RevGraph(*_graph);
1.464 + }
1.465 + if (!_in_res_graph) {
1.466 + _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
1.467 + }
1.468 + if (!_in_current_edge) {
1.469 + _in_current_edge = new InCurrentEdgeMap(*_graph);
1.470 }
1.471 if (!_min_cut_map) {
1.472 _min_cut_map = new MinCutMap(*_graph);
1.473 }
1.474 - if (!_res_graph) {
1.475 - _res_graph = new ResGraph(*_graph, *_capacity, *_preflow);
1.476 - }
1.477
1.478 _min_cut = std::numeric_limits<Value>::max();
1.479 }
1.480
1.481
1.482 /// \brief Calculates the minimum cut with the \c source node
1.483 - /// in the first partition.
1.484 + /// in the \f$ V_{out} \f$.
1.485 ///
1.486 /// Calculates the minimum cut with the \c source node
1.487 - /// in the first partition.
1.488 + /// in the \f$ V_{out} \f$.
1.489 void calculateOut() {
1.490 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.491 if (it != _source) {
1.492 @@ -382,75 +541,20 @@
1.493 }
1.494
1.495 /// \brief Calculates the minimum cut with the \c source node
1.496 - /// in the first partition.
1.497 + /// in the \f$ V_{out} \f$.
1.498 ///
1.499 /// Calculates the minimum cut with the \c source node
1.500 - /// in the first partition. The \c target is the initial target
1.501 + /// in the \f$ V_{out} \f$. The \c target is the initial target
1.502 /// for the push-relabel algorithm.
1.503 void calculateOut(const Node& target) {
1.504 - for (NodeIt it(*_graph); it != INVALID; ++it) {
1.505 - (*_wake)[it] = true;
1.506 - (*_dist)[it] = 1;
1.507 - (*_excess)[it] = 0;
1.508 - (*_source_set)[it] = false;
1.509 -
1.510 - _res_graph->firstOut((*_current_arc)[it], it);
1.511 - }
1.512 -
1.513 - _target = target;
1.514 - (*_dist)[target] = 0;
1.515 -
1.516 - for (ResOutEdgeIt it(*_res_graph, _source); it != INVALID; ++it) {
1.517 - push(it, _res_graph->rescap(it));
1.518 - }
1.519 -
1.520 - _dormant[0].push_front(_source);
1.521 - (*_source_set)[_source] = true;
1.522 - _dormant_max = 0;
1.523 - (*_wake)[_source]=false;
1.524 -
1.525 - _level_size[0] = 1;
1.526 - _level_size[1] = _node_num - 1;
1.527 -
1.528 - do {
1.529 - Node n;
1.530 - while ((n = findActiveNode()) != INVALID) {
1.531 - ResEdge e;
1.532 - while (_tolerance.positive((*_excess)[n]) &&
1.533 - (e = findAdmissibleEdge(n)) != INVALID){
1.534 - Value delta;
1.535 - if ((*_excess)[n] < _res_graph->rescap(e)) {
1.536 - delta = (*_excess)[n];
1.537 - } else {
1.538 - delta = _res_graph->rescap(e);
1.539 - _res_graph->nextOut((*_current_arc)[n]);
1.540 - }
1.541 - if (!_tolerance.positive(delta)) continue;
1.542 - _res_graph->augment(e, delta);
1.543 - (*_excess)[_res_graph->source(e)] -= delta;
1.544 - Node a = _res_graph->target(e);
1.545 - if (!_tolerance.positive((*_excess)[a]) && a != _target) {
1.546 - _active_nodes[(*_dist)[a]].push_front(a);
1.547 - }
1.548 - (*_excess)[a] += delta;
1.549 - }
1.550 - if (_tolerance.positive((*_excess)[n])) {
1.551 - relabel(n);
1.552 - }
1.553 - }
1.554 -
1.555 - Value current_value = cutValue();
1.556 - if (_min_cut > current_value){
1.557 - for (NodeIt it(*_graph); it != INVALID; ++it) {
1.558 - _min_cut_map->set(it, !(*_wake)[it]);
1.559 - }
1.560 -
1.561 - _min_cut = current_value;
1.562 - }
1.563 -
1.564 - } while (selectNewSink());
1.565 + findMinCut(target, true, *_out_res_graph, *_out_current_edge);
1.566 }
1.567
1.568 + /// \brief Calculates the minimum cut with the \c source node
1.569 + /// in the \f$ V_{in} \f$.
1.570 + ///
1.571 + /// Calculates the minimum cut with the \c source node
1.572 + /// in the \f$ V_{in} \f$.
1.573 void calculateIn() {
1.574 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.575 if (it != _source) {
1.576 @@ -460,40 +564,70 @@
1.577 }
1.578 }
1.579
1.580 + /// \brief Calculates the minimum cut with the \c source node
1.581 + /// in the \f$ V_{in} \f$.
1.582 + ///
1.583 + /// Calculates the minimum cut with the \c source node
1.584 + /// in the \f$ V_{in} \f$. The \c target is the initial target
1.585 + /// for the push-relabel algorithm.
1.586 + void calculateIn(const Node& target) {
1.587 + findMinCut(target, false, *_in_res_graph, *_in_current_edge);
1.588 + }
1.589 +
1.590 + /// \brief Runs the algorithm.
1.591 + ///
1.592 + /// Runs the algorithm. It finds a proper \c source and \c target
1.593 + /// and then calls the \ref init(), \ref calculateOut() and \ref
1.594 + /// calculateIn().
1.595 void run() {
1.596 init();
1.597 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.598 if (it != _source) {
1.599 - startOut(it);
1.600 - // startIn(it);
1.601 + calculateOut(it);
1.602 + calculateIn(it);
1.603 return;
1.604 }
1.605 }
1.606 }
1.607
1.608 + /// \brief Runs the algorithm.
1.609 + ///
1.610 + /// Runs the algorithm. It finds a proper \c target and then calls
1.611 + /// the \ref init(), \ref calculateOut() and \ref calculateIn().
1.612 void run(const Node& s) {
1.613 init(s);
1.614 for (NodeIt it(*_graph); it != INVALID; ++it) {
1.615 if (it != _source) {
1.616 - startOut(it);
1.617 - // startIn(it);
1.618 + calculateOut(it);
1.619 + calculateIn(it);
1.620 return;
1.621 }
1.622 }
1.623 }
1.624
1.625 + /// \brief Runs the algorithm.
1.626 + ///
1.627 + /// Runs the algorithm. It just calls the \ref init() and then
1.628 + /// \ref calculateOut() and \ref calculateIn().
1.629 void run(const Node& s, const Node& t) {
1.630 - init(s);
1.631 - startOut(t);
1.632 - startIn(t);
1.633 + init(s);
1.634 + calculateOut(t);
1.635 + calculateIn(t);
1.636 }
1.637 +
1.638 + /// @}
1.639
1.640 - /// \brief Returns the value of the minimum value cut with node \c
1.641 - /// source on the source side.
1.642 + /// \name Query Functions The result of the %HaoOrlin algorithm
1.643 + /// can be obtained using these functions.
1.644 + /// \n
1.645 + /// Before the use of these functions, either \ref run(), \ref
1.646 + /// calculateOut() or \ref calculateIn() must be called.
1.647 +
1.648 + /// @{
1.649 +
1.650 + /// \brief Returns the value of the minimum value cut.
1.651 ///
1.652 - /// Returns the value of the minimum value cut with node \c source
1.653 - /// on the source side. This function can be called after running
1.654 - /// \ref findMinCut.
1.655 + /// Returns the value of the minimum value cut.
1.656 Value minCut() const {
1.657 return _min_cut;
1.658 }
1.659 @@ -502,8 +636,8 @@
1.660 /// \brief Returns a minimum value cut.
1.661 ///
1.662 /// Sets \c nodeMap to the characteristic vector of a minimum
1.663 - /// value cut with node \c source on the source side. This
1.664 - /// function can be called after running \ref findMinCut.
1.665 + /// value cut. The nodes in \f$ V_{out} \f$ will be set true and
1.666 + /// the nodes in \f$ V_{in} \f$ will be set false.
1.667 /// \pre nodeMap should be a bool-valued node-map.
1.668 template <typename NodeMap>
1.669 Value minCut(NodeMap& nodeMap) const {
1.670 @@ -512,6 +646,8 @@
1.671 }
1.672 return minCut();
1.673 }
1.674 +
1.675 + /// @}
1.676
1.677 }; //class HaoOrlin
1.678
2.1 --- a/lemon/min_cut.h Fri Sep 29 11:26:29 2006 +0000
2.2 +++ b/lemon/min_cut.h Fri Sep 29 11:36:30 2006 +0000
2.3 @@ -830,18 +830,19 @@
2.4
2.5 /// \ingroup topology
2.6 ///
2.7 - /// \brief Calculates the min cut in an undirected graph.
2.8 + /// \brief Calculates the minimum cut in an undirected graph.
2.9 ///
2.10 - /// Calculates the min cut in an undirected graph.
2.11 - /// The algorithm separates the graph's nodes into two partitions with the
2.12 - /// min sum of edge capacities between the two partitions. The
2.13 - /// algorithm can be used to test the network reliability specifically
2.14 - /// to test how many links have to be destroyed in the network to split it
2.15 - /// at least two distinict subnetwork.
2.16 + /// Calculates the minimum cut in an undirected graph with the
2.17 + /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
2.18 + /// nodes into two partitions with the minimum sum of edge capacities
2.19 + /// between the two partitions. The algorithm can be used to test
2.20 + /// the network reliability specifically to test how many links have
2.21 + /// to be destroyed in the network to split it at least two
2.22 + /// distinict subnetwork.
2.23 ///
2.24 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
2.25 - /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
2.26 - /// the neutral capacity map is used then it uses BucketHeap which
2.27 + /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
2.28 + /// \f$. When capacity map is neutral then it uses BucketHeap which
2.29 /// results \f$ O(ne) \f$ time complexity.
2.30 #ifdef DOXYGEN
2.31 template <typename _Graph, typename _CapacityMap, typename _Traits>