lemon/nagamochi_ibaraki.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 22 Dec 2011 20:55:43 +0100
changeset 992 78434a448b5e
parent 913 5087694945e4
child 1092 dceba191c00d
permissions -rw-r--r--
Update INSTALL to use CMAKE. Also update AUTHORS and LICENSE
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     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.
    12  *
    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
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_NAGAMOCHI_IBARAKI_H
    20 #define LEMON_NAGAMOCHI_IBARAKI_H
    21 
    22 
    23 /// \ingroup min_cut
    24 /// \file
    25 /// \brief Implementation of the Nagamochi-Ibaraki algorithm.
    26 
    27 #include <lemon/core.h>
    28 #include <lemon/bin_heap.h>
    29 #include <lemon/bucket_heap.h>
    30 #include <lemon/maps.h>
    31 #include <lemon/radix_sort.h>
    32 #include <lemon/unionfind.h>
    33 
    34 #include <cassert>
    35 
    36 namespace lemon {
    37 
    38   /// \brief Default traits class for NagamochiIbaraki class.
    39   ///
    40   /// Default traits class for NagamochiIbaraki class.
    41   /// \param GR The undirected graph type.
    42   /// \param CM Type of capacity map.
    43   template <typename GR, typename CM>
    44   struct NagamochiIbarakiDefaultTraits {
    45     /// The type of the capacity map.
    46     typedef typename CM::Value Value;
    47 
    48     /// The undirected graph type the algorithm runs on.
    49     typedef GR Graph;
    50 
    51     /// \brief The type of the map that stores the edge capacities.
    52     ///
    53     /// The type of the map that stores the edge capacities.
    54     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    55     typedef CM CapacityMap;
    56 
    57     /// \brief Instantiates a CapacityMap.
    58     ///
    59     /// This function instantiates a \ref CapacityMap.
    60 #ifdef DOXYGEN
    61     static CapacityMap *createCapacityMap(const Graph& graph)
    62 #else
    63     static CapacityMap *createCapacityMap(const Graph&)
    64 #endif
    65     {
    66         LEMON_ASSERT(false, "CapacityMap is not initialized");
    67         return 0; // ignore warnings
    68     }
    69 
    70     /// \brief The cross reference type used by heap.
    71     ///
    72     /// The cross reference type used by heap.
    73     /// Usually \c Graph::NodeMap<int>.
    74     typedef typename Graph::template NodeMap<int> HeapCrossRef;
    75 
    76     /// \brief Instantiates a HeapCrossRef.
    77     ///
    78     /// This function instantiates a \ref HeapCrossRef.
    79     /// \param g is the graph, to which we would like to define the
    80     /// \ref HeapCrossRef.
    81     static HeapCrossRef *createHeapCrossRef(const Graph& g) {
    82       return new HeapCrossRef(g);
    83     }
    84 
    85     /// \brief The heap type used by NagamochiIbaraki algorithm.
    86     ///
    87     /// The heap type used by NagamochiIbaraki algorithm. It has to
    88     /// maximize the priorities.
    89     ///
    90     /// \sa BinHeap
    91     /// \sa NagamochiIbaraki
    92     typedef BinHeap<Value, HeapCrossRef, std::greater<Value> > Heap;
    93 
    94     /// \brief Instantiates a Heap.
    95     ///
    96     /// This function instantiates a \ref Heap.
    97     /// \param r is the cross reference of the heap.
    98     static Heap *createHeap(HeapCrossRef& r) {
    99       return new Heap(r);
   100     }
   101   };
   102 
   103   /// \ingroup min_cut
   104   ///
   105   /// \brief Calculates the minimum cut in an undirected graph.
   106   ///
   107   /// Calculates the minimum cut in an undirected graph with the
   108   /// Nagamochi-Ibaraki algorithm. The algorithm separates the graph's
   109   /// nodes into two partitions with the minimum sum of edge capacities
   110   /// between the two partitions. The algorithm can be used to test
   111   /// the network reliability, especially to test how many links have
   112   /// to be destroyed in the network to split it to at least two
   113   /// distinict subnetworks.
   114   ///
   115   /// The complexity of the algorithm is \f$ O(nm\log(n)) \f$ but with
   116   /// \ref FibHeap "Fibonacci heap" it can be decreased to
   117   /// \f$ O(nm+n^2\log(n)) \f$.  When the edges have unit capacities,
   118   /// \c BucketHeap can be used which yields \f$ O(nm) \f$ time
   119   /// complexity.
   120   ///
   121   /// \warning The value type of the capacity map should be able to
   122   /// hold any cut value of the graph, otherwise the result can
   123   /// overflow.
   124   /// \note This capacity is supposed to be integer type.
   125 #ifdef DOXYGEN
   126   template <typename GR, typename CM, typename TR>
   127 #else
   128   template <typename GR,
   129             typename CM = typename GR::template EdgeMap<int>,
   130             typename TR = NagamochiIbarakiDefaultTraits<GR, CM> >
   131 #endif
   132   class NagamochiIbaraki {
   133   public:
   134 
   135     typedef TR Traits;
   136     /// The type of the underlying graph.
   137     typedef typename Traits::Graph Graph;
   138 
   139     /// The type of the capacity map.
   140     typedef typename Traits::CapacityMap CapacityMap;
   141     /// The value type of the capacity map.
   142     typedef typename Traits::CapacityMap::Value Value;
   143 
   144     /// The heap type used by the algorithm.
   145     typedef typename Traits::Heap Heap;
   146     /// The cross reference type used for the heap.
   147     typedef typename Traits::HeapCrossRef HeapCrossRef;
   148 
   149     ///\name Named template parameters
   150 
   151     ///@{
   152 
   153     struct SetUnitCapacityTraits : public Traits {
   154       typedef ConstMap<typename Graph::Edge, Const<int, 1> > CapacityMap;
   155       static CapacityMap *createCapacityMap(const Graph&) {
   156         return new CapacityMap();
   157       }
   158     };
   159 
   160     /// \brief \ref named-templ-param "Named parameter" for setting
   161     /// the capacity map to a constMap<Edge, int, 1>() instance
   162     ///
   163     /// \ref named-templ-param "Named parameter" for setting
   164     /// the capacity map to a constMap<Edge, int, 1>() instance
   165     struct SetUnitCapacity
   166       : public NagamochiIbaraki<Graph, CapacityMap,
   167                                 SetUnitCapacityTraits> {
   168       typedef NagamochiIbaraki<Graph, CapacityMap,
   169                                SetUnitCapacityTraits> Create;
   170     };
   171 
   172 
   173     template <class H, class CR>
   174     struct SetHeapTraits : public Traits {
   175       typedef CR HeapCrossRef;
   176       typedef H Heap;
   177       static HeapCrossRef *createHeapCrossRef(int num) {
   178         LEMON_ASSERT(false, "HeapCrossRef is not initialized");
   179         return 0; // ignore warnings
   180       }
   181       static Heap *createHeap(HeapCrossRef &) {
   182         LEMON_ASSERT(false, "Heap is not initialized");
   183         return 0; // ignore warnings
   184       }
   185     };
   186 
   187     /// \brief \ref named-templ-param "Named parameter" for setting
   188     /// heap and cross reference type
   189     ///
   190     /// \ref named-templ-param "Named parameter" for setting heap and
   191     /// cross reference type. The heap has to maximize the priorities.
   192     template <class H, class CR = RangeMap<int> >
   193     struct SetHeap
   194       : public NagamochiIbaraki<Graph, CapacityMap, SetHeapTraits<H, CR> > {
   195       typedef NagamochiIbaraki< Graph, CapacityMap, SetHeapTraits<H, CR> >
   196       Create;
   197     };
   198 
   199     template <class H, class CR>
   200     struct SetStandardHeapTraits : public Traits {
   201       typedef CR HeapCrossRef;
   202       typedef H Heap;
   203       static HeapCrossRef *createHeapCrossRef(int size) {
   204         return new HeapCrossRef(size);
   205       }
   206       static Heap *createHeap(HeapCrossRef &crossref) {
   207         return new Heap(crossref);
   208       }
   209     };
   210 
   211     /// \brief \ref named-templ-param "Named parameter" for setting
   212     /// heap and cross reference type with automatic allocation
   213     ///
   214     /// \ref named-templ-param "Named parameter" for setting heap and
   215     /// cross reference type with automatic allocation. They should
   216     /// have standard constructor interfaces to be able to
   217     /// automatically created by the algorithm (i.e. the graph should
   218     /// be passed to the constructor of the cross reference and the
   219     /// cross reference should be passed to the constructor of the
   220     /// heap). However, external heap and cross reference objects
   221     /// could also be passed to the algorithm using the \ref heap()
   222     /// function before calling \ref run() or \ref init(). The heap
   223     /// has to maximize the priorities.
   224     /// \sa SetHeap
   225     template <class H, class CR = RangeMap<int> >
   226     struct SetStandardHeap
   227       : public NagamochiIbaraki<Graph, CapacityMap,
   228                                 SetStandardHeapTraits<H, CR> > {
   229       typedef NagamochiIbaraki<Graph, CapacityMap,
   230                                SetStandardHeapTraits<H, CR> > Create;
   231     };
   232 
   233     ///@}
   234 
   235 
   236   private:
   237 
   238     const Graph &_graph;
   239     const CapacityMap *_capacity;
   240     bool _local_capacity; // unit capacity
   241 
   242     struct ArcData {
   243       typename Graph::Node target;
   244       int prev, next;
   245     };
   246     struct EdgeData {
   247       Value capacity;
   248       Value cut;
   249     };
   250 
   251     struct NodeData {
   252       int first_arc;
   253       typename Graph::Node prev, next;
   254       int curr_arc;
   255       typename Graph::Node last_rep;
   256       Value sum;
   257     };
   258 
   259     typename Graph::template NodeMap<NodeData> *_nodes;
   260     std::vector<ArcData> _arcs;
   261     std::vector<EdgeData> _edges;
   262 
   263     typename Graph::Node _first_node;
   264     int _node_num;
   265 
   266     Value _min_cut;
   267 
   268     HeapCrossRef *_heap_cross_ref;
   269     bool _local_heap_cross_ref;
   270     Heap *_heap;
   271     bool _local_heap;
   272 
   273     typedef typename Graph::template NodeMap<typename Graph::Node> NodeList;
   274     NodeList *_next_rep;
   275 
   276     typedef typename Graph::template NodeMap<bool> MinCutMap;
   277     MinCutMap *_cut_map;
   278 
   279     void createStructures() {
   280       if (!_nodes) {
   281         _nodes = new (typename Graph::template NodeMap<NodeData>)(_graph);
   282       }
   283       if (!_capacity) {
   284         _local_capacity = true;
   285         _capacity = Traits::createCapacityMap(_graph);
   286       }
   287       if (!_heap_cross_ref) {
   288         _local_heap_cross_ref = true;
   289         _heap_cross_ref = Traits::createHeapCrossRef(_graph);
   290       }
   291       if (!_heap) {
   292         _local_heap = true;
   293         _heap = Traits::createHeap(*_heap_cross_ref);
   294       }
   295       if (!_next_rep) {
   296         _next_rep = new NodeList(_graph);
   297       }
   298       if (!_cut_map) {
   299         _cut_map = new MinCutMap(_graph);
   300       }
   301     }
   302 
   303   protected:
   304     //This is here to avoid a gcc-3.3 compilation error.
   305     //It should never be called.
   306     NagamochiIbaraki() {} 
   307     
   308   public:
   309 
   310     typedef NagamochiIbaraki Create;
   311 
   312 
   313     /// \brief Constructor.
   314     ///
   315     /// \param graph The graph the algorithm runs on.
   316     /// \param capacity The capacity map used by the algorithm.
   317     NagamochiIbaraki(const Graph& graph, const CapacityMap& capacity)
   318       : _graph(graph), _capacity(&capacity), _local_capacity(false),
   319         _nodes(0), _arcs(), _edges(), _min_cut(),
   320         _heap_cross_ref(0), _local_heap_cross_ref(false),
   321         _heap(0), _local_heap(false),
   322         _next_rep(0), _cut_map(0) {}
   323 
   324     /// \brief Constructor.
   325     ///
   326     /// This constructor can be used only when the Traits class
   327     /// defines how can the local capacity map be instantiated.
   328     /// If the SetUnitCapacity used the algorithm automatically
   329     /// constructs the capacity map.
   330     ///
   331     ///\param graph The graph the algorithm runs on.
   332     NagamochiIbaraki(const Graph& graph)
   333       : _graph(graph), _capacity(0), _local_capacity(false),
   334         _nodes(0), _arcs(), _edges(), _min_cut(),
   335         _heap_cross_ref(0), _local_heap_cross_ref(false),
   336         _heap(0), _local_heap(false),
   337         _next_rep(0), _cut_map(0) {}
   338 
   339     /// \brief Destructor.
   340     ///
   341     /// Destructor.
   342     ~NagamochiIbaraki() {
   343       if (_local_capacity) delete _capacity;
   344       if (_nodes) delete _nodes;
   345       if (_local_heap) delete _heap;
   346       if (_local_heap_cross_ref) delete _heap_cross_ref;
   347       if (_next_rep) delete _next_rep;
   348       if (_cut_map) delete _cut_map;
   349     }
   350 
   351     /// \brief Sets the heap and the cross reference used by algorithm.
   352     ///
   353     /// Sets the heap and the cross reference used by algorithm.
   354     /// If you don't use this function before calling \ref run(),
   355     /// it will allocate one. The destuctor deallocates this
   356     /// automatically allocated heap and cross reference, of course.
   357     /// \return <tt> (*this) </tt>
   358     NagamochiIbaraki &heap(Heap& hp, HeapCrossRef &cr)
   359     {
   360       if (_local_heap_cross_ref) {
   361         delete _heap_cross_ref;
   362         _local_heap_cross_ref = false;
   363       }
   364       _heap_cross_ref = &cr;
   365       if (_local_heap) {
   366         delete _heap;
   367         _local_heap = false;
   368       }
   369       _heap = &hp;
   370       return *this;
   371     }
   372 
   373     /// \name Execution control
   374     /// The simplest way to execute the algorithm is to use
   375     /// one of the member functions called \c run().
   376     /// \n
   377     /// If you need more control on the execution,
   378     /// first you must call \ref init() and then call the start()
   379     /// or proper times the processNextPhase() member functions.
   380 
   381     ///@{
   382 
   383     /// \brief Initializes the internal data structures.
   384     ///
   385     /// Initializes the internal data structures.
   386     void init() {
   387       createStructures();
   388 
   389       int edge_num = countEdges(_graph);
   390       _edges.resize(edge_num);
   391       _arcs.resize(2 * edge_num);
   392 
   393       typename Graph::Node prev = INVALID;
   394       _node_num = 0;
   395       for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   396         (*_cut_map)[n] = false;
   397         (*_next_rep)[n] = INVALID;
   398         (*_nodes)[n].last_rep = n;
   399         (*_nodes)[n].first_arc = -1;
   400         (*_nodes)[n].curr_arc = -1;
   401         (*_nodes)[n].prev = prev;
   402         if (prev != INVALID) {
   403           (*_nodes)[prev].next = n;
   404         }
   405         (*_nodes)[n].next = INVALID;
   406         (*_nodes)[n].sum = 0;
   407         prev = n;
   408         ++_node_num;
   409       }
   410 
   411       _first_node = typename Graph::NodeIt(_graph);
   412 
   413       int index = 0;
   414       for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   415         for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
   416           typename Graph::Node m = _graph.target(a);
   417           
   418           if (!(n < m)) continue;
   419 
   420           (*_nodes)[n].sum += (*_capacity)[a];
   421           (*_nodes)[m].sum += (*_capacity)[a];
   422           
   423           int c = (*_nodes)[m].curr_arc;
   424           if (c != -1 && _arcs[c ^ 1].target == n) {
   425             _edges[c >> 1].capacity += (*_capacity)[a];
   426           } else {
   427             _edges[index].capacity = (*_capacity)[a];
   428             
   429             _arcs[index << 1].prev = -1;
   430             if ((*_nodes)[n].first_arc != -1) {
   431               _arcs[(*_nodes)[n].first_arc].prev = (index << 1);
   432             }
   433             _arcs[index << 1].next = (*_nodes)[n].first_arc;
   434             (*_nodes)[n].first_arc = (index << 1);
   435             _arcs[index << 1].target = m;
   436 
   437             (*_nodes)[m].curr_arc = (index << 1);
   438             
   439             _arcs[(index << 1) | 1].prev = -1;
   440             if ((*_nodes)[m].first_arc != -1) {
   441               _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1);
   442             }
   443             _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc;
   444             (*_nodes)[m].first_arc = ((index << 1) | 1);
   445             _arcs[(index << 1) | 1].target = n;
   446             
   447             ++index;
   448           }
   449         }
   450       }
   451 
   452       typename Graph::Node cut_node = INVALID;
   453       _min_cut = std::numeric_limits<Value>::max();
   454 
   455       for (typename Graph::Node n = _first_node; 
   456            n != INVALID; n = (*_nodes)[n].next) {
   457         if ((*_nodes)[n].sum < _min_cut) {
   458           cut_node = n;
   459           _min_cut = (*_nodes)[n].sum;
   460         }
   461       }
   462       (*_cut_map)[cut_node] = true;
   463       if (_min_cut == 0) {
   464         _first_node = INVALID;
   465       }
   466     }
   467 
   468   public:
   469 
   470     /// \brief Processes the next phase
   471     ///
   472     /// Processes the next phase in the algorithm. It must be called
   473     /// at most one less the number of the nodes in the graph.
   474     ///
   475     ///\return %True when the algorithm finished.
   476     bool processNextPhase() {
   477       if (_first_node == INVALID) return true;
   478 
   479       _heap->clear();
   480       for (typename Graph::Node n = _first_node; 
   481            n != INVALID; n = (*_nodes)[n].next) {
   482         (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
   483       }
   484 
   485       std::vector<typename Graph::Node> order;
   486       order.reserve(_node_num);
   487       int sep = 0;
   488 
   489       Value alpha = 0;
   490       Value pmc = std::numeric_limits<Value>::max();
   491 
   492       _heap->push(_first_node, static_cast<Value>(0));
   493       while (!_heap->empty()) {
   494         typename Graph::Node n = _heap->top();
   495         Value v = _heap->prio();
   496 
   497         _heap->pop();
   498         for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
   499           switch (_heap->state(_arcs[a].target)) {
   500           case Heap::PRE_HEAP: 
   501             {
   502               Value nv = _edges[a >> 1].capacity;
   503               _heap->push(_arcs[a].target, nv);
   504               _edges[a >> 1].cut = nv;
   505             } break;
   506           case Heap::IN_HEAP:
   507             {
   508               Value nv = _edges[a >> 1].capacity + (*_heap)[_arcs[a].target];
   509               _heap->decrease(_arcs[a].target, nv);
   510               _edges[a >> 1].cut = nv;
   511             } break;
   512           case Heap::POST_HEAP:
   513             break;
   514           }
   515         }
   516 
   517         alpha += (*_nodes)[n].sum;
   518         alpha -= 2 * v;
   519 
   520         order.push_back(n);
   521         if (!_heap->empty()) {
   522           if (alpha < pmc) {
   523             pmc = alpha;
   524             sep = order.size();
   525           }
   526         }
   527       }
   528 
   529       if (static_cast<int>(order.size()) < _node_num) {
   530         _first_node = INVALID;
   531         for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   532           (*_cut_map)[n] = false;
   533         }
   534         for (int i = 0; i < static_cast<int>(order.size()); ++i) {
   535           typename Graph::Node n = order[i];
   536           while (n != INVALID) {
   537             (*_cut_map)[n] = true;
   538             n = (*_next_rep)[n];
   539           }
   540         }
   541         _min_cut = 0;
   542         return true;
   543       }
   544 
   545       if (pmc < _min_cut) {
   546         for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   547           (*_cut_map)[n] = false;
   548         }
   549         for (int i = 0; i < sep; ++i) {
   550           typename Graph::Node n = order[i];
   551           while (n != INVALID) {
   552             (*_cut_map)[n] = true;
   553             n = (*_next_rep)[n];
   554           }
   555         }
   556         _min_cut = pmc;
   557       }
   558 
   559       for (typename Graph::Node n = _first_node;
   560            n != INVALID; n = (*_nodes)[n].next) {
   561         bool merged = false;
   562         for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
   563           if (!(_edges[a >> 1].cut < pmc)) {
   564             if (!merged) {
   565               for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
   566                 (*_nodes)[_arcs[b].target].curr_arc = b;          
   567               }
   568               merged = true;
   569             }
   570             typename Graph::Node m = _arcs[a].target;
   571             int nb = 0;
   572             for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) {
   573               nb = _arcs[b].next;
   574               if ((b ^ a) == 1) continue;
   575               typename Graph::Node o = _arcs[b].target;
   576               int c = (*_nodes)[o].curr_arc; 
   577               if (c != -1 && _arcs[c ^ 1].target == n) {
   578                 _edges[c >> 1].capacity += _edges[b >> 1].capacity;
   579                 (*_nodes)[n].sum += _edges[b >> 1].capacity;
   580                 if (_edges[b >> 1].cut < _edges[c >> 1].cut) {
   581                   _edges[b >> 1].cut = _edges[c >> 1].cut;
   582                 }
   583                 if (_arcs[b ^ 1].prev != -1) {
   584                   _arcs[_arcs[b ^ 1].prev].next = _arcs[b ^ 1].next;
   585                 } else {
   586                   (*_nodes)[o].first_arc = _arcs[b ^ 1].next;
   587                 }
   588                 if (_arcs[b ^ 1].next != -1) {
   589                   _arcs[_arcs[b ^ 1].next].prev = _arcs[b ^ 1].prev;
   590                 }
   591               } else {
   592                 if (_arcs[a].next != -1) {
   593                   _arcs[_arcs[a].next].prev = b;
   594                 }
   595                 _arcs[b].next = _arcs[a].next;
   596                 _arcs[b].prev = a;
   597                 _arcs[a].next = b;
   598                 _arcs[b ^ 1].target = n;
   599 
   600                 (*_nodes)[n].sum += _edges[b >> 1].capacity;
   601                 (*_nodes)[o].curr_arc = b;
   602               }
   603             }
   604 
   605             if (_arcs[a].prev != -1) {
   606               _arcs[_arcs[a].prev].next = _arcs[a].next;
   607             } else {
   608               (*_nodes)[n].first_arc = _arcs[a].next;
   609             }            
   610             if (_arcs[a].next != -1) {
   611               _arcs[_arcs[a].next].prev = _arcs[a].prev;
   612             }
   613 
   614             (*_nodes)[n].sum -= _edges[a >> 1].capacity;
   615             (*_next_rep)[(*_nodes)[n].last_rep] = m;
   616             (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
   617             
   618             if ((*_nodes)[m].prev != INVALID) {
   619               (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
   620             } else{
   621               _first_node = (*_nodes)[m].next;
   622             }
   623             if ((*_nodes)[m].next != INVALID) {
   624               (*_nodes)[(*_nodes)[m].next].prev = (*_nodes)[m].prev;
   625             }
   626             --_node_num;
   627           }
   628         }
   629       }
   630 
   631       if (_node_num == 1) {
   632         _first_node = INVALID;
   633         return true;
   634       }
   635 
   636       return false;
   637     }
   638 
   639     /// \brief Executes the algorithm.
   640     ///
   641     /// Executes the algorithm.
   642     ///
   643     /// \pre init() must be called
   644     void start() {
   645       while (!processNextPhase()) {}
   646     }
   647 
   648 
   649     /// \brief Runs %NagamochiIbaraki algorithm.
   650     ///
   651     /// This method runs the %Min cut algorithm
   652     ///
   653     /// \note mc.run(s) is just a shortcut of the following code.
   654     ///\code
   655     ///  mc.init();
   656     ///  mc.start();
   657     ///\endcode
   658     void run() {
   659       init();
   660       start();
   661     }
   662 
   663     ///@}
   664 
   665     /// \name Query Functions
   666     ///
   667     /// The result of the %NagamochiIbaraki
   668     /// algorithm can be obtained using these functions.\n
   669     /// Before the use of these functions, either run() or start()
   670     /// must be called.
   671 
   672     ///@{
   673 
   674     /// \brief Returns the min cut value.
   675     ///
   676     /// Returns the min cut value if the algorithm finished.
   677     /// After the first processNextPhase() it is a value of a
   678     /// valid cut in the graph.
   679     Value minCutValue() const {
   680       return _min_cut;
   681     }
   682 
   683     /// \brief Returns a min cut in a NodeMap.
   684     ///
   685     /// It sets the nodes of one of the two partitions to true and
   686     /// the other partition to false.
   687     /// \param cutMap A \ref concepts::WriteMap "writable" node map with
   688     /// \c bool (or convertible) value type.
   689     template <typename CutMap>
   690     Value minCutMap(CutMap& cutMap) const {
   691       for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
   692         cutMap.set(n, (*_cut_map)[n]);
   693       }
   694       return minCutValue();
   695     }
   696 
   697     ///@}
   698 
   699   };
   700 }
   701 
   702 #endif