1.1 --- a/lemon/nagamochi_ibaraki.h Tue Jan 09 11:42:43 2007 +0000
1.2 +++ b/lemon/nagamochi_ibaraki.h Thu Jan 11 21:05:00 2007 +0000
1.3 @@ -14,24 +14,31 @@
1.4 *
1.5 */
1.6
1.7 -#ifndef LEMON_MIN_CUT_H
1.8 -#define LEMON_MIN_CUT_H
1.9 +#ifndef LEMON_NAGAMOCHI_IBARAKI_H
1.10 +#define LEMON_NAGAMOCHI_IBARAKI_H
1.11
1.12
1.13 -/// \ingroup topology
1.14 -/// \file
1.15 -/// \brief Maximum cardinality search and min cut in undirected graphs.
1.16 +/// \ingroup topology
1.17 +/// \file
1.18 +/// \brief Maximum cardinality search and minimum cut in undirected
1.19 +/// graphs.
1.20
1.21 #include <lemon/list_graph.h>
1.22 #include <lemon/bin_heap.h>
1.23 #include <lemon/bucket_heap.h>
1.24
1.25 +#include <lemon/unionfind.h>
1.26 +#include <lemon/topology.h>
1.27 +
1.28 #include <lemon/bits/invalid.h>
1.29 #include <lemon/error.h>
1.30 #include <lemon/maps.h>
1.31
1.32 #include <functional>
1.33
1.34 +#include <lemon/graph_writer.h>
1.35 +#include <lemon/time_measure.h>
1.36 +
1.37 namespace lemon {
1.38
1.39 namespace _min_cut_bits {
1.40 @@ -146,6 +153,7 @@
1.41 return new CardinalityMap(graph);
1.42 }
1.43
1.44 +
1.45 };
1.46
1.47 /// \ingroup topology
1.48 @@ -665,6 +673,12 @@
1.49 /// of this funcion is undefined.
1.50 Value cardinality(Node node) const { return (*_cardinality)[node]; }
1.51
1.52 + /// \brief The current cardinality of a node.
1.53 + ///
1.54 + /// Returns the current cardinality of a node.
1.55 + /// \pre the given node should be reached but not processed
1.56 + Value currentCardinality(Node node) const { return (*_heap)[node]; }
1.57 +
1.58 /// \brief Returns a reference to the NodeMap of cardinalities.
1.59 ///
1.60 /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
1.61 @@ -729,9 +743,21 @@
1.62 throw UninitializedParameter();
1.63 }
1.64
1.65 + /// \brief The CutValueMap type
1.66 + ///
1.67 + /// The type of the map that stores the cut value of a node.
1.68 + typedef AuxGraph::NodeMap<Value> AuxCutValueMap;
1.69 +
1.70 + /// \brief Instantiates a AuxCutValueMap.
1.71 + ///
1.72 + /// This function instantiates a \ref AuxCutValueMap.
1.73 + static AuxCutValueMap *createAuxCutValueMap(const AuxGraph& graph) {
1.74 + return new AuxCutValueMap(graph);
1.75 + }
1.76 +
1.77 /// \brief The AuxCapacityMap type
1.78 ///
1.79 - /// The type of the map that stores the auxing edge capacities.
1.80 + /// The type of the map that stores the auxiliary edge capacities.
1.81 typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
1.82
1.83 /// \brief Instantiates a AuxCapacityMap.
1.84 @@ -806,28 +832,6 @@
1.85
1.86 };
1.87
1.88 - namespace _min_cut_bits {
1.89 - template <typename _Key>
1.90 - class LastTwoMap {
1.91 - public:
1.92 - typedef _Key Key;
1.93 - typedef bool Value;
1.94 -
1.95 - LastTwoMap(int _num) : num(_num) {}
1.96 - void set(const Key& key, bool val) {
1.97 - if (!val) return;
1.98 - --num;
1.99 - if (num > 1) return;
1.100 - keys[num] = key;
1.101 - }
1.102 -
1.103 - Key operator[](int index) const { return keys[index]; }
1.104 - private:
1.105 - Key keys[2];
1.106 - int num;
1.107 - };
1.108 - }
1.109 -
1.110 /// \ingroup topology
1.111 ///
1.112 /// \brief Calculates the minimum cut in an undirected graph.
1.113 @@ -841,9 +845,12 @@
1.114 /// distinict subnetwork.
1.115 ///
1.116 /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
1.117 - /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n))
1.118 - /// \f$. When capacity map is neutral then it uses BucketHeap which
1.119 + /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$.
1.120 + /// When capacity map is neutral then it uses BucketHeap which
1.121 /// results \f$ O(ne) \f$ time complexity.
1.122 + ///
1.123 + /// \warning The value type of the capacity map should be able to hold
1.124 + /// any cut value of the graph, otherwise the result can overflow.
1.125 #ifdef DOXYGEN
1.126 template <typename _Graph, typename _CapacityMap, typename _Traits>
1.127 #else
1.128 @@ -880,6 +887,8 @@
1.129 typedef typename Traits::AuxGraph AuxGraph;
1.130 /// The type of the aux capacity map
1.131 typedef typename Traits::AuxCapacityMap AuxCapacityMap;
1.132 + /// The type of the aux cut value map
1.133 + typedef typename Traits::AuxCutValueMap AuxCutValueMap;
1.134 /// The cross reference type used for the current heap.
1.135 typedef typename Traits::HeapCrossRef HeapCrossRef;
1.136 /// The heap type used by the max cardinality algorithm.
1.137 @@ -988,6 +997,11 @@
1.138 /// \brief Indicates if \ref _aux_capacity is locally allocated
1.139 /// (\c true) or not.
1.140 bool local_aux_capacity;
1.141 + /// Pointer to the aux cut value map
1.142 + AuxCutValueMap *_aux_cut_value;
1.143 + /// \brief Indicates if \ref _aux_cut_value is locally allocated
1.144 + /// (\c true) or not.
1.145 + bool local_aux_cut_value;
1.146 /// Pointer to the heap cross references.
1.147 HeapCrossRef *_heap_cross_ref;
1.148 /// \brief Indicates if \ref _heap_cross_ref is locally allocated
1.149 @@ -1002,8 +1016,8 @@
1.150 Value _min_cut;
1.151 /// The number of the nodes of the aux graph.
1.152 int _node_num;
1.153 - /// The first and last node of the min cut in the next list;
1.154 - typename Graph::Node _first_node, _last_node;
1.155 + /// The first and last node of the min cut in the next list.
1.156 + std::vector<typename Graph::Node> _cut;
1.157
1.158 /// \brief The first and last element in the list associated
1.159 /// to the aux graph node.
1.160 @@ -1011,7 +1025,7 @@
1.161 /// \brief The next node in the node lists.
1.162 ListRefMap *_next;
1.163
1.164 - void create_structures() {
1.165 + void createStructures() {
1.166 if (!_capacity) {
1.167 local_capacity = true;
1.168 _capacity = Traits::createCapacityMap(*_graph);
1.169 @@ -1024,31 +1038,16 @@
1.170 local_aux_capacity = true;
1.171 _aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
1.172 }
1.173 + if(!_aux_cut_value) {
1.174 + local_aux_cut_value = true;
1.175 + _aux_cut_value = Traits::createAuxCutValueMap(*_aux_graph);
1.176 + }
1.177
1.178 _first = Traits::createNodeRefMap(*_aux_graph);
1.179 _last = Traits::createNodeRefMap(*_aux_graph);
1.180
1.181 _next = Traits::createListRefMap(*_graph);
1.182
1.183 - typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
1.184 -
1.185 - for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
1.186 - _next->set(it, INVALID);
1.187 - typename AuxGraph::Node node = _aux_graph->addNode();
1.188 - _first->set(node, it);
1.189 - _last->set(node, it);
1.190 - ref.set(it, node);
1.191 - }
1.192 -
1.193 - for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
1.194 - if (_graph->source(it) == _graph->target(it)) continue;
1.195 - typename AuxGraph::UEdge uedge =
1.196 - _aux_graph->addEdge(ref[_graph->source(it)],
1.197 - ref[_graph->target(it)]);
1.198 - _aux_capacity->set(uedge, (*_capacity)[it]);
1.199 -
1.200 - }
1.201 -
1.202 if (!_heap_cross_ref) {
1.203 local_heap_cross_ref = true;
1.204 _heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
1.205 @@ -1059,6 +1058,57 @@
1.206 }
1.207 }
1.208
1.209 + void createAuxGraph() {
1.210 + typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
1.211 +
1.212 + for (typename Graph::NodeIt n(*_graph); n != INVALID; ++n) {
1.213 + _next->set(n, INVALID);
1.214 + typename AuxGraph::Node node = _aux_graph->addNode();
1.215 + _first->set(node, n);
1.216 + _last->set(node, n);
1.217 + ref.set(n, node);
1.218 + }
1.219 +
1.220 + typename AuxGraph::template NodeMap<typename AuxGraph::UEdge>
1.221 + edges(*_aux_graph, INVALID);
1.222 +
1.223 + for (typename Graph::NodeIt n(*_graph); n != INVALID; ++n) {
1.224 + for (typename Graph::IncEdgeIt e(*_graph, n); e != INVALID; ++e) {
1.225 + typename Graph::Node tn = _graph->runningNode(e);
1.226 + if (n < tn || n == tn) continue;
1.227 + if (edges[ref[tn]] != INVALID) {
1.228 + Value value =
1.229 + (*_aux_capacity)[edges[ref[tn]]] + (*_capacity)[e];
1.230 + _aux_capacity->set(edges[ref[tn]], value);
1.231 + } else {
1.232 + edges.set(ref[tn], _aux_graph->addEdge(ref[n], ref[tn]));
1.233 + Value value = (*_capacity)[e];
1.234 + _aux_capacity->set(edges[ref[tn]], value);
1.235 + }
1.236 + }
1.237 + for (typename Graph::IncEdgeIt e(*_graph, n); e != INVALID; ++e) {
1.238 + typename Graph::Node tn = _graph->runningNode(e);
1.239 + edges.set(ref[tn], INVALID);
1.240 + }
1.241 + }
1.242 +
1.243 + _cut.resize(1, INVALID);
1.244 + _min_cut = std::numeric_limits<Value>::max();
1.245 + for (typename AuxGraph::NodeIt n(*_aux_graph); n != INVALID; ++n) {
1.246 + Value value = 0;
1.247 + for (typename AuxGraph::IncEdgeIt e(*_aux_graph, n);
1.248 + e != INVALID; ++e) {
1.249 + value += (*_aux_capacity)[e];
1.250 + }
1.251 + if (_min_cut > value) {
1.252 + _min_cut = value;
1.253 + _cut[0] = (*_first)[n];
1.254 + }
1.255 + (*_aux_cut_value)[n] = value;
1.256 + }
1.257 + }
1.258 +
1.259 +
1.260 public :
1.261
1.262 typedef NagamochiIbaraki Create;
1.263 @@ -1073,6 +1123,7 @@
1.264 _capacity(&capacity), local_capacity(false),
1.265 _aux_graph(0), local_aux_graph(false),
1.266 _aux_capacity(0), local_aux_capacity(false),
1.267 + _aux_cut_value(0), local_aux_cut_value(false),
1.268 _heap_cross_ref(0), local_heap_cross_ref(false),
1.269 _heap(0), local_heap(false),
1.270 _first(0), _last(0), _next(0) {}
1.271 @@ -1090,6 +1141,7 @@
1.272 _capacity(0), local_capacity(false),
1.273 _aux_graph(0), local_aux_graph(false),
1.274 _aux_capacity(0), local_aux_capacity(false),
1.275 + _aux_cut_value(0), local_aux_cut_value(false),
1.276 _heap_cross_ref(0), local_heap_cross_ref(false),
1.277 _heap(0), local_heap(false),
1.278 _first(0), _last(0), _next(0) {}
1.279 @@ -1104,6 +1156,7 @@
1.280 if (_last) delete _last;
1.281 if (_next) delete _next;
1.282 if (local_aux_capacity) delete _aux_capacity;
1.283 + if (local_aux_cut_value) delete _aux_cut_value;
1.284 if (local_aux_graph) delete _aux_graph;
1.285 if (local_capacity) delete _capacity;
1.286 }
1.287 @@ -1178,91 +1231,221 @@
1.288 ///
1.289 /// Initializes the internal data structures.
1.290 void init() {
1.291 - create_structures();
1.292 - _first_node = _last_node = INVALID;
1.293 _node_num = countNodes(*_graph);
1.294 + createStructures();
1.295 + createAuxGraph();
1.296 }
1.297
1.298 + private:
1.299 +
1.300 + struct EdgeInfo {
1.301 + typename AuxGraph::Node source, target;
1.302 + Value capacity;
1.303 + };
1.304 +
1.305 + struct EdgeInfoLess {
1.306 + bool operator()(const EdgeInfo& left, const EdgeInfo& right) const {
1.307 + return (left.source < right.source) ||
1.308 + (left.source == right.source && left.target < right.target);
1.309 + }
1.310 + };
1.311 +
1.312 + public:
1.313 +
1.314 +
1.315 /// \brief Processes the next phase
1.316 ///
1.317 - /// Processes the next phase in the algorithm. The function
1.318 - /// should be called countNodes(graph) - 1 times to get
1.319 - /// surely the min cut in the graph. The
1.320 + /// Processes the next phase in the algorithm. The function should
1.321 + /// be called at most countNodes(graph) - 1 times to get surely
1.322 + /// the min cut in the graph.
1.323 ///
1.324 ///\return %True when the algorithm finished.
1.325 bool processNextPhase() {
1.326 if (_node_num <= 1) return true;
1.327 - using namespace _min_cut_bits;
1.328
1.329 typedef typename AuxGraph::Node Node;
1.330 typedef typename AuxGraph::NodeIt NodeIt;
1.331 typedef typename AuxGraph::UEdge UEdge;
1.332 + typedef typename AuxGraph::UEdgeIt UEdgeIt;
1.333 typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
1.334
1.335 - typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
1.336 - template DefHeap<Heap, HeapCrossRef>::
1.337 - template DefCardinalityMap<NullMap<Node, Value> >::
1.338 - template DefProcessedMap<LastTwoMap<Node> >::
1.339 - Create MaxCardinalitySearch;
1.340 -
1.341 - MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
1.342 - for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
1.343 - _heap_cross_ref->set(it, Heap::PRE_HEAP);
1.344 + typename AuxGraph::template UEdgeMap<Value> _edge_cut(*_aux_graph);
1.345 +
1.346 +
1.347 + for (NodeIt n(*_aux_graph); n != INVALID; ++n) {
1.348 + _heap_cross_ref->set(n, Heap::PRE_HEAP);
1.349 }
1.350 - mcs.heap(*_heap, *_heap_cross_ref);
1.351
1.352 - LastTwoMap<Node> last_two_nodes(_node_num);
1.353 - mcs.processedMap(last_two_nodes);
1.354 + std::vector<Node> nodes;
1.355 + nodes.reserve(_node_num);
1.356 + int sep = 0;
1.357
1.358 - NullMap<Node, Value> cardinality;
1.359 - mcs.cardinalityMap(cardinality);
1.360 + Value alpha = 0;
1.361 + Value emc = std::numeric_limits<Value>::max();
1.362
1.363 - mcs.run();
1.364 + _heap->push(typename AuxGraph::NodeIt(*_aux_graph), 0);
1.365 + while (!_heap->empty()) {
1.366 + Node node = _heap->top();
1.367 + Value value = _heap->prio();
1.368 +
1.369 + _heap->pop();
1.370 + for (typename AuxGraph::IncEdgeIt e(*_aux_graph, node);
1.371 + e != INVALID; ++e) {
1.372 + Node tn = _aux_graph->runningNode(e);
1.373 + switch (_heap->state(tn)) {
1.374 + case Heap::PRE_HEAP:
1.375 + _heap->push(tn, (*_aux_capacity)[e]);
1.376 + _edge_cut[e] = (*_heap)[tn];
1.377 + break;
1.378 + case Heap::IN_HEAP:
1.379 + _heap->decrease(tn, (*_aux_capacity)[e] + (*_heap)[tn]);
1.380 + _edge_cut[e] = (*_heap)[tn];
1.381 + break;
1.382 + case Heap::POST_HEAP:
1.383 + break;
1.384 + }
1.385 + }
1.386
1.387 - Node new_node = _aux_graph->addNode();
1.388 + alpha += (*_aux_cut_value)[node];
1.389 + alpha -= 2 * value;
1.390
1.391 - typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
1.392 -
1.393 - Node first_node = last_two_nodes[0];
1.394 - Node second_node = last_two_nodes[1];
1.395 -
1.396 - _next->set((*_last)[first_node], (*_first)[second_node]);
1.397 - _first->set(new_node, (*_first)[first_node]);
1.398 - _last->set(new_node, (*_last)[second_node]);
1.399 -
1.400 - Value current_cut = 0;
1.401 - for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
1.402 - Node node = _aux_graph->runningNode(it);
1.403 - current_cut += (*_aux_capacity)[it];
1.404 - if (node == second_node) continue;
1.405 - if (edges[node] == INVALID) {
1.406 - edges[node] = _aux_graph->addEdge(new_node, node);
1.407 - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1.408 - } else {
1.409 - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
1.410 + nodes.push_back(node);
1.411 + if (!_heap->empty()) {
1.412 + if (alpha < emc) {
1.413 + emc = alpha;
1.414 + sep = nodes.size();
1.415 + }
1.416 }
1.417 }
1.418
1.419 - if (_first_node == INVALID || current_cut < _min_cut) {
1.420 - _first_node = (*_first)[first_node];
1.421 - _last_node = (*_last)[first_node];
1.422 - _min_cut = current_cut;
1.423 + if ((int)nodes.size() < _node_num) {
1.424 + _aux_graph->clear();
1.425 + _node_num = 1;
1.426 + _cut.clear();
1.427 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.428 + typename Graph::Node n = (*_first)[nodes[i]];
1.429 + while (n != INVALID) {
1.430 + _cut.push_back(n);
1.431 + n = (*_next)[n];
1.432 + }
1.433 + }
1.434 + _min_cut = 0;
1.435 + return true;
1.436 }
1.437
1.438 - _aux_graph->erase(first_node);
1.439 + if (emc < _min_cut) {
1.440 + _cut.clear();
1.441 + for (int i = 0; i < sep; ++i) {
1.442 + typename Graph::Node n = (*_first)[nodes[i]];
1.443 + while (n != INVALID) {
1.444 + _cut.push_back(n);
1.445 + n = (*_next)[n];
1.446 + }
1.447 + }
1.448 + _min_cut = emc;
1.449 + }
1.450
1.451 - for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
1.452 - Node node = _aux_graph->runningNode(it);
1.453 - if (edges[node] == INVALID) {
1.454 - edges[node] = _aux_graph->addEdge(new_node, node);
1.455 - (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
1.456 - } else {
1.457 - (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];
1.458 + typedef typename AuxGraph::template NodeMap<int> UfeCr;
1.459 + UfeCr ufecr(*_aux_graph);
1.460 + typedef UnionFindEnum<UfeCr> Ufe;
1.461 + Ufe ufe(ufecr);
1.462 +
1.463 + for (typename AuxGraph::NodeIt n(*_aux_graph); n != INVALID; ++n) {
1.464 + ufe.insert(n);
1.465 + }
1.466 +
1.467 + for (typename AuxGraph::UEdgeIt e(*_aux_graph); e != INVALID; ++e) {
1.468 + if (_edge_cut[e] >= emc) {
1.469 + ufe.join(_aux_graph->source(e), _aux_graph->target(e));
1.470 }
1.471 }
1.472 - _aux_graph->erase(second_node);
1.473
1.474 - --_node_num;
1.475 + if (ufe.size((typename Ufe::ClassIt)(ufe)) == _node_num) {
1.476 + _aux_graph->clear();
1.477 + _node_num = 1;
1.478 + return true;
1.479 + }
1.480 +
1.481 + std::vector<typename AuxGraph::Node> remnodes;
1.482 +
1.483 + typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
1.484 + for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
1.485 + if (ufe.size(c) == 1) continue;
1.486 + for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) {
1.487 + if ((Node)r == (Node)c) continue;
1.488 + _next->set((*_last)[c], (*_first)[r]);
1.489 + _last->set(c, (*_last)[r]);
1.490 + remnodes.push_back(r);
1.491 + --_node_num;
1.492 + }
1.493 + }
1.494 +
1.495 + std::vector<EdgeInfo> addedges;
1.496 + std::vector<UEdge> remedges;
1.497 +
1.498 + for (typename AuxGraph::UEdgeIt e(*_aux_graph);
1.499 + e != INVALID; ++e) {
1.500 + Node sn = ufe.find(_aux_graph->source(e));
1.501 + Node tn = ufe.find(_aux_graph->target(e));
1.502 + if ((ufe.size(sn) == 1 && ufe.size(tn) == 1)) {
1.503 + continue;
1.504 + }
1.505 + if (sn == tn) {
1.506 + remedges.push_back(e);
1.507 + continue;
1.508 + }
1.509 + EdgeInfo info;
1.510 + if (sn < tn) {
1.511 + info.source = sn;
1.512 + info.target = tn;
1.513 + } else {
1.514 + info.source = tn;
1.515 + info.target = sn;
1.516 + }
1.517 + info.capacity = (*_aux_capacity)[e];
1.518 + addedges.push_back(info);
1.519 + remedges.push_back(e);
1.520 + }
1.521 +
1.522 + for (int i = 0; i < (int)remedges.size(); ++i) {
1.523 + _aux_graph->erase(remedges[i]);
1.524 + }
1.525 +
1.526 + sort(addedges.begin(), addedges.end(), EdgeInfoLess());
1.527 +
1.528 + {
1.529 + int i = 0;
1.530 + while (i < (int)addedges.size()) {
1.531 + Node sn = addedges[i].source;
1.532 + Node tn = addedges[i].target;
1.533 + Value ec = addedges[i].capacity;
1.534 + ++i;
1.535 + while (i < (int)addedges.size() &&
1.536 + sn == addedges[i].source && tn == addedges[i].target) {
1.537 + ec += addedges[i].capacity;
1.538 + ++i;
1.539 + }
1.540 + typename AuxGraph::UEdge ne = _aux_graph->addEdge(sn, tn);
1.541 + (*_aux_capacity)[ne] = ec;
1.542 + }
1.543 + }
1.544 +
1.545 + for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
1.546 + if (ufe.size(c) == 1) continue;
1.547 + Value cutvalue = 0;
1.548 + for (typename AuxGraph::IncEdgeIt e(*_aux_graph, c);
1.549 + e != INVALID; ++e) {
1.550 + cutvalue += (*_aux_capacity)[e];
1.551 + }
1.552 +
1.553 + (*_aux_cut_value)[c] = cutvalue;
1.554 +
1.555 + }
1.556 +
1.557 + for (int i = 0; i < (int)remnodes.size(); ++i) {
1.558 + _aux_graph->erase(remnodes[i]);
1.559 + }
1.560 +
1.561 return _node_num == 1;
1.562 }
1.563
1.564 @@ -1317,11 +1500,9 @@
1.565 /// map have been set false previously.
1.566 template <typename NodeMap>
1.567 Value quickMinCut(NodeMap& nodeMap) const {
1.568 - for (typename Graph::Node it = _first_node;
1.569 - it != _last_node; it = (*_next)[it]) {
1.570 - nodeMap.set(it, true);
1.571 - }
1.572 - nodeMap.set(_last_node, true);
1.573 + for (int i = 0; i < (int)_cut.size(); ++i) {
1.574 + nodeMap.set(_cut[i], true);
1.575 + }
1.576 return minCut();
1.577 }
1.578
1.579 @@ -1355,6 +1536,9 @@
1.580
1.581 ///@}
1.582
1.583 + private:
1.584 +
1.585 +
1.586 };
1.587 }
1.588