1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_PREFLOW_H
20 #define LEMON_PREFLOW_H
22 #include <lemon/tolerance.h>
23 #include <lemon/elevator.h>
27 /// \brief Implementation of the preflow algorithm.
31 /// \brief Default traits class of Preflow class.
33 /// Default traits class of Preflow class.
34 /// \tparam GR Digraph type.
35 /// \tparam CAP Capacity map type.
36 template <typename GR, typename CAP>
37 struct PreflowDefaultTraits {
39 /// \brief The type of the digraph the algorithm runs on.
42 /// \brief The type of the map that stores the arc capacities.
44 /// The type of the map that stores the arc capacities.
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
46 typedef CAP CapacityMap;
48 /// \brief The type of the flow values.
49 typedef typename CapacityMap::Value Value;
51 /// \brief The type of the map that stores the flow values.
53 /// The type of the map that stores the flow values.
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
56 typedef GR::ArcMap<Value> FlowMap;
58 typedef typename Digraph::template ArcMap<Value> FlowMap;
61 /// \brief Instantiates a FlowMap.
63 /// This function instantiates a \ref FlowMap.
64 /// \param digraph The digraph for which we would like to define
66 static FlowMap* createFlowMap(const Digraph& digraph) {
67 return new FlowMap(digraph);
70 /// \brief The elevator type used by Preflow algorithm.
72 /// The elevator type used by Preflow algorithm.
74 /// \sa Elevator, LinkedElevator
76 typedef lemon::Elevator<GR, GR::Node> Elevator;
78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
81 /// \brief Instantiates an Elevator.
83 /// This function instantiates an \ref Elevator.
84 /// \param digraph The digraph for which we would like to define
86 /// \param max_level The maximum level of the elevator.
87 static Elevator* createElevator(const Digraph& digraph, int max_level) {
88 return new Elevator(digraph, max_level);
91 /// \brief The tolerance used by the algorithm
93 /// The tolerance used by the algorithm to handle inexact computation.
94 typedef lemon::Tolerance<Value> Tolerance;
101 /// \brief %Preflow algorithm class.
103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow
104 /// \e push-relabel algorithm producing a \ref max_flow
105 /// "flow of maximum value" in a digraph \ref clrs01algorithms,
106 /// \ref amo93networkflows, \ref goldberg88newapproach.
107 /// The preflow algorithms are the fastest known maximum
108 /// flow algorithms. The current implementation uses a mixture of the
109 /// \e "highest label" and the \e "bound decrease" heuristics.
110 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
112 /// The algorithm consists of two phases. After the first phase
113 /// the maximum flow value and the minimum cut is obtained. The
114 /// second phase constructs a feasible maximum flow on each arc.
116 /// \warning This implementation cannot handle infinite or very large
117 /// capacities (e.g. the maximum value of \c CAP::Value).
119 /// \tparam GR The type of the digraph the algorithm runs on.
120 /// \tparam CAP The type of the capacity map. The default map
121 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
122 /// \tparam TR The traits class that defines various types used by the
123 /// algorithm. By default, it is \ref PreflowDefaultTraits
124 /// "PreflowDefaultTraits<GR, CAP>".
125 /// In most cases, this parameter should not be set directly,
126 /// consider to use the named template parameters instead.
128 template <typename GR, typename CAP, typename TR>
130 template <typename GR,
131 typename CAP = typename GR::template ArcMap<int>,
132 typename TR = PreflowDefaultTraits<GR, CAP> >
137 ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
139 ///The type of the digraph the algorithm runs on.
140 typedef typename Traits::Digraph Digraph;
141 ///The type of the capacity map.
142 typedef typename Traits::CapacityMap CapacityMap;
143 ///The type of the flow values.
144 typedef typename Traits::Value Value;
146 ///The type of the flow map.
147 typedef typename Traits::FlowMap FlowMap;
148 ///The type of the elevator.
149 typedef typename Traits::Elevator Elevator;
150 ///The type of the tolerance.
151 typedef typename Traits::Tolerance Tolerance;
155 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
157 const Digraph& _graph;
158 const CapacityMap* _capacity;
162 Node _source, _target;
170 typedef typename Digraph::template NodeMap<Value> ExcessMap;
173 Tolerance _tolerance;
178 void createStructures() {
179 _node_num = countNodes(_graph);
182 _flow = Traits::createFlowMap(_graph);
186 _level = Traits::createElevator(_graph, _node_num);
190 _excess = new ExcessMap(_graph);
194 void destroyStructures() {
208 typedef Preflow Create;
210 ///\name Named Template Parameters
214 template <typename T>
215 struct SetFlowMapTraits : public Traits {
217 static FlowMap *createFlowMap(const Digraph&) {
218 LEMON_ASSERT(false, "FlowMap is not initialized");
219 return 0; // ignore warnings
223 /// \brief \ref named-templ-param "Named parameter" for setting
226 /// \ref named-templ-param "Named parameter" for setting FlowMap
228 template <typename T>
230 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
231 typedef Preflow<Digraph, CapacityMap,
232 SetFlowMapTraits<T> > Create;
235 template <typename T>
236 struct SetElevatorTraits : public Traits {
238 static Elevator *createElevator(const Digraph&, int) {
239 LEMON_ASSERT(false, "Elevator is not initialized");
240 return 0; // ignore warnings
244 /// \brief \ref named-templ-param "Named parameter" for setting
247 /// \ref named-templ-param "Named parameter" for setting Elevator
248 /// type. If this named parameter is used, then an external
249 /// elevator object must be passed to the algorithm using the
250 /// \ref elevator(Elevator&) "elevator()" function before calling
251 /// \ref run() or \ref init().
252 /// \sa SetStandardElevator
253 template <typename T>
255 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
256 typedef Preflow<Digraph, CapacityMap,
257 SetElevatorTraits<T> > Create;
260 template <typename T>
261 struct SetStandardElevatorTraits : public Traits {
263 static Elevator *createElevator(const Digraph& digraph, int max_level) {
264 return new Elevator(digraph, max_level);
268 /// \brief \ref named-templ-param "Named parameter" for setting
269 /// Elevator type with automatic allocation
271 /// \ref named-templ-param "Named parameter" for setting Elevator
272 /// type with automatic allocation.
273 /// The Elevator should have standard constructor interface to be
274 /// able to automatically created by the algorithm (i.e. the
275 /// digraph and the maximum level should be passed to it).
276 /// However, an external elevator object could also be passed to the
277 /// algorithm with the \ref elevator(Elevator&) "elevator()" function
278 /// before calling \ref run() or \ref init().
280 template <typename T>
281 struct SetStandardElevator
282 : public Preflow<Digraph, CapacityMap,
283 SetStandardElevatorTraits<T> > {
284 typedef Preflow<Digraph, CapacityMap,
285 SetStandardElevatorTraits<T> > Create;
297 /// \brief The constructor of the class.
299 /// The constructor of the class.
300 /// \param digraph The digraph the algorithm runs on.
301 /// \param capacity The capacity of the arcs.
302 /// \param source The source node.
303 /// \param target The target node.
304 Preflow(const Digraph& digraph, const CapacityMap& capacity,
305 Node source, Node target)
306 : _graph(digraph), _capacity(&capacity),
307 _node_num(0), _source(source), _target(target),
308 _flow(0), _local_flow(false),
309 _level(0), _local_level(false),
310 _excess(0), _tolerance(), _phase() {}
312 /// \brief Destructor.
319 /// \brief Sets the capacity map.
321 /// Sets the capacity map.
322 /// \return <tt>(*this)</tt>
323 Preflow& capacityMap(const CapacityMap& map) {
328 /// \brief Sets the flow map.
330 /// Sets the flow map.
331 /// If you don't use this function before calling \ref run() or
332 /// \ref init(), an instance will be allocated automatically.
333 /// The destructor deallocates this automatically allocated map,
335 /// \return <tt>(*this)</tt>
336 Preflow& flowMap(FlowMap& map) {
345 /// \brief Sets the source node.
347 /// Sets the source node.
348 /// \return <tt>(*this)</tt>
349 Preflow& source(const Node& node) {
354 /// \brief Sets the target node.
356 /// Sets the target node.
357 /// \return <tt>(*this)</tt>
358 Preflow& target(const Node& node) {
363 /// \brief Sets the elevator used by algorithm.
365 /// Sets the elevator used by algorithm.
366 /// If you don't use this function before calling \ref run() or
367 /// \ref init(), an instance will be allocated automatically.
368 /// The destructor deallocates this automatically allocated elevator,
370 /// \return <tt>(*this)</tt>
371 Preflow& elevator(Elevator& elevator) {
374 _local_level = false;
380 /// \brief Returns a const reference to the elevator.
382 /// Returns a const reference to the elevator.
384 /// \pre Either \ref run() or \ref init() must be called before
385 /// using this function.
386 const Elevator& elevator() const {
390 /// \brief Sets the tolerance used by the algorithm.
392 /// Sets the tolerance object used by the algorithm.
393 /// \return <tt>(*this)</tt>
394 Preflow& tolerance(const Tolerance& tolerance) {
395 _tolerance = tolerance;
399 /// \brief Returns a const reference to the tolerance.
401 /// Returns a const reference to the tolerance object used by
403 const Tolerance& tolerance() const {
407 /// \name Execution Control
408 /// The simplest way to execute the preflow algorithm is to use
409 /// \ref run() or \ref runMinCut().\n
410 /// If you need better control on the initial solution or the execution,
411 /// you have to call one of the \ref init() functions first, then
412 /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
416 /// \brief Initializes the internal data structures.
418 /// Initializes the internal data structures and sets the initial
419 /// flow to zero on each arc.
424 for (NodeIt n(_graph); n != INVALID; ++n) {
428 for (ArcIt e(_graph); e != INVALID; ++e) {
432 typename Digraph::template NodeMap<bool> reached(_graph, false);
435 _level->initAddItem(_target);
437 std::vector<Node> queue;
438 reached[_source] = true;
440 queue.push_back(_target);
441 reached[_target] = true;
442 while (!queue.empty()) {
443 _level->initNewLevel();
444 std::vector<Node> nqueue;
445 for (int i = 0; i < int(queue.size()); ++i) {
447 for (InArcIt e(_graph, n); e != INVALID; ++e) {
448 Node u = _graph.source(e);
449 if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
451 _level->initAddItem(u);
458 _level->initFinish();
460 for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
461 if (_tolerance.positive((*_capacity)[e])) {
462 Node u = _graph.target(e);
463 if ((*_level)[u] == _level->maxLevel()) continue;
464 _flow->set(e, (*_capacity)[e]);
465 (*_excess)[u] += (*_capacity)[e];
466 if (u != _target && !_level->active(u)) {
473 /// \brief Initializes the internal data structures using the
476 /// Initializes the internal data structures and sets the initial
477 /// flow to the given \c flowMap. The \c flowMap should contain a
478 /// flow or at least a preflow, i.e. at each node excluding the
479 /// source node the incoming flow should greater or equal to the
481 /// \return \c false if the given \c flowMap is not a preflow.
482 template <typename FlowMap>
483 bool init(const FlowMap& flowMap) {
486 for (ArcIt e(_graph); e != INVALID; ++e) {
487 _flow->set(e, flowMap[e]);
490 for (NodeIt n(_graph); n != INVALID; ++n) {
492 for (InArcIt e(_graph, n); e != INVALID; ++e) {
493 excess += (*_flow)[e];
495 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
496 excess -= (*_flow)[e];
498 if (excess < 0 && n != _source) return false;
499 (*_excess)[n] = excess;
502 typename Digraph::template NodeMap<bool> reached(_graph, false);
505 _level->initAddItem(_target);
507 std::vector<Node> queue;
508 reached[_source] = true;
510 queue.push_back(_target);
511 reached[_target] = true;
512 while (!queue.empty()) {
513 _level->initNewLevel();
514 std::vector<Node> nqueue;
515 for (int i = 0; i < int(queue.size()); ++i) {
517 for (InArcIt e(_graph, n); e != INVALID; ++e) {
518 Node u = _graph.source(e);
520 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
522 _level->initAddItem(u);
526 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
527 Node v = _graph.target(e);
528 if (!reached[v] && _tolerance.positive((*_flow)[e])) {
530 _level->initAddItem(v);
537 _level->initFinish();
539 for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
540 Value rem = (*_capacity)[e] - (*_flow)[e];
541 if (_tolerance.positive(rem)) {
542 Node u = _graph.target(e);
543 if ((*_level)[u] == _level->maxLevel()) continue;
544 _flow->set(e, (*_capacity)[e]);
545 (*_excess)[u] += rem;
546 if (u != _target && !_level->active(u)) {
551 for (InArcIt e(_graph, _source); e != INVALID; ++e) {
552 Value rem = (*_flow)[e];
553 if (_tolerance.positive(rem)) {
554 Node v = _graph.source(e);
555 if ((*_level)[v] == _level->maxLevel()) continue;
557 (*_excess)[v] += rem;
558 if (v != _target && !_level->active(v)) {
566 /// \brief Starts the first phase of the preflow algorithm.
568 /// The preflow algorithm consists of two phases, this method runs
569 /// the first phase. After the first phase the maximum flow value
570 /// and a minimum value cut can already be computed, although a
571 /// maximum flow is not yet obtained. So after calling this method
572 /// \ref flowValue() returns the value of a maximum flow and \ref
573 /// minCut() returns a minimum cut.
574 /// \pre One of the \ref init() functions must be called before
575 /// using this function.
576 void startFirstPhase() {
586 n = _level->highestActive();
587 if (n == INVALID) goto first_phase_done;
588 level = _level->highestActiveLevel();
591 Value excess = (*_excess)[n];
592 int new_level = _level->maxLevel();
594 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
595 Value rem = (*_capacity)[e] - (*_flow)[e];
596 if (!_tolerance.positive(rem)) continue;
597 Node v = _graph.target(e);
598 if ((*_level)[v] < level) {
599 if (!_level->active(v) && v != _target) {
602 if (!_tolerance.less(rem, excess)) {
603 _flow->set(e, (*_flow)[e] + excess);
604 (*_excess)[v] += excess;
609 (*_excess)[v] += rem;
610 _flow->set(e, (*_capacity)[e]);
612 } else if (new_level > (*_level)[v]) {
613 new_level = (*_level)[v];
617 for (InArcIt e(_graph, n); e != INVALID; ++e) {
618 Value rem = (*_flow)[e];
619 if (!_tolerance.positive(rem)) continue;
620 Node v = _graph.source(e);
621 if ((*_level)[v] < level) {
622 if (!_level->active(v) && v != _target) {
625 if (!_tolerance.less(rem, excess)) {
626 _flow->set(e, (*_flow)[e] - excess);
627 (*_excess)[v] += excess;
632 (*_excess)[v] += rem;
635 } else if (new_level > (*_level)[v]) {
636 new_level = (*_level)[v];
642 (*_excess)[n] = excess;
645 if (new_level + 1 < _level->maxLevel()) {
646 _level->liftHighestActive(new_level + 1);
648 _level->liftHighestActiveToTop();
650 if (_level->emptyLevel(level)) {
651 _level->liftToTop(level);
654 _level->deactivate(n);
658 num = _node_num * 20;
660 while (level >= 0 && _level->activeFree(level)) {
664 n = _level->highestActive();
665 level = _level->highestActiveLevel();
666 if (n == INVALID) goto first_phase_done;
668 n = _level->activeOn(level);
672 Value excess = (*_excess)[n];
673 int new_level = _level->maxLevel();
675 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
676 Value rem = (*_capacity)[e] - (*_flow)[e];
677 if (!_tolerance.positive(rem)) continue;
678 Node v = _graph.target(e);
679 if ((*_level)[v] < level) {
680 if (!_level->active(v) && v != _target) {
683 if (!_tolerance.less(rem, excess)) {
684 _flow->set(e, (*_flow)[e] + excess);
685 (*_excess)[v] += excess;
690 (*_excess)[v] += rem;
691 _flow->set(e, (*_capacity)[e]);
693 } else if (new_level > (*_level)[v]) {
694 new_level = (*_level)[v];
698 for (InArcIt e(_graph, n); e != INVALID; ++e) {
699 Value rem = (*_flow)[e];
700 if (!_tolerance.positive(rem)) continue;
701 Node v = _graph.source(e);
702 if ((*_level)[v] < level) {
703 if (!_level->active(v) && v != _target) {
706 if (!_tolerance.less(rem, excess)) {
707 _flow->set(e, (*_flow)[e] - excess);
708 (*_excess)[v] += excess;
713 (*_excess)[v] += rem;
716 } else if (new_level > (*_level)[v]) {
717 new_level = (*_level)[v];
723 (*_excess)[n] = excess;
726 if (new_level + 1 < _level->maxLevel()) {
727 _level->liftActiveOn(level, new_level + 1);
729 _level->liftActiveToTop(level);
731 if (_level->emptyLevel(level)) {
732 _level->liftToTop(level);
735 _level->deactivate(n);
742 /// \brief Starts the second phase of the preflow algorithm.
744 /// The preflow algorithm consists of two phases, this method runs
745 /// the second phase. After calling one of the \ref init() functions
746 /// and \ref startFirstPhase() and then \ref startSecondPhase(),
747 /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
748 /// value of a maximum flow, \ref minCut() returns a minimum cut
749 /// \pre One of the \ref init() functions and \ref startFirstPhase()
750 /// must be called before using this function.
751 void startSecondPhase() {
754 typename Digraph::template NodeMap<bool> reached(_graph);
755 for (NodeIt n(_graph); n != INVALID; ++n) {
756 reached[n] = (*_level)[n] < _level->maxLevel();
760 _level->initAddItem(_source);
762 std::vector<Node> queue;
763 queue.push_back(_source);
764 reached[_source] = true;
766 while (!queue.empty()) {
767 _level->initNewLevel();
768 std::vector<Node> nqueue;
769 for (int i = 0; i < int(queue.size()); ++i) {
771 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
772 Node v = _graph.target(e);
773 if (!reached[v] && _tolerance.positive((*_flow)[e])) {
775 _level->initAddItem(v);
779 for (InArcIt e(_graph, n); e != INVALID; ++e) {
780 Node u = _graph.source(e);
782 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
784 _level->initAddItem(u);
791 _level->initFinish();
793 for (NodeIt n(_graph); n != INVALID; ++n) {
795 _level->dirtyTopButOne(n);
796 } else if ((*_excess)[n] > 0 && _target != n) {
802 while ((n = _level->highestActive()) != INVALID) {
803 Value excess = (*_excess)[n];
804 int level = _level->highestActiveLevel();
805 int new_level = _level->maxLevel();
807 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
808 Value rem = (*_capacity)[e] - (*_flow)[e];
809 if (!_tolerance.positive(rem)) continue;
810 Node v = _graph.target(e);
811 if ((*_level)[v] < level) {
812 if (!_level->active(v) && v != _source) {
815 if (!_tolerance.less(rem, excess)) {
816 _flow->set(e, (*_flow)[e] + excess);
817 (*_excess)[v] += excess;
822 (*_excess)[v] += rem;
823 _flow->set(e, (*_capacity)[e]);
825 } else if (new_level > (*_level)[v]) {
826 new_level = (*_level)[v];
830 for (InArcIt e(_graph, n); e != INVALID; ++e) {
831 Value rem = (*_flow)[e];
832 if (!_tolerance.positive(rem)) continue;
833 Node v = _graph.source(e);
834 if ((*_level)[v] < level) {
835 if (!_level->active(v) && v != _source) {
838 if (!_tolerance.less(rem, excess)) {
839 _flow->set(e, (*_flow)[e] - excess);
840 (*_excess)[v] += excess;
845 (*_excess)[v] += rem;
848 } else if (new_level > (*_level)[v]) {
849 new_level = (*_level)[v];
855 (*_excess)[n] = excess;
858 if (new_level + 1 < _level->maxLevel()) {
859 _level->liftHighestActive(new_level + 1);
862 _level->liftHighestActiveToTop();
864 if (_level->emptyLevel(level)) {
866 _level->liftToTop(level);
869 _level->deactivate(n);
875 /// \brief Runs the preflow algorithm.
877 /// Runs the preflow algorithm.
878 /// \note pf.run() is just a shortcut of the following code.
881 /// pf.startFirstPhase();
882 /// pf.startSecondPhase();
890 /// \brief Runs the preflow algorithm to compute the minimum cut.
892 /// Runs the preflow algorithm to compute the minimum cut.
893 /// \note pf.runMinCut() is just a shortcut of the following code.
896 /// pf.startFirstPhase();
905 /// \name Query Functions
906 /// The results of the preflow algorithm can be obtained using these
908 /// Either one of the \ref run() "run*()" functions or one of the
909 /// \ref startFirstPhase() "start*()" functions should be called
910 /// before using them.
914 /// \brief Returns the value of the maximum flow.
916 /// Returns the value of the maximum flow by returning the excess
917 /// of the target node. This value equals to the value of
918 /// the maximum flow already after the first phase of the algorithm.
920 /// \pre Either \ref run() or \ref init() must be called before
921 /// using this function.
922 Value flowValue() const {
923 return (*_excess)[_target];
926 /// \brief Returns the flow value on the given arc.
928 /// Returns the flow value on the given arc. This method can
929 /// be called after the second phase of the algorithm.
931 /// \pre Either \ref run() or \ref init() must be called before
932 /// using this function.
933 Value flow(const Arc& arc) const {
934 return (*_flow)[arc];
937 /// \brief Returns a const reference to the flow map.
939 /// Returns a const reference to the arc map storing the found flow.
940 /// This method can be called after the second phase of the algorithm.
942 /// \pre Either \ref run() or \ref init() must be called before
943 /// using this function.
944 const FlowMap& flowMap() const {
948 /// \brief Returns \c true when the node is on the source side of the
951 /// Returns true when the node is on the source side of the found
952 /// minimum cut. This method can be called both after running \ref
953 /// startFirstPhase() and \ref startSecondPhase().
955 /// \pre Either \ref run() or \ref init() must be called before
956 /// using this function.
957 bool minCut(const Node& node) const {
958 return ((*_level)[node] == _level->maxLevel()) == _phase;
961 /// \brief Gives back a minimum value cut.
963 /// Sets \c cutMap to the characteristic vector of a minimum value
964 /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
965 /// node map with \c bool (or convertible) value type.
967 /// This method can be called both after running \ref startFirstPhase()
968 /// and \ref startSecondPhase(). The result after the second phase
969 /// could be slightly different if inexact computation is used.
971 /// \note This function calls \ref minCut() for each node, so it runs in
974 /// \pre Either \ref run() or \ref init() must be called before
975 /// using this function.
976 template <typename CutMap>
977 void minCutMap(CutMap& cutMap) const {
978 for (NodeIt n(_graph); n != INVALID; ++n) {
979 cutMap.set(n, minCut(n));