lemon/min_cut.h
author klao
Wed, 31 May 2006 16:48:31 +0000
changeset 2099 eb126f29038c
parent 2042 bdc953f2a449
child 2111 ea1fa1bc3f6d
permissions -rw-r--r--
benchmark: radix_sort-bench was not compiled
     1 /* -*- C++ -*-
     2  * lemon/min_cut.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_MIN_CUT_H
    18 #define LEMON_MIN_CUT_H
    19 
    20 
    21 /// \ingroup topology
    22 /// \file
    23 /// \brief Maximum cardinality search and min cut in undirected graphs.
    24 
    25 #include <lemon/list_graph.h>
    26 #include <lemon/bin_heap.h>
    27 #include <lemon/bucket_heap.h>
    28 
    29 #include <lemon/bits/invalid.h>
    30 #include <lemon/error.h>
    31 #include <lemon/maps.h>
    32 
    33 #include <functional>
    34 
    35 namespace lemon {
    36 
    37   namespace _min_cut_bits {
    38 
    39     template <typename CapacityMap>
    40     struct HeapSelector {
    41       template <typename Key, typename Value, typename Ref>
    42       struct Selector {
    43         typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
    44       };
    45     };
    46 
    47     template <typename CapacityKey>
    48     struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
    49       template <typename Key, typename Value, typename Ref>
    50       struct Selector {
    51         typedef BucketHeap<Key, Ref, false > Heap;
    52       };
    53     };
    54 
    55   }
    56 
    57   /// \brief Default traits class of MaxCardinalitySearch class.
    58   ///
    59   /// Default traits class of MaxCardinalitySearch class.
    60   /// \param Graph Graph type.
    61   /// \param CapacityMap Type of length map.
    62   template <typename _Graph, typename _CapacityMap>
    63   struct MaxCardinalitySearchDefaultTraits {
    64     /// The graph type the algorithm runs on. 
    65     typedef _Graph Graph;
    66 
    67     /// \brief The type of the map that stores the edge capacities.
    68     ///
    69     /// The type of the map that stores the edge capacities.
    70     /// It must meet the \ref concept::ReadMap "ReadMap" concept.
    71     typedef _CapacityMap CapacityMap;
    72 
    73     /// \brief The type of the capacity of the edges.
    74     typedef typename CapacityMap::Value Value;
    75 
    76     /// \brief The cross reference type used by heap.
    77     ///
    78     /// The cross reference type used by heap.
    79     /// Usually it is \c Graph::NodeMap<int>.
    80     typedef typename Graph::template NodeMap<int> HeapCrossRef;
    81 
    82     /// \brief Instantiates a HeapCrossRef.
    83     ///
    84     /// This function instantiates a \ref HeapCrossRef. 
    85     /// \param graph is the graph, to which we would like to define the 
    86     /// HeapCrossRef.
    87     static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
    88       return new HeapCrossRef(graph);
    89     }
    90     
    91     /// \brief The heap type used by MaxCardinalitySearch algorithm.
    92     ///
    93     /// The heap type used by MaxCardinalitySearch algorithm. It should
    94     /// maximalize the priorities. The default heap type is
    95     /// the \ref BinHeap, but it is specialized when the
    96     /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
    97     /// to BucketHeap.
    98     ///
    99     /// \sa MaxCardinalitySearch
   100     typedef typename _min_cut_bits
   101     ::HeapSelector<CapacityMap>
   102     ::template Selector<typename Graph::Node, Value, HeapCrossRef>
   103     ::Heap Heap;
   104 
   105     /// \brief Instantiates a Heap.
   106     ///
   107     /// This function instantiates a \ref Heap. 
   108     /// \param crossref The cross reference of the heap.
   109     static Heap *createHeap(HeapCrossRef& crossref) {
   110       return new Heap(crossref);
   111     }
   112 
   113     /// \brief The type of the map that stores whether a nodes is processed.
   114     ///
   115     /// The type of the map that stores whether a nodes is processed.
   116     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   117     /// By default it is a NullMap.
   118     typedef NullMap<typename Graph::Node, bool> ProcessedMap;
   119 
   120     /// \brief Instantiates a ProcessedMap.
   121     ///
   122     /// This function instantiates a \ref ProcessedMap. 
   123     /// \param graph is the graph, to which
   124     /// we would like to define the \ref ProcessedMap
   125 #ifdef DOXYGEN
   126     static ProcessedMap *createProcessedMap(const Graph &graph)
   127 #else
   128     static ProcessedMap *createProcessedMap(const Graph &)
   129 #endif
   130     {
   131       return new ProcessedMap();
   132     }
   133 
   134     /// \brief The type of the map that stores the cardinalties of the nodes.
   135     /// 
   136     /// The type of the map that stores the cardinalities of the nodes.
   137     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   138     typedef typename Graph::template NodeMap<Value> CardinalityMap;
   139 
   140     /// \brief Instantiates a CardinalityMap.
   141     ///
   142     /// This function instantiates a \ref CardinalityMap. 
   143     /// \param graph is the graph, to which we would like to define the \ref 
   144     /// CardinalityMap
   145     static CardinalityMap *createCardinalityMap(const Graph &graph) {
   146       return new CardinalityMap(graph);
   147     }
   148 
   149   };
   150   
   151   /// \ingroup topology
   152   ///
   153   /// \brief Maximum Cardinality Search algorithm class.
   154   ///
   155   /// This class provides an efficient implementation of Maximum Cardinality 
   156   /// Search algorithm. The maximum cardinality search chooses first time any 
   157   /// node of the graph. Then every time it chooses the node which is connected
   158   /// to the processed nodes at most in the sum of capacities on the out 
   159   /// edges. If there is a cut in the graph the algorithm should choose
   160   /// again any unprocessed node of the graph. Each node cardinality is
   161   /// the sum of capacities on the out edges to the nodes which are processed
   162   /// before the given node.
   163   ///
   164   /// The edge capacities are passed to the algorithm using a
   165   /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   166   /// kind of capacity.
   167   ///
   168   /// The type of the capacity is determined by the \ref 
   169   /// concept::ReadMap::Value "Value" of the capacity map.
   170   ///
   171   /// It is also possible to change the underlying priority heap.
   172   ///
   173   ///
   174   /// \param _Graph The graph type the algorithm runs on. The default value
   175   /// is \ref ListGraph. The value of Graph is not used directly by
   176   /// the search algorithm, it is only passed to 
   177   /// \ref MaxCardinalitySearchDefaultTraits.
   178   /// \param _CapacityMap This read-only EdgeMap determines the capacities of 
   179   /// the edges. It is read once for each edge, so the map may involve in
   180   /// relatively time consuming process to compute the edge capacity if
   181   /// it is necessary. The default map type is \ref
   182   /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
   183   /// of CapacityMap is not used directly by search algorithm, it is only 
   184   /// passed to \ref MaxCardinalitySearchDefaultTraits.  
   185   /// \param _Traits Traits class to set various data types used by the 
   186   /// algorithm.  The default traits class is 
   187   /// \ref MaxCardinalitySearchDefaultTraits 
   188   /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".  
   189   /// See \ref MaxCardinalitySearchDefaultTraits 
   190   /// for the documentation of a MaxCardinalitySearch traits class.
   191   ///
   192   /// \author Balazs Dezso
   193 
   194 #ifdef DOXYGEN
   195   template <typename _Graph, typename _CapacityMap, typename _Traits>
   196 #else
   197   template <typename _Graph = ListUGraph,
   198 	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
   199 	    typename _Traits = 
   200             MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
   201 #endif
   202   class MaxCardinalitySearch {
   203   public:
   204     /// \brief \ref Exception for uninitialized parameters.
   205     ///
   206     /// This error represents problems in the initialization
   207     /// of the parameters of the algorithms.
   208     class UninitializedParameter : public lemon::UninitializedParameter {
   209     public:
   210       virtual const char* exceptionName() const {
   211 	return "lemon::MaxCardinalitySearch::UninitializedParameter";
   212       }
   213     };
   214 
   215     typedef _Traits Traits;
   216     ///The type of the underlying graph.
   217     typedef typename Traits::Graph Graph;
   218     
   219     ///The type of the capacity of the edges.
   220     typedef typename Traits::CapacityMap::Value Value;
   221     ///The type of the map that stores the edge capacities.
   222     typedef typename Traits::CapacityMap CapacityMap;
   223     ///The type of the map indicating if a node is processed.
   224     typedef typename Traits::ProcessedMap ProcessedMap;
   225     ///The type of the map that stores the cardinalities of the nodes.
   226     typedef typename Traits::CardinalityMap CardinalityMap;
   227     ///The cross reference type used for the current heap.
   228     typedef typename Traits::HeapCrossRef HeapCrossRef;
   229     ///The heap type used by the algorithm. It maximize the priorities.
   230     typedef typename Traits::Heap Heap;
   231   private:
   232     /// Pointer to the underlying graph.
   233     const Graph *_graph;
   234     /// Pointer to the capacity map
   235     const CapacityMap *_capacity;
   236     ///Pointer to the map of cardinality.
   237     CardinalityMap *_cardinality;
   238     ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
   239     bool local_cardinality;
   240     ///Pointer to the map of processed status of the nodes.
   241     ProcessedMap *_processed;
   242     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   243     bool local_processed;
   244     ///Pointer to the heap cross references.
   245     HeapCrossRef *_heap_cross_ref;
   246     ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   247     bool local_heap_cross_ref;
   248     ///Pointer to the heap.
   249     Heap *_heap;
   250     ///Indicates if \ref _heap is locally allocated (\c true) or not.
   251     bool local_heap;
   252 
   253   public :
   254 
   255     typedef MaxCardinalitySearch Create;
   256  
   257     ///\name Named template parameters
   258 
   259     ///@{
   260 
   261     template <class T>
   262     struct DefCardinalityMapTraits : public Traits {
   263       typedef T CardinalityMap;
   264       static CardinalityMap *createCardinalityMap(const Graph &) 
   265       {
   266 	throw UninitializedParameter();
   267       }
   268     };
   269     /// \brief \ref named-templ-param "Named parameter" for setting 
   270     /// CardinalityMap type
   271     ///
   272     /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
   273     /// type
   274     template <class T>
   275     struct DefCardinalityMap 
   276       : public MaxCardinalitySearch<Graph, CapacityMap, 
   277                                     DefCardinalityMapTraits<T> > { 
   278       typedef MaxCardinalitySearch<Graph, CapacityMap, 
   279                                    DefCardinalityMapTraits<T> > Create;
   280     };
   281     
   282     template <class T>
   283     struct DefProcessedMapTraits : public Traits {
   284       typedef T ProcessedMap;
   285       static ProcessedMap *createProcessedMap(const Graph &) {
   286 	throw UninitializedParameter();
   287       }
   288     };
   289     /// \brief \ref named-templ-param "Named parameter" for setting 
   290     /// ProcessedMap type
   291     ///
   292     /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
   293     ///
   294     template <class T>
   295     struct DefProcessedMap 
   296       : public MaxCardinalitySearch<Graph, CapacityMap, 
   297                                     DefProcessedMapTraits<T> > { 
   298       typedef MaxCardinalitySearch<Graph, CapacityMap, 
   299                                    DefProcessedMapTraits<T> > Create;
   300     };
   301     
   302     template <class H, class CR>
   303     struct DefHeapTraits : public Traits {
   304       typedef CR HeapCrossRef;
   305       typedef H Heap;
   306       static HeapCrossRef *createHeapCrossRef(const Graph &) {
   307 	throw UninitializedParameter();
   308       }
   309       static Heap *createHeap(HeapCrossRef &) {
   310 	throw UninitializedParameter();
   311       }
   312     };
   313     /// \brief \ref named-templ-param "Named parameter" for setting heap 
   314     /// and cross reference type
   315     ///
   316     /// \ref named-templ-param "Named parameter" for setting heap and cross 
   317     /// reference type
   318     template <class H, class CR = typename Graph::template NodeMap<int> >
   319     struct DefHeap
   320       : public MaxCardinalitySearch<Graph, CapacityMap, 
   321                                     DefHeapTraits<H, CR> > { 
   322       typedef MaxCardinalitySearch< Graph, CapacityMap, 
   323                                     DefHeapTraits<H, CR> > Create;
   324     };
   325 
   326     template <class H, class CR>
   327     struct DefStandardHeapTraits : public Traits {
   328       typedef CR HeapCrossRef;
   329       typedef H Heap;
   330       static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
   331 	return new HeapCrossRef(graph);
   332       }
   333       static Heap *createHeap(HeapCrossRef &crossref) {
   334 	return new Heap(crossref);
   335       }
   336     };
   337 
   338     /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   339     /// cross reference type with automatic allocation
   340     ///
   341     /// \ref named-templ-param "Named parameter" for setting heap and cross 
   342     /// reference type. It can allocate the heap and the cross reference 
   343     /// object if the cross reference's constructor waits for the graph as 
   344     /// parameter and the heap's constructor waits for the cross reference.
   345     template <class H, class CR = typename Graph::template NodeMap<int> >
   346     struct DefStandardHeap
   347       : public MaxCardinalitySearch<Graph, CapacityMap, 
   348                                     DefStandardHeapTraits<H, CR> > { 
   349       typedef MaxCardinalitySearch<Graph, CapacityMap, 
   350                                    DefStandardHeapTraits<H, CR> > 
   351       Create;
   352     };
   353     
   354     ///@}
   355 
   356 
   357   protected:
   358 
   359     MaxCardinalitySearch() {}
   360 
   361   public:      
   362     
   363     /// \brief Constructor.
   364     ///
   365     ///\param graph the graph the algorithm will run on.
   366     ///\param capacity the capacity map used by the algorithm.
   367     MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
   368       _graph(&graph), _capacity(&capacity),
   369       _cardinality(0), local_cardinality(false),
   370       _processed(0), local_processed(false),
   371       _heap_cross_ref(0), local_heap_cross_ref(false),
   372       _heap(0), local_heap(false)
   373     { }
   374     
   375     /// \brief Destructor.
   376     ~MaxCardinalitySearch() {
   377       if(local_cardinality) delete _cardinality;
   378       if(local_processed) delete _processed;
   379       if(local_heap_cross_ref) delete _heap_cross_ref;
   380       if(local_heap) delete _heap;
   381     }
   382 
   383     /// \brief Sets the capacity map.
   384     ///
   385     /// Sets the capacity map.
   386     /// \return <tt> (*this) </tt>
   387     MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
   388       _capacity = &m;
   389       return *this;
   390     }
   391 
   392     /// \brief Sets the map storing the cardinalities calculated by the 
   393     /// algorithm.
   394     ///
   395     /// Sets the map storing the cardinalities calculated by the algorithm.
   396     /// If you don't use this function before calling \ref run(),
   397     /// it will allocate one. The destuctor deallocates this
   398     /// automatically allocated map, of course.
   399     /// \return <tt> (*this) </tt>
   400     MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
   401       if(local_cardinality) {
   402 	delete _cardinality;
   403 	local_cardinality=false;
   404       }
   405       _cardinality = &m;
   406       return *this;
   407     }
   408 
   409     /// \brief Sets the map storing the processed nodes.
   410     ///
   411     /// Sets the map storing the processed nodes.
   412     /// If you don't use this function before calling \ref run(),
   413     /// it will allocate one. The destuctor deallocates this
   414     /// automatically allocated map, of course.
   415     /// \return <tt> (*this) </tt>
   416     MaxCardinalitySearch &processedMap(ProcessedMap &m) 
   417     {
   418       if(local_processed) {
   419 	delete _processed;
   420 	local_processed=false;
   421       }
   422       _processed = &m;
   423       return *this;
   424     }
   425 
   426     /// \brief Sets the heap and the cross reference used by algorithm.
   427     ///
   428     /// Sets the heap and the cross reference used by algorithm.
   429     /// If you don't use this function before calling \ref run(),
   430     /// it will allocate one. The destuctor deallocates this
   431     /// automatically allocated map, of course.
   432     /// \return <tt> (*this) </tt>
   433     MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
   434       if(local_heap_cross_ref) {
   435 	delete _heap_cross_ref;
   436 	local_heap_cross_ref = false;
   437       }
   438       _heap_cross_ref = &crossRef;
   439       if(local_heap) {
   440 	delete _heap;
   441 	local_heap = false;
   442       }
   443       _heap = &heap;
   444       return *this;
   445     }
   446 
   447   private:
   448 
   449     typedef typename Graph::Node Node;
   450     typedef typename Graph::NodeIt NodeIt;
   451     typedef typename Graph::Edge Edge;
   452     typedef typename Graph::InEdgeIt InEdgeIt;
   453 
   454     void create_maps() {
   455       if(!_cardinality) {
   456 	local_cardinality = true;
   457 	_cardinality = Traits::createCardinalityMap(*_graph);
   458       }
   459       if(!_processed) {
   460 	local_processed = true;
   461 	_processed = Traits::createProcessedMap(*_graph);
   462       }
   463       if (!_heap_cross_ref) {
   464 	local_heap_cross_ref = true;
   465 	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
   466       }
   467       if (!_heap) {
   468 	local_heap = true;
   469 	_heap = Traits::createHeap(*_heap_cross_ref);
   470       }
   471     }
   472     
   473     void finalizeNodeData(Node node, Value capacity) {
   474       _processed->set(node, true);
   475       _cardinality->set(node, capacity);
   476     }
   477 
   478   public:
   479     /// \name Execution control
   480     /// The simplest way to execute the algorithm is to use
   481     /// one of the member functions called \c run(...).
   482     /// \n
   483     /// If you need more control on the execution,
   484     /// first you must call \ref init(), then you can add several source nodes
   485     /// with \ref addSource().
   486     /// Finally \ref start() will perform the actual path
   487     /// computation.
   488 
   489     ///@{
   490 
   491     /// \brief Initializes the internal data structures.
   492     ///
   493     /// Initializes the internal data structures.
   494     void init() {
   495       create_maps();
   496       _heap->clear();
   497       for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
   498 	_processed->set(it, false);
   499 	_heap_cross_ref->set(it, Heap::PRE_HEAP);
   500       }
   501     }
   502     
   503     /// \brief Adds a new source node.
   504     /// 
   505     /// Adds a new source node to the priority heap.
   506     ///
   507     /// It checks if the node has not yet been added to the heap.
   508     void addSource(Node source, Value capacity = 0) {
   509       if(_heap->state(source) == Heap::PRE_HEAP) {
   510 	_heap->push(source, capacity);
   511       } 
   512     }
   513     
   514     /// \brief Processes the next node in the priority heap
   515     ///
   516     /// Processes the next node in the priority heap.
   517     ///
   518     /// \return The processed node.
   519     ///
   520     /// \warning The priority heap must not be empty!
   521     Node processNextNode() {
   522       Node node = _heap->top(); 
   523       finalizeNodeData(node, _heap->prio());
   524       _heap->pop();
   525       
   526       for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
   527 	Node source = _graph->source(it); 
   528 	switch (_heap->state(source)) {
   529 	case Heap::PRE_HEAP:
   530 	  _heap->push(source, (*_capacity)[it]); 
   531 	  break;
   532 	case Heap::IN_HEAP:
   533 	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); 
   534 	  break;
   535 	case Heap::POST_HEAP:
   536 	  break;
   537 	}
   538       }
   539       return node;
   540     }
   541 
   542     /// \brief Next node to be processed.
   543     ///
   544     /// Next node to be processed.
   545     ///
   546     /// \return The next node to be processed or INVALID if the 
   547     /// priority heap is empty.
   548     Node nextNode() { 
   549       return _heap->empty() ? _heap->top() : INVALID;
   550     }
   551  
   552     /// \brief Returns \c false if there are nodes
   553     /// to be processed in the priority heap
   554     ///
   555     /// Returns \c false if there are nodes
   556     /// to be processed in the priority heap
   557     bool emptyQueue() { return _heap->empty(); }
   558     /// \brief Returns the number of the nodes to be processed 
   559     /// in the priority heap
   560     ///
   561     /// Returns the number of the nodes to be processed in the priority heap
   562     int queueSize() { return _heap->size(); }
   563     
   564     /// \brief Executes the algorithm.
   565     ///
   566     /// Executes the algorithm.
   567     ///
   568     ///\pre init() must be called and at least one node should be added
   569     /// with addSource() before using this function.
   570     ///
   571     /// This method runs the Maximum Cardinality Search algorithm from the 
   572     /// source node(s).
   573     void start() {
   574       while ( !_heap->empty() ) processNextNode();
   575     }
   576     
   577     /// \brief Executes the algorithm until \c dest is reached.
   578     ///
   579     /// Executes the algorithm until \c dest is reached.
   580     ///
   581     /// \pre init() must be called and at least one node should be added
   582     /// with addSource() before using this function.
   583     ///
   584     /// This method runs the %MaxCardinalitySearch algorithm from the source 
   585     /// nodes.
   586     void start(Node dest) {
   587       while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   588       if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
   589     }
   590     
   591     /// \brief Executes the algorithm until a condition is met.
   592     ///
   593     /// Executes the algorithm until a condition is met.
   594     ///
   595     /// \pre init() must be called and at least one node should be added
   596     /// with addSource() before using this function.
   597     ///
   598     /// \param nm must be a bool (or convertible) node map. The algorithm
   599     /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
   600     template <typename NodeBoolMap>
   601     void start(const NodeBoolMap &nm) {
   602       while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   603       if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
   604     }
   605     
   606     /// \brief Runs the maximal cardinality search algorithm from node \c s.
   607     ///
   608     /// This method runs the %MaxCardinalitySearch algorithm from a root 
   609     /// node \c s.
   610     ///
   611     ///\note d.run(s) is just a shortcut of the following code.
   612     ///\code
   613     ///  d.init();
   614     ///  d.addSource(s);
   615     ///  d.start();
   616     ///\endcode
   617     void run(Node s) {
   618       init();
   619       addSource(s);
   620       start();
   621     }
   622 
   623     /// \brief Runs the maximal cardinality search algorithm for the 
   624     /// whole graph.
   625     ///
   626     /// This method runs the %MaxCardinalitySearch algorithm from all 
   627     /// unprocessed node of the graph.
   628     ///
   629     ///\note d.run(s) is just a shortcut of the following code.
   630     ///\code
   631     ///  d.init();
   632     ///  for (NodeIt it(graph); it != INVALID; ++it) {
   633     ///    if (!d.reached(it)) {
   634     ///      d.addSource(s);
   635     ///      d.start();
   636     ///    }
   637     ///  }
   638     ///\endcode
   639     void run() {
   640       init();
   641       for (NodeIt it(*_graph); it != INVALID; ++it) {
   642         if (!reached(it)) {
   643           addSource(it);
   644           start();
   645         }
   646       }
   647     }
   648     
   649     ///@}
   650 
   651     /// \name Query Functions
   652     /// The result of the maximum cardinality search algorithm can be 
   653     /// obtained using these functions.
   654     /// \n
   655     /// Before the use of these functions, either run() or start() must be 
   656     /// called.
   657     
   658     ///@{
   659 
   660     /// \brief The cardinality of a node.
   661     ///
   662     /// Returns the cardinality of a node.
   663     /// \pre \ref run() must be called before using this function.
   664     /// \warning If node \c v in unreachable from the root the return value
   665     /// of this funcion is undefined.
   666     Value cardinality(Node node) const { return (*_cardinality)[node]; }
   667 
   668     /// \brief Returns a reference to the NodeMap of cardinalities.
   669     ///
   670     /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
   671     /// must be called before using this function.
   672     const CardinalityMap &cardinalityMap() const { return *_cardinality;}
   673  
   674     /// \brief Checks if a node is reachable from the root.
   675     ///
   676     /// Returns \c true if \c v is reachable from the root.
   677     /// \warning The source nodes are inditated as unreached.
   678     /// \pre \ref run() must be called before using this function.
   679     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   680 
   681     /// \brief Checks if a node is processed.
   682     ///
   683     /// Returns \c true if \c v is processed, i.e. the shortest
   684     /// path to \c v has already found.
   685     /// \pre \ref run() must be called before using this function.
   686     bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   687     
   688     ///@}
   689   };
   690 
   691   /// \brief Default traits class of MinCut class.
   692   ///
   693   /// Default traits class of MinCut class.
   694   /// \param Graph Graph type.
   695   /// \param CapacityMap Type of length map.
   696   template <typename _Graph, typename _CapacityMap>
   697   struct MinCutDefaultTraits {
   698     /// \brief The type of the capacity of the edges.
   699     typedef typename _CapacityMap::Value Value;
   700 
   701     /// The graph type the algorithm runs on. 
   702     typedef _Graph Graph;
   703 
   704     /// The AuxGraph type which is an ErasableGraph
   705     typedef ListUGraph AuxGraph;
   706 
   707     /// \brief Instantiates a AuxGraph.
   708     ///
   709     /// This function instantiates a \ref AuxGraph. 
   710     static AuxGraph *createAuxGraph() {
   711       return new AuxGraph();
   712     }
   713 
   714     /// \brief The type of the map that stores the edge capacities.
   715     ///
   716     /// The type of the map that stores the edge capacities.
   717     /// It must meet the \ref concept::ReadMap "ReadMap" concept.
   718     typedef _CapacityMap CapacityMap;
   719 
   720     /// \brief Instantiates a CapacityMap.
   721     ///
   722     /// This function instantiates a \ref CapacityMap.
   723 #ifdef DOXYGEN
   724     static CapacityMap *createCapacityMap(const Graph& graph) 
   725 #else
   726     static CapacityMap *createCapacityMap(const Graph&)
   727 #endif
   728     {
   729       throw UninitializedParameter();
   730     }
   731 
   732     /// \brief The AuxCapacityMap type
   733     ///
   734     /// The type of the map that stores the auxing edge capacities.
   735     typedef AuxGraph::UEdgeMap<Value> AuxCapacityMap;
   736 
   737     /// \brief Instantiates a AuxCapacityMap.
   738     ///
   739     /// This function instantiates a \ref AuxCapacityMap. 
   740     static AuxCapacityMap *createAuxCapacityMap(const AuxGraph& graph) {
   741       return new AuxCapacityMap(graph);
   742     }
   743 
   744     /// \brief The cross reference type used by heap.
   745     ///
   746     /// The cross reference type used by heap.
   747     /// Usually it is \c Graph::NodeMap<int>.
   748     typedef AuxGraph::NodeMap<int> HeapCrossRef;
   749 
   750     /// \brief Instantiates a HeapCrossRef.
   751     ///
   752     /// This function instantiates a \ref HeapCrossRef. 
   753     /// \param graph is the graph, to which we would like to define the 
   754     /// HeapCrossRef.
   755     static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
   756       return new HeapCrossRef(graph);
   757     }
   758     
   759     /// \brief The heap type used by MinCut algorithm.
   760     ///
   761     /// The heap type used by MinCut algorithm. It should
   762     /// maximalize the priorities and the heap's key type is
   763     /// the aux graph's node.
   764     ///
   765     /// \sa BinHeap
   766     /// \sa MinCut
   767     typedef typename _min_cut_bits
   768     ::HeapSelector<CapacityMap>
   769     ::template Selector<typename AuxGraph::Node, Value, HeapCrossRef>
   770     ::Heap Heap;
   771     
   772     /// \brief Instantiates a Heap.
   773     ///
   774     /// This function instantiates a \ref Heap. 
   775     /// \param crossref The cross reference of the heap.
   776     static Heap *createHeap(HeapCrossRef& crossref) {
   777       return new Heap(crossref);
   778     }
   779 
   780     /// \brief Map from the AuxGraph's node type to the Graph's node type.
   781     ///
   782     /// Map from the AuxGraph's node type to the Graph's node type.
   783     typedef typename AuxGraph
   784     ::template NodeMap<typename Graph::Node> NodeRefMap;
   785 
   786     /// \brief Instantiates a NodeRefMap.
   787     ///
   788     /// This function instantiates a \ref NodeRefMap. 
   789     static NodeRefMap *createNodeRefMap(const AuxGraph& graph) {
   790       return new NodeRefMap(graph);
   791     }
   792 
   793     /// \brief Map from the Graph's node type to the Graph's node type.
   794     ///
   795     /// Map from the Graph's node type to the Graph's node type.
   796     typedef typename Graph
   797     ::template NodeMap<typename Graph::Node> ListRefMap;
   798 
   799     /// \brief Instantiates a ListRefMap.
   800     ///
   801     /// This function instantiates a \ref ListRefMap. 
   802     static ListRefMap *createListRefMap(const Graph& graph) {
   803       return new ListRefMap(graph);
   804     }
   805     
   806 
   807   };
   808 
   809   namespace _min_cut_bits {
   810     template <typename _Key>
   811     class LastTwoMap {
   812     public:
   813       typedef _Key Key;
   814       typedef bool Value;
   815 
   816       LastTwoMap(int _num) : num(_num) {}
   817       void set(const Key& key, bool val) {
   818         if (!val) return;
   819         --num;
   820         if (num > 1) return;
   821         keys[num] = key;
   822       }
   823       
   824       Key operator[](int index) const { return keys[index]; }
   825     private:
   826       Key keys[2];
   827       int num;
   828     };
   829   }
   830 
   831   /// \ingroup topology
   832   ///
   833   /// \brief Calculates the min cut in an undirected graph.
   834   ///
   835   /// Calculates the min cut in an undirected graph. 
   836   /// The algorithm separates the graph's nodes to two partitions with the 
   837   /// min sum of edge capacities between the two partitions. The
   838   /// algorithm can be used to test the netaux reliability specifically
   839   /// to test how many links have to be destroyed in the netaux to split it 
   840   /// at least two distinict subnetaux.
   841   ///
   842   /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
   843   /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
   844   /// the neutral capacity map is used then it uses BucketHeap which
   845   /// results \f$ O(ne) \f$ time complexity.
   846 #ifdef DOXYGEN
   847   template <typename _Graph, typename _CapacityMap, typename _Traits>
   848 #else
   849   template <typename _Graph = ListUGraph, 
   850 	    typename _CapacityMap = typename _Graph::template UEdgeMap<int>, 
   851 	    typename _Traits = MinCutDefaultTraits<_Graph, _CapacityMap> >
   852 #endif
   853   class MinCut {
   854   public:
   855     /// \brief \ref Exception for uninitialized parameters.
   856     ///
   857     /// This error represents problems in the initialization
   858     /// of the parameters of the algorithms.
   859     class UninitializedParameter : public lemon::UninitializedParameter {
   860     public:
   861       virtual const char* exceptionName() const {
   862 	return "lemon::MinCut::UninitializedParameter";
   863       }
   864     };
   865 
   866 
   867   private:
   868 
   869     typedef _Traits Traits;
   870     /// The type of the underlying graph.
   871     typedef typename Traits::Graph Graph;
   872     
   873     /// The type of the capacity of the edges.
   874     typedef typename Traits::CapacityMap::Value Value;
   875     /// The type of the map that stores the edge capacities.
   876     typedef typename Traits::CapacityMap CapacityMap;
   877     /// The type of the aux graph
   878     typedef typename Traits::AuxGraph AuxGraph;
   879     /// The type of the aux capacity map
   880     typedef typename Traits::AuxCapacityMap AuxCapacityMap;
   881     /// The cross reference type used for the current heap.
   882     typedef typename Traits::HeapCrossRef HeapCrossRef;
   883     /// The heap type used by the max cardinality algorithm.
   884     typedef typename Traits::Heap Heap;
   885     /// The node refrefernces between the original and aux graph type.
   886     typedef typename Traits::NodeRefMap NodeRefMap;
   887     /// The list node refrefernces in the original graph type.
   888     typedef typename Traits::ListRefMap ListRefMap;
   889 
   890   public:
   891 
   892     ///\name Named template parameters
   893 
   894     ///@{
   895 
   896     struct DefNeutralCapacityTraits : public Traits {
   897       typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
   898       static CapacityMap *createCapacityMap(const Graph&) {
   899 	return new CapacityMap();
   900       }
   901     };
   902     /// \brief \ref named-templ-param "Named parameter" for setting  
   903     /// the capacity type to constMap<UEdge, int, 1>()
   904     ///
   905     /// \ref named-templ-param "Named parameter" for setting 
   906     /// the capacity type to constMap<UEdge, int, 1>()
   907     struct DefNeutralCapacity
   908       : public MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 
   909       typedef MinCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
   910     };
   911 
   912 
   913     template <class H, class CR>
   914     struct DefHeapTraits : public Traits {
   915       typedef CR HeapCrossRef;
   916       typedef H Heap;
   917       static HeapCrossRef *createHeapCrossRef(const AuxGraph &) {
   918 	throw UninitializedParameter();
   919       }
   920       static Heap *createHeap(HeapCrossRef &) {
   921 	throw UninitializedParameter();
   922       }
   923     };
   924     /// \brief \ref named-templ-param "Named parameter" for setting heap 
   925     /// and cross reference type
   926     ///
   927     /// \ref named-templ-param "Named parameter" for setting heap and cross 
   928     /// reference type
   929     template <class H, class CR = typename Graph::template NodeMap<int> >
   930     struct DefHeap
   931       : public MinCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 
   932       typedef MinCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
   933     };
   934 
   935     template <class H, class CR>
   936     struct DefStandardHeapTraits : public Traits {
   937       typedef CR HeapCrossRef;
   938       typedef H Heap;
   939       static HeapCrossRef *createHeapCrossRef(const AuxGraph &graph) {
   940 	return new HeapCrossRef(graph);
   941       }
   942       static Heap *createHeap(HeapCrossRef &crossref) {
   943 	return new Heap(crossref);
   944       }
   945     };
   946 
   947     /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   948     /// cross reference type with automatic allocation
   949     ///
   950     /// \ref named-templ-param "Named parameter" for setting heap and cross 
   951     /// reference type. It can allocate the heap and the cross reference 
   952     /// object if the cross reference's constructor waits for the graph as 
   953     /// parameter and the heap's constructor waits for the cross reference.
   954     template <class H, class CR = typename Graph::template NodeMap<int> >
   955     struct DefStandardHeap
   956       : public MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 
   957       typedef MinCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 
   958       Create;
   959     };
   960 
   961     ///@}
   962 
   963 
   964   private:
   965     /// Pointer to the underlying graph.
   966     const Graph *_graph;
   967     /// Pointer to the capacity map
   968     const CapacityMap *_capacity;
   969     /// \brief Indicates if \ref _capacity is locally allocated 
   970     /// (\c true) or not.
   971     bool local_capacity;
   972 
   973     /// Pointer to the aux graph.
   974     AuxGraph *_aux_graph;
   975     /// \brief Indicates if \ref _aux_graph is locally allocated 
   976     /// (\c true) or not.
   977     bool local_aux_graph;
   978     /// Pointer to the aux capacity map
   979     AuxCapacityMap *_aux_capacity;
   980     /// \brief Indicates if \ref _aux_capacity is locally allocated 
   981     /// (\c true) or not.
   982     bool local_aux_capacity;
   983     /// Pointer to the heap cross references.
   984     HeapCrossRef *_heap_cross_ref;
   985     /// \brief Indicates if \ref _heap_cross_ref is locally allocated 
   986     /// (\c true) or not.
   987     bool local_heap_cross_ref;
   988     /// Pointer to the heap.
   989     Heap *_heap;
   990     /// Indicates if \ref _heap is locally allocated (\c true) or not.
   991     bool local_heap;
   992 
   993     /// The min cut value.
   994     Value _min_cut;
   995     /// The number of the nodes of the aux graph.
   996     int _node_num;
   997     /// The first and last node of the min cut in the next list;
   998     typename Graph::Node _first_node, _last_node;
   999 
  1000     /// \brief The first and last element in the list associated
  1001     /// to the aux graph node.
  1002     NodeRefMap *_first, *_last;
  1003     /// \brief The next node in the node lists.
  1004     ListRefMap *_next;
  1005     
  1006     void create_structures() {
  1007       if (!_capacity) {
  1008         local_capacity = true;
  1009         _capacity = Traits::createCapacityMap(*_graph);
  1010       }
  1011       if(!_aux_graph) {
  1012 	local_aux_graph = true;
  1013 	_aux_graph = Traits::createAuxGraph();
  1014       }
  1015       if(!_aux_capacity) {
  1016 	local_aux_capacity = true;
  1017 	_aux_capacity = Traits::createAuxCapacityMap(*_aux_graph);
  1018       }
  1019 
  1020       _first = Traits::createNodeRefMap(*_aux_graph);
  1021       _last = Traits::createNodeRefMap(*_aux_graph);
  1022 
  1023       _next = Traits::createListRefMap(*_graph);
  1024 
  1025       typename Graph::template NodeMap<typename AuxGraph::Node> ref(*_graph);
  1026 
  1027       for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  1028         _next->set(it, INVALID);
  1029         typename AuxGraph::Node node = _aux_graph->addNode();
  1030         _first->set(node, it);
  1031         _last->set(node, it);
  1032         ref.set(it, node);
  1033       }
  1034 
  1035       for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
  1036         if (_graph->source(it) == _graph->target(it)) continue;
  1037         typename AuxGraph::UEdge uedge = 
  1038           _aux_graph->addEdge(ref[_graph->source(it)], 
  1039                                ref[_graph->target(it)]);
  1040         _aux_capacity->set(uedge, (*_capacity)[it]);
  1041         
  1042       }
  1043 
  1044       if (!_heap_cross_ref) {
  1045 	local_heap_cross_ref = true;
  1046 	_heap_cross_ref = Traits::createHeapCrossRef(*_aux_graph);
  1047       }
  1048       if (!_heap) {
  1049 	local_heap = true;
  1050 	_heap = Traits::createHeap(*_heap_cross_ref);
  1051       }
  1052     }
  1053 
  1054   public :
  1055 
  1056     typedef MinCut Create;
  1057 
  1058 
  1059     /// \brief Constructor.
  1060     ///
  1061     ///\param graph the graph the algorithm will run on.
  1062     ///\param capacity the capacity map used by the algorithm.
  1063     MinCut(const Graph& graph, const CapacityMap& capacity) 
  1064       : _graph(&graph), 
  1065         _capacity(&capacity), local_capacity(false),
  1066         _aux_graph(0), local_aux_graph(false),
  1067         _aux_capacity(0), local_aux_capacity(false),
  1068         _heap_cross_ref(0), local_heap_cross_ref(false),
  1069         _heap(0), local_heap(false),
  1070         _first(0), _last(0), _next(0) {}
  1071 
  1072     /// \brief Constructor.
  1073     ///
  1074     /// This constructor can be used only when the Traits class
  1075     /// defines how can we instantiate a local capacity map.
  1076     /// If the DefNeutralCapacity used the algorithm automatically
  1077     /// construct the capacity map.
  1078     ///
  1079     ///\param graph the graph the algorithm will run on.
  1080     MinCut(const Graph& graph) 
  1081       : _graph(&graph), 
  1082         _capacity(0), local_capacity(false),
  1083         _aux_graph(0), local_aux_graph(false),
  1084         _aux_capacity(0), local_aux_capacity(false),
  1085         _heap_cross_ref(0), local_heap_cross_ref(false),
  1086         _heap(0), local_heap(false),
  1087         _first(0), _last(0), _next(0) {}
  1088 
  1089     /// \brief Destructor.
  1090     ///
  1091     /// Destructor.
  1092     ~MinCut() {
  1093       if (local_heap) delete _heap;
  1094       if (local_heap_cross_ref) delete _heap_cross_ref;
  1095       if (_first) delete _first;
  1096       if (_last) delete _last;
  1097       if (_next) delete _next;
  1098       if (local_aux_capacity) delete _aux_capacity;
  1099       if (local_aux_graph) delete _aux_graph;
  1100       if (local_capacity) delete _capacity;
  1101     }
  1102 
  1103     /// \brief Sets the heap and the cross reference used by algorithm.
  1104     ///
  1105     /// Sets the heap and the cross reference used by algorithm.
  1106     /// If you don't use this function before calling \ref run(),
  1107     /// it will allocate one. The destuctor deallocates this
  1108     /// automatically allocated heap and cross reference, of course.
  1109     /// \return <tt> (*this) </tt>
  1110     MinCut &heap(Heap& heap, HeapCrossRef &crossRef)
  1111     {
  1112       if (local_heap_cross_ref) {
  1113 	delete _heap_cross_ref;
  1114 	local_heap_cross_ref=false;
  1115       }
  1116       _heap_cross_ref = &crossRef;
  1117       if (local_heap) {
  1118 	delete _heap;
  1119 	local_heap=false;
  1120       }
  1121       _heap = &heap;
  1122       return *this;
  1123     }
  1124 
  1125     /// \brief Sets the aux graph.
  1126     ///
  1127     /// Sets the aux graph used by algorithm.
  1128     /// If you don't use this function before calling \ref run(),
  1129     /// it will allocate one. The destuctor deallocates this
  1130     /// automatically allocated graph, of course.
  1131     /// \return <tt> (*this) </tt>
  1132     MinCut &auxGraph(AuxGraph& aux_graph)
  1133     {
  1134       if(local_aux_graph) {
  1135 	delete _aux_graph;
  1136 	local_aux_graph=false;
  1137       }
  1138       _aux_graph = &aux_graph;
  1139       return *this;
  1140     }
  1141 
  1142     /// \brief Sets the aux capacity map.
  1143     ///
  1144     /// Sets the aux capacity map used by algorithm.
  1145     /// If you don't use this function before calling \ref run(),
  1146     /// it will allocate one. The destuctor deallocates this
  1147     /// automatically allocated graph, of course.
  1148     /// \return <tt> (*this) </tt>
  1149     MinCut &auxCapacityMap(AuxCapacityMap& aux_capacity_map)
  1150     {
  1151       if(local_aux_capacity) {
  1152 	delete _aux_capacity;
  1153 	local_aux_capacity=false;
  1154       }
  1155       _aux_capacity = &aux_capacity_map;
  1156       return *this;
  1157     }
  1158 
  1159     /// \name Execution control
  1160     /// The simplest way to execute the algorithm is to use
  1161     /// one of the member functions called \c run().
  1162     /// \n
  1163     /// If you need more control on the execution,
  1164     /// first you must call \ref init() and then call the start()
  1165     /// or proper times the processNextPhase() member functions.
  1166 
  1167     ///@{
  1168 
  1169     /// \brief Initializes the internal data structures.
  1170     ///
  1171     /// Initializes the internal data structures.
  1172     void init() {
  1173       create_structures();
  1174       _first_node = _last_node = INVALID;
  1175       _node_num = countNodes(*_graph);
  1176     }
  1177 
  1178     /// \brief Processes the next phase
  1179     ///
  1180     /// Processes the next phase in the algorithm. The function
  1181     /// should be called countNodes(graph) - 1 times to get
  1182     /// surely the min cut in the graph. The  
  1183     ///
  1184     ///\return %True when the algorithm finished.
  1185     bool processNextPhase() {
  1186       if (_node_num <= 1) return true;
  1187       using namespace _min_cut_bits;
  1188 
  1189       typedef typename AuxGraph::Node Node;
  1190       typedef typename AuxGraph::NodeIt NodeIt;
  1191       typedef typename AuxGraph::UEdge UEdge;
  1192       typedef typename AuxGraph::IncEdgeIt IncEdgeIt;
  1193       
  1194       typedef typename MaxCardinalitySearch<AuxGraph, AuxCapacityMap>::
  1195       template DefHeap<Heap, HeapCrossRef>::
  1196       template DefCardinalityMap<NullMap<Node, Value> >::
  1197       template DefProcessedMap<LastTwoMap<Node> >::
  1198       Create MaxCardinalitySearch;
  1199       
  1200       MaxCardinalitySearch mcs(*_aux_graph, *_aux_capacity);
  1201       for (NodeIt it(*_aux_graph); it != INVALID; ++it) {
  1202         _heap_cross_ref->set(it, Heap::PRE_HEAP);
  1203       }
  1204       mcs.heap(*_heap, *_heap_cross_ref);
  1205 
  1206       LastTwoMap<Node> last_two_nodes(_node_num);
  1207       mcs.processedMap(last_two_nodes);
  1208 
  1209       NullMap<Node, Value> cardinality;
  1210       mcs.cardinalityMap(cardinality);
  1211 
  1212       mcs.run();
  1213 
  1214       Node new_node = _aux_graph->addNode();
  1215 
  1216       typename AuxGraph::template NodeMap<UEdge> edges(*_aux_graph, INVALID);
  1217       
  1218       Node first_node = last_two_nodes[0];
  1219       Node second_node = last_two_nodes[1];
  1220       
  1221       _next->set((*_last)[first_node], (*_first)[second_node]);
  1222       _first->set(new_node, (*_first)[first_node]);
  1223       _last->set(new_node, (*_last)[second_node]);
  1224 
  1225       Value current_cut = 0;      
  1226       for (IncEdgeIt it(*_aux_graph, first_node); it != INVALID; ++it) {
  1227         Node node = _aux_graph->runningNode(it);
  1228         current_cut += (*_aux_capacity)[it];
  1229         if (node == second_node) continue;
  1230         if (edges[node] == INVALID) {
  1231           edges[node] = _aux_graph->addEdge(new_node, node);
  1232           (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
  1233         } else {
  1234           (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];          
  1235         }
  1236       }
  1237 
  1238       if (_first_node == INVALID || current_cut < _min_cut) {
  1239         _first_node = (*_first)[first_node];
  1240         _last_node = (*_last)[first_node];
  1241         _min_cut = current_cut;
  1242       }
  1243 
  1244       _aux_graph->erase(first_node);
  1245 
  1246       for (IncEdgeIt it(*_aux_graph, second_node); it != INVALID; ++it) {
  1247         Node node = _aux_graph->runningNode(it);
  1248         if (edges[node] == INVALID) {
  1249           edges[node] = _aux_graph->addEdge(new_node, node);
  1250           (*_aux_capacity)[edges[node]] = (*_aux_capacity)[it];
  1251         } else {
  1252           (*_aux_capacity)[edges[node]] += (*_aux_capacity)[it];          
  1253         }
  1254       }
  1255       _aux_graph->erase(second_node);
  1256 
  1257       --_node_num;
  1258       return _node_num == 1;
  1259     }
  1260 
  1261     /// \brief Executes the algorithm.
  1262     ///
  1263     /// Executes the algorithm.
  1264     ///
  1265     /// \pre init() must be called
  1266     void start() {
  1267       while (!processNextPhase());
  1268     }
  1269 
  1270 
  1271     /// \brief Runs %MinCut algorithm.
  1272     ///
  1273     /// This method runs the %Min cut algorithm
  1274     ///
  1275     /// \note mc.run(s) is just a shortcut of the following code.
  1276     ///\code
  1277     ///  mc.init();
  1278     ///  mc.start();
  1279     ///\endcode
  1280     void run() {
  1281       init();
  1282       start();
  1283     }
  1284 
  1285     ///@}
  1286 
  1287     /// \name Query Functions
  1288     /// The result of the %MinCut algorithm can be obtained using these
  1289     /// functions.\n
  1290     /// Before the use of these functions,
  1291     /// either run() or start() must be called.
  1292     
  1293     ///@{
  1294 
  1295     /// \brief Returns the min cut value.
  1296     ///
  1297     /// Returns the min cut value if the algorithm finished.
  1298     /// After the first processNextPhase() it is a value of a
  1299     /// valid cut in the graph.
  1300     Value minCut() const {
  1301       return _min_cut;
  1302     }
  1303 
  1304     /// \brief Returns a min cut in a NodeMap.
  1305     ///
  1306     /// It sets the nodes of one of the two partitions to true in
  1307     /// the given BoolNodeMap. The map contains a valid cut if the
  1308     /// map have been set false previously. 
  1309     template <typename NodeMap>
  1310     Value quickMinCut(NodeMap& nodeMap) const { 
  1311       for (typename Graph::Node it = _first_node; 
  1312            it != _last_node; it = (*_next)[it]) {
  1313              nodeMap.set(it, true);
  1314            }
  1315       nodeMap.set(_last_node, true);
  1316       return minCut();
  1317     }
  1318 
  1319     /// \brief Returns a min cut in a NodeMap.
  1320     ///
  1321     /// It sets the nodes of one of the two partitions to true and
  1322     /// the other partition to false. The function first set all of the
  1323     /// nodes to false and after it call the quickMinCut() member.
  1324     template <typename NodeMap>
  1325     Value minCut(NodeMap& nodeMap) const { 
  1326       for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  1327         nodeMap.set(it, false);      
  1328       }
  1329       quickMinCut(nodeMap);
  1330       return minCut();
  1331     }
  1332 
  1333     /// \brief Returns a min cut in an EdgeMap.
  1334     ///
  1335     /// If an undirected edge is in a min cut then it will be
  1336     /// set to true and the others will be set to false in the given map.
  1337     template <typename EdgeMap>
  1338     Value cutEdges(EdgeMap& edgeMap) const {
  1339       typename Graph::template NodeMap<bool> cut(*_graph, false);
  1340       quickMinCut(cut);
  1341       for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
  1342         edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
  1343       }
  1344       return minCut();
  1345     }
  1346 
  1347     ///@}
  1348 
  1349   };
  1350 }
  1351 
  1352 #endif