Name modification
authordeba
Tue, 14 Feb 2006 10:41:16 +0000
changeset 196878e6e2d1fd96
parent 1967 5d81ba873b90
child 1969 68c2c1176e9e
Name modification
lemon/Makefile.am
lemon/minimal_cut.h
lemon/minimum_cut.h
     1.1 --- a/lemon/Makefile.am	Mon Feb 13 09:42:53 2006 +0000
     1.2 +++ b/lemon/Makefile.am	Tue Feb 14 10:41:16 2006 +0000
     1.3 @@ -58,7 +58,7 @@
     1.4  	map_iterator.h \
     1.5  	max_matching.h \
     1.6  	min_cost_flow.h \
     1.7 -	minimal_cut.h \
     1.8 +	minimum_cut.h \
     1.9  	suurballe.h \
    1.10  	preflow.h \
    1.11  	path.h \
     2.1 --- a/lemon/minimal_cut.h	Mon Feb 13 09:42:53 2006 +0000
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,1351 +0,0 @@
     2.4 -/* -*- C++ -*-
     2.5 - * lemon/minimal_cut.h - Part of LEMON, a generic C++ optimization library
     2.6 - *
     2.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     2.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
     2.9 - *
    2.10 - * Permission to use, modify and distribute this software is granted
    2.11 - * provided that this copyright notice appears in all copies. For
    2.12 - * precise terms see the accompanying LICENSE file.
    2.13 - *
    2.14 - * This software is provided "AS IS" with no warranty of any kind,
    2.15 - * express or implied, and with no claim as to its suitability for any
    2.16 - * purpose.
    2.17 - *
    2.18 - */
    2.19 -
    2.20 -#ifndef LEMON_MINIMAL_CUT_H
    2.21 -#define LEMON_MINIMAL_CUT_H
    2.22 -
    2.23 -
    2.24 -/// \ingroup topology
    2.25 -/// \file
    2.26 -/// \brief Maximum cardinality search and minimal cut in undirected graphs.
    2.27 -
    2.28 -#include <lemon/list_graph.h>
    2.29 -#include <lemon/bin_heap.h>
    2.30 -#include <lemon/linear_heap.h>
    2.31 -
    2.32 -#include <lemon/invalid.h>
    2.33 -#include <lemon/error.h>
    2.34 -#include <lemon/maps.h>
    2.35 -
    2.36 -#include <functional>
    2.37 -
    2.38 -namespace lemon {
    2.39 -
    2.40 -  namespace _minimal_cut_bits {
    2.41 -
    2.42 -    template <typename CapacityMap>
    2.43 -    struct HeapSelector {
    2.44 -      template <typename Key, typename Value, typename Ref>
    2.45 -      struct Selector {
    2.46 -        typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
    2.47 -      };
    2.48 -    };
    2.49 -
    2.50 -    template <typename CapacityKey>
    2.51 -    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
    2.52 -      template <typename Key, typename Value, typename Ref>
    2.53 -      struct Selector {
    2.54 -        typedef LinearHeap<Key, Ref, false > Heap;
    2.55 -      };
    2.56 -    };
    2.57 -
    2.58 -  }
    2.59 -
    2.60 -  /// \brief Default traits class of MaxCardinalitySearch class.
    2.61 -  ///
    2.62 -  /// Default traits class of MaxCardinalitySearch class.
    2.63 -  /// \param Graph Graph type.
    2.64 -  /// \param CapacityMap Type of length map.
    2.65 -  template <typename _Graph, typename _CapacityMap>
    2.66 -  struct MaxCardinalitySearchDefaultTraits {
    2.67 -    /// The graph type the algorithm runs on. 
    2.68 -    typedef _Graph Graph;
    2.69 -
    2.70 -    /// \brief The type of the map that stores the edge capacities.
    2.71 -    ///
    2.72 -    /// The type of the map that stores the edge capacities.
    2.73 -    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
    2.74 -    typedef _CapacityMap CapacityMap;
    2.75 -
    2.76 -    /// \brief The type of the capacity of the edges.
    2.77 -    typedef typename CapacityMap::Value Value;
    2.78 -
    2.79 -    /// \brief The cross reference type used by heap.
    2.80 -    ///
    2.81 -    /// The cross reference type used by heap.
    2.82 -    /// Usually it is \c Graph::NodeMap<int>.
    2.83 -    typedef typename Graph::template NodeMap<int> HeapCrossRef;
    2.84 -
    2.85 -    /// \brief Instantiates a HeapCrossRef.
    2.86 -    ///
    2.87 -    /// This function instantiates a \ref HeapCrossRef. 
    2.88 -    /// \param graph is the graph, to which we would like to define the 
    2.89 -    /// HeapCrossRef.
    2.90 -    static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
    2.91 -      return new HeapCrossRef(graph);
    2.92 -    }
    2.93 -    
    2.94 -    /// \brief The heap type used by MaxCardinalitySearch algorithm.
    2.95 -    ///
    2.96 -    /// The heap type used by MaxCardinalitySearch algorithm. It should
    2.97 -    /// maximalize the priorities. The default heap type is
    2.98 -    /// the \ref BinHeap, but it is specialized when the
    2.99 -    /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
   2.100 -    /// to LinearHeap.
   2.101 -    ///
   2.102 -    /// \sa MaxCardinalitySearch
   2.103 -    typedef typename _minimal_cut_bits
   2.104 -    ::HeapSelector<CapacityMap>
   2.105 -    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
   2.106 -    ::Heap Heap;
   2.107 -
   2.108 -    /// \brief Instantiates a Heap.
   2.109 -    ///
   2.110 -    /// This function instantiates a \ref Heap. 
   2.111 -    /// \param crossref The cross reference of the heap.
   2.112 -    static Heap *createHeap(HeapCrossRef& crossref) {
   2.113 -      return new Heap(crossref);
   2.114 -    }
   2.115 -
   2.116 -    /// \brief The type of the map that stores whether a nodes is processed.
   2.117 -    ///
   2.118 -    /// The type of the map that stores whether a nodes is processed.
   2.119 -    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   2.120 -    /// By default it is a NullMap.
   2.121 -    typedef NullMap<typename Graph::Node, bool> ProcessedMap;
   2.122 -
   2.123 -    /// \brief Instantiates a ProcessedMap.
   2.124 -    ///
   2.125 -    /// This function instantiates a \ref ProcessedMap. 
   2.126 -    /// \param g is the graph, to which
   2.127 -    /// we would like to define the \ref ProcessedMap
   2.128 -#ifdef DOXYGEN
   2.129 -    static ProcessedMap *createProcessedMap(const Graph &graph)
   2.130 -#else
   2.131 -    static ProcessedMap *createProcessedMap(const Graph &)
   2.132 -#endif
   2.133 -    {
   2.134 -      return new ProcessedMap();
   2.135 -    }
   2.136 -
   2.137 -    /// \brief The type of the map that stores the cardinalties of the nodes.
   2.138 -    /// 
   2.139 -    /// The type of the map that stores the cardinalities of the nodes.
   2.140 -    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   2.141 -    typedef typename Graph::template NodeMap<Value> CardinalityMap;
   2.142 -
   2.143 -    /// \brief Instantiates a CardinalityMap.
   2.144 -    ///
   2.145 -    /// This function instantiates a \ref CardinalityMap. 
   2.146 -    /// \param graph is the graph, to which we would like to define the \ref 
   2.147 -    /// CardinalityMap
   2.148 -    static CardinalityMap *createCardinalityMap(const Graph &graph) {
   2.149 -      return new CardinalityMap(graph);
   2.150 -    }
   2.151 -
   2.152 -  };
   2.153 -  
   2.154 -  /// \ingroup topology
   2.155 -  ///
   2.156 -  /// \brief Maximum Cardinality Search algorithm class.
   2.157 -  ///
   2.158 -  /// This class provides an efficient implementation of Maximum Cardinality 
   2.159 -  /// Search algorithm. The maximum cardinality search chooses first time any 
   2.160 -  /// node of the graph. Then every time chooses that node which connected
   2.161 -  /// to the processed nodes at most in the sum of capacities on the out 
   2.162 -  /// edges. If there is a cut in the graph the algorithm should choose
   2.163 -  /// again any unprocessed node of the graph. Each nodes cardinality is
   2.164 -  /// the sum of capacities on the out edges to the nodes which are processed
   2.165 -  /// before the given node.
   2.166 -  ///
   2.167 -  /// The edge capacities are passed to the algorithm using a
   2.168 -  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   2.169 -  /// kind of capacity.
   2.170 -  ///
   2.171 -  /// The type of the capacity is determined by the \ref 
   2.172 -  /// concept::ReadMap::Value "Value" of the capacity map.
   2.173 -  ///
   2.174 -  /// It is also possible to change the underlying priority heap.
   2.175 -  ///
   2.176 -  ///
   2.177 -  /// \param _Graph The graph type the algorithm runs on. The default value
   2.178 -  /// is \ref ListGraph. The value of Graph is not used directly by
   2.179 -  /// the search algorithm, it is only passed to 
   2.180 -  /// \ref MaxCardinalitySearchDefaultTraits.
   2.181 -  /// \param _CapacityMap This read-only EdgeMap determines the capacities of 
   2.182 -  /// the edges. It is read once for each edge, so the map may involve in
   2.183 -  /// relatively time consuming process to compute the edge capacity if
   2.184 -  /// it is necessary. The default map type is \ref
   2.185 -  /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
   2.186 -  /// of CapacityMap is not used directly by search algorithm, it is only 
   2.187 -  /// passed to \ref MaxCardinalitySearchDefaultTraits.  
   2.188 -  /// \param _Traits Traits class to set various data types used by the 
   2.189 -  /// algorithm.  The default traits class is 
   2.190 -  /// \ref MaxCardinalitySearchDefaultTraits 
   2.191 -  /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".  
   2.192 -  /// See \ref MaxCardinalitySearchDefaultTraits 
   2.193 -  /// for the documentation of a MaxCardinalitySearch traits class.
   2.194 -  ///
   2.195 -  /// \author Balazs Dezso
   2.196 -
   2.197 -#ifdef DOXYGEN
   2.198 -  template <typename _Graph, typename _CapacityMap, typename _Traits>
   2.199 -#else
   2.200 -  template <typename _Graph = ListUGraph,
   2.201 -	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
   2.202 -	    typename _Traits = 
   2.203 -            MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
   2.204 -#endif
   2.205 -  class MaxCardinalitySearch {
   2.206 -  public:
   2.207 -    /// \brief \ref Exception for uninitialized parameters.
   2.208 -    ///
   2.209 -    /// This error represents problems in the initialization
   2.210 -    /// of the parameters of the algorithms.
   2.211 -    class UninitializedParameter : public lemon::UninitializedParameter {
   2.212 -    public:
   2.213 -      virtual const char* exceptionName() const {
   2.214 -	return "lemon::MaxCardinalitySearch::UninitializedParameter";
   2.215 -      }
   2.216 -    };
   2.217 -
   2.218 -    typedef _Traits Traits;
   2.219 -    ///The type of the underlying graph.
   2.220 -    typedef typename Traits::Graph Graph;
   2.221 -    
   2.222 -    ///The type of the capacity of the edges.
   2.223 -    typedef typename Traits::CapacityMap::Value Value;
   2.224 -    ///The type of the map that stores the edge capacities.
   2.225 -    typedef typename Traits::CapacityMap CapacityMap;
   2.226 -    ///The type of the map indicating if a node is processed.
   2.227 -    typedef typename Traits::ProcessedMap ProcessedMap;
   2.228 -    ///The type of the map that stores the cardinalities of the nodes.
   2.229 -    typedef typename Traits::CardinalityMap CardinalityMap;
   2.230 -    ///The cross reference type used for the current heap.
   2.231 -    typedef typename Traits::HeapCrossRef HeapCrossRef;
   2.232 -    ///The heap type used by the algorithm. It maximize the priorities.
   2.233 -    typedef typename Traits::Heap Heap;
   2.234 -  private:
   2.235 -    /// Pointer to the underlying graph.
   2.236 -    const Graph *_graph;
   2.237 -    /// Pointer to the capacity map
   2.238 -    const CapacityMap *_capacity;
   2.239 -    ///Pointer to the map of cardinality.
   2.240 -    CardinalityMap *_cardinality;
   2.241 -    ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
   2.242 -    bool local_cardinality;
   2.243 -    ///Pointer to the map of processed status of the nodes.
   2.244 -    ProcessedMap *_processed;
   2.245 -    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   2.246 -    bool local_processed;
   2.247 -    ///Pointer to the heap cross references.
   2.248 -    HeapCrossRef *_heap_cross_ref;
   2.249 -    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   2.250 -    bool local_heap_cross_ref;
   2.251 -    ///Pointer to the heap.
   2.252 -    Heap *_heap;
   2.253 -    ///Indicates if \ref _heap is locally allocated (\c true) or not.
   2.254 -    bool local_heap;
   2.255 -
   2.256 -  public :
   2.257 -
   2.258 -    typedef MaxCardinalitySearch Create;
   2.259 - 
   2.260 -    ///\name Named template parameters
   2.261 -
   2.262 -    ///@{
   2.263 -
   2.264 -    template <class T>
   2.265 -    struct DefCardinalityMapTraits : public Traits {
   2.266 -      typedef T CardinalityMap;
   2.267 -      static CardinalityMap *createCardinalityMap(const Graph &) 
   2.268 -      {
   2.269 -	throw UninitializedParameter();
   2.270 -      }
   2.271 -    };
   2.272 -    /// \brief \ref named-templ-param "Named parameter" for setting 
   2.273 -    /// CardinalityMap type
   2.274 -    ///
   2.275 -    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
   2.276 -    /// type
   2.277 -    template <class T>
   2.278 -    struct DefCardinalityMap 
   2.279 -      : public MaxCardinalitySearch<Graph, CapacityMap, 
   2.280 -                                    DefCardinalityMapTraits<T> > { 
   2.281 -      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   2.282 -                                   DefCardinalityMapTraits<T> > Create;
   2.283 -    };
   2.284 -    
   2.285 -    template <class T>
   2.286 -    struct DefProcessedMapTraits : public Traits {
   2.287 -      typedef T ProcessedMap;
   2.288 -      static ProcessedMap *createProcessedMap(const Graph &) {
   2.289 -	throw UninitializedParameter();
   2.290 -      }
   2.291 -    };
   2.292 -    /// \brief \ref named-templ-param "Named parameter" for setting 
   2.293 -    /// ProcessedMap type
   2.294 -    ///
   2.295 -    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
   2.296 -    ///
   2.297 -    template <class T>
   2.298 -    struct DefProcessedMap 
   2.299 -      : public MaxCardinalitySearch<Graph, CapacityMap, 
   2.300 -                                    DefProcessedMapTraits<T> > { 
   2.301 -      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   2.302 -                                   DefProcessedMapTraits<T> > Create;
   2.303 -    };
   2.304 -    
   2.305 -    template <class H, class CR>
   2.306 -    struct DefHeapTraits : public Traits {
   2.307 -      typedef CR HeapCrossRef;
   2.308 -      typedef H Heap;
   2.309 -      static HeapCrossRef *createHeapCrossRef(const Graph &) {
   2.310 -	throw UninitializedParameter();
   2.311 -      }
   2.312 -      static Heap *createHeap(HeapCrossRef &) {
   2.313 -	throw UninitializedParameter();
   2.314 -      }
   2.315 -    };
   2.316 -    /// \brief \ref named-templ-param "Named parameter" for setting heap 
   2.317 -    /// and cross reference type
   2.318 -    ///
   2.319 -    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   2.320 -    /// reference type
   2.321 -    template <class H, class CR = typename Graph::template NodeMap<int> >
   2.322 -    struct DefHeap
   2.323 -      : public MaxCardinalitySearch<Graph, CapacityMap, 
   2.324 -                                    DefHeapTraits<H, CR> > { 
   2.325 -      typedef MaxCardinalitySearch< Graph, CapacityMap, 
   2.326 -                                    DefHeapTraits<H, CR> > Create;
   2.327 -    };
   2.328 -
   2.329 -    template <class H, class CR>
   2.330 -    struct DefStandardHeapTraits : public Traits {
   2.331 -      typedef CR HeapCrossRef;
   2.332 -      typedef H Heap;
   2.333 -      static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
   2.334 -	return new HeapCrossRef(graph);
   2.335 -      }
   2.336 -      static Heap *createHeap(HeapCrossRef &crossref) {
   2.337 -	return new Heap(crossref);
   2.338 -      }
   2.339 -    };
   2.340 -
   2.341 -    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   2.342 -    /// cross reference type with automatic allocation
   2.343 -    ///
   2.344 -    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   2.345 -    /// reference type. It can allocate the heap and the cross reference 
   2.346 -    /// object if the cross reference's constructor waits for the graph as 
   2.347 -    /// parameter and the heap's constructor waits for the cross reference.
   2.348 -    template <class H, class CR = typename Graph::template NodeMap<int> >
   2.349 -    struct DefStandardHeap
   2.350 -      : public MaxCardinalitySearch<Graph, CapacityMap, 
   2.351 -                                    DefStandardHeapTraits<H, CR> > { 
   2.352 -      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   2.353 -                                   DefStandardHeapTraits<H, CR> > 
   2.354 -      Create;
   2.355 -    };
   2.356 -    
   2.357 -    ///@}
   2.358 -
   2.359 -
   2.360 -  protected:
   2.361 -
   2.362 -    MaxCardinalitySearch() {}
   2.363 -
   2.364 -  public:      
   2.365 -    
   2.366 -    /// \brief Constructor.
   2.367 -    ///
   2.368 -    ///\param _graph the graph the algorithm will run on.
   2.369 -    ///\param _capacity the capacity map used by the algorithm.
   2.370 -    MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
   2.371 -      _graph(&graph), _capacity(&capacity),
   2.372 -      _cardinality(0), local_cardinality(false),
   2.373 -      _processed(0), local_processed(false),
   2.374 -      _heap_cross_ref(0), local_heap_cross_ref(false),
   2.375 -      _heap(0), local_heap(false)
   2.376 -    { }
   2.377 -    
   2.378 -    /// \brief Destructor.
   2.379 -    ~MaxCardinalitySearch() {
   2.380 -      if(local_cardinality) delete _cardinality;
   2.381 -      if(local_processed) delete _processed;
   2.382 -      if(local_heap_cross_ref) delete _heap_cross_ref;
   2.383 -      if(local_heap) delete _heap;
   2.384 -    }
   2.385 -
   2.386 -    /// \brief Sets the capacity map.
   2.387 -    ///
   2.388 -    /// Sets the capacity map.
   2.389 -    /// \return <tt> (*this) </tt>
   2.390 -    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
   2.391 -      _capacity = &m;
   2.392 -      return *this;
   2.393 -    }
   2.394 -
   2.395 -    /// \brief Sets the map storing the cardinalities calculated by the 
   2.396 -    /// algorithm.
   2.397 -    ///
   2.398 -    /// Sets the map storing the cardinalities calculated by the algorithm.
   2.399 -    /// If you don't use this function before calling \ref run(),
   2.400 -    /// it will allocate one. The destuctor deallocates this
   2.401 -    /// automatically allocated map, of course.
   2.402 -    /// \return <tt> (*this) </tt>
   2.403 -    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
   2.404 -      if(local_cardinality) {
   2.405 -	delete _cardinality;
   2.406 -	local_cardinality=false;
   2.407 -      }
   2.408 -      _cardinality = &m;
   2.409 -      return *this;
   2.410 -    }
   2.411 -
   2.412 -    /// \brief Sets the map storing the processed nodes.
   2.413 -    ///
   2.414 -    /// Sets the map storing the processed nodes.
   2.415 -    /// If you don't use this function before calling \ref run(),
   2.416 -    /// it will allocate one. The destuctor deallocates this
   2.417 -    /// automatically allocated map, of course.
   2.418 -    /// \return <tt> (*this) </tt>
   2.419 -    MaxCardinalitySearch &processedMap(ProcessedMap &m) 
   2.420 -    {
   2.421 -      if(local_processed) {
   2.422 -	delete _processed;
   2.423 -	local_processed=false;
   2.424 -      }
   2.425 -      _processed = &m;
   2.426 -      return *this;
   2.427 -    }
   2.428 -
   2.429 -    /// \brief Sets the heap and the cross reference used by algorithm.
   2.430 -    ///
   2.431 -    /// Sets the heap and the cross reference used by algorithm.
   2.432 -    /// If you don't use this function before calling \ref run(),
   2.433 -    /// it will allocate one. The destuctor deallocates this
   2.434 -    /// automatically allocated map, of course.
   2.435 -    /// \return <tt> (*this) </tt>
   2.436 -    MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
   2.437 -      if(local_heap_cross_ref) {
   2.438 -	delete _heap_cross_ref;
   2.439 -	local_heap_cross_ref = false;
   2.440 -      }
   2.441 -      _heap_cross_ref = &crossRef;
   2.442 -      if(local_heap) {
   2.443 -	delete _heap;
   2.444 -	local_heap = false;
   2.445 -      }
   2.446 -      _heap = &heap;
   2.447 -      return *this;
   2.448 -    }
   2.449 -
   2.450 -  private:
   2.451 -
   2.452 -    typedef typename Graph::Node Node;
   2.453 -    typedef typename Graph::NodeIt NodeIt;
   2.454 -    typedef typename Graph::Edge Edge;
   2.455 -    typedef typename Graph::InEdgeIt InEdgeIt;
   2.456 -
   2.457 -    void create_maps() {
   2.458 -      if(!_cardinality) {
   2.459 -	local_cardinality = true;
   2.460 -	_cardinality = Traits::createCardinalityMap(*_graph);
   2.461 -      }
   2.462 -      if(!_processed) {
   2.463 -	local_processed = true;
   2.464 -	_processed = Traits::createProcessedMap(*_graph);
   2.465 -      }
   2.466 -      if (!_heap_cross_ref) {
   2.467 -	local_heap_cross_ref = true;
   2.468 -	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
   2.469 -      }
   2.470 -      if (!_heap) {
   2.471 -	local_heap = true;
   2.472 -	_heap = Traits::createHeap(*_heap_cross_ref);
   2.473 -      }
   2.474 -    }
   2.475 -    
   2.476 -    void finalizeNodeData(Node node, Value capacity) {
   2.477 -      _processed->set(node, true);
   2.478 -      _cardinality->set(node, capacity);
   2.479 -    }
   2.480 -
   2.481 -  public:
   2.482 -    /// \name Execution control
   2.483 -    /// The simplest way to execute the algorithm is to use
   2.484 -    /// one of the member functions called \c run(...).
   2.485 -    /// \n
   2.486 -    /// If you need more control on the execution,
   2.487 -    /// first you must call \ref init(), then you can add several source nodes
   2.488 -    /// with \ref addSource().
   2.489 -    /// Finally \ref start() will perform the actual path
   2.490 -    /// computation.
   2.491 -
   2.492 -    ///@{
   2.493 -
   2.494 -    /// \brief Initializes the internal data structures.
   2.495 -    ///
   2.496 -    /// Initializes the internal data structures.
   2.497 -    void init() {
   2.498 -      create_maps();
   2.499 -      _heap->clear();
   2.500 -      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
   2.501 -	_processed->set(it, false);
   2.502 -	_heap_cross_ref->set(it, Heap::PRE_HEAP);
   2.503 -      }
   2.504 -    }
   2.505 -    
   2.506 -    /// \brief Adds a new source node.
   2.507 -    /// 
   2.508 -    /// Adds a new source node to the priority heap.
   2.509 -    ///
   2.510 -    /// It checks if the node has not yet been added to the heap.
   2.511 -    void addSource(Node source, Value capacity = 0) {
   2.512 -      if(_heap->state(source) == Heap::PRE_HEAP) {
   2.513 -	_heap->push(source, capacity);
   2.514 -      } 
   2.515 -    }
   2.516 -    
   2.517 -    /// \brief Processes the next node in the priority heap
   2.518 -    ///
   2.519 -    /// Processes the next node in the priority heap.
   2.520 -    ///
   2.521 -    /// \return The processed node.
   2.522 -    ///
   2.523 -    /// \warning The priority heap must not be empty!
   2.524 -    Node processNextNode() {
   2.525 -      Node node = _heap->top(); 
   2.526 -      finalizeNodeData(node, _heap->prio());
   2.527 -      _heap->pop();
   2.528 -      
   2.529 -      for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
   2.530 -	Node source = _graph->source(it); 
   2.531 -	switch (_heap->state(source)) {
   2.532 -	case Heap::PRE_HEAP:
   2.533 -	  _heap->push(source, (*_capacity)[it]); 
   2.534 -	  break;
   2.535 -	case Heap::IN_HEAP:
   2.536 -	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); 
   2.537 -	  break;
   2.538 -	case Heap::POST_HEAP:
   2.539 -	  break;
   2.540 -	}
   2.541 -      }
   2.542 -      return node;
   2.543 -    }
   2.544 -
   2.545 -    /// \brief Next node to be processed.
   2.546 -    ///
   2.547 -    /// Next node to be processed.
   2.548 -    ///
   2.549 -    /// \return The next node to be processed or INVALID if the 
   2.550 -    /// priority heap is empty.
   2.551 -    Node nextNode() { 
   2.552 -      return _heap->empty() ? _heap->top() : INVALID;
   2.553 -    }
   2.554 - 
   2.555 -    /// \brief Returns \c false if there are nodes
   2.556 -    /// to be processed in the priority heap
   2.557 -    ///
   2.558 -    /// Returns \c false if there are nodes
   2.559 -    /// to be processed in the priority heap
   2.560 -    bool emptyQueue() { return _heap->empty(); }
   2.561 -    /// \brief Returns the number of the nodes to be processed 
   2.562 -    /// in the priority heap
   2.563 -    ///
   2.564 -    /// Returns the number of the nodes to be processed in the priority heap
   2.565 -    int queueSize() { return _heap->size(); }
   2.566 -    
   2.567 -    /// \brief Executes the algorithm.
   2.568 -    ///
   2.569 -    /// Executes the algorithm.
   2.570 -    ///
   2.571 -    ///\pre init() must be called and at least one node should be added
   2.572 -    /// with addSource() before using this function.
   2.573 -    ///
   2.574 -    /// This method runs the Maximum Cardinality Search algorithm from the 
   2.575 -    /// source node(s).
   2.576 -    void start() {
   2.577 -      while ( !_heap->empty() ) processNextNode();
   2.578 -    }
   2.579 -    
   2.580 -    /// \brief Executes the algorithm until \c dest is reached.
   2.581 -    ///
   2.582 -    /// Executes the algorithm until \c dest is reached.
   2.583 -    ///
   2.584 -    /// \pre init() must be called and at least one node should be added
   2.585 -    /// with addSource() before using this function.
   2.586 -    ///
   2.587 -    /// This method runs the %MaxCardinalitySearch algorithm from the source 
   2.588 -    /// nodes.
   2.589 -    void start(Node dest) {
   2.590 -      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   2.591 -      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
   2.592 -    }
   2.593 -    
   2.594 -    /// \brief Executes the algorithm until a condition is met.
   2.595 -    ///
   2.596 -    /// Executes the algorithm until a condition is met.
   2.597 -    ///
   2.598 -    /// \pre init() must be called and at least one node should be added
   2.599 -    /// with addSource() before using this function.
   2.600 -    ///
   2.601 -    /// \param nm must be a bool (or convertible) node map. The algorithm
   2.602 -    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
   2.603 -    template <typename NodeBoolMap>
   2.604 -    void start(const NodeBoolMap &nm) {
   2.605 -      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   2.606 -      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
   2.607 -    }
   2.608 -    
   2.609 -    /// \brief Runs the maximal cardinality search algorithm from node \c s.
   2.610 -    ///
   2.611 -    /// This method runs the %MaxCardinalitySearch algorithm from a root 
   2.612 -    /// node \c s.
   2.613 -    ///
   2.614 -    ///\note d.run(s) is just a shortcut of the following code.
   2.615 -    ///\code
   2.616 -    ///  d.init();
   2.617 -    ///  d.addSource(s);
   2.618 -    ///  d.start();
   2.619 -    ///\endcode
   2.620 -    void run(Node s) {
   2.621 -      init();
   2.622 -      addSource(s);
   2.623 -      start();
   2.624 -    }
   2.625 -
   2.626 -    /// \brief Runs the maximal cardinality search algorithm for the 
   2.627 -    /// whole graph.
   2.628 -    ///
   2.629 -    /// This method runs the %MaxCardinalitySearch algorithm from all 
   2.630 -    /// unprocessed node of the graph.
   2.631 -    ///
   2.632 -    ///\note d.run(s) is just a shortcut of the following code.
   2.633 -    ///\code
   2.634 -    ///  d.init();
   2.635 -    ///  for (NodeIt it(graph); it != INVALID; ++it) {
   2.636 -    ///    if (!d.reached(it)) {
   2.637 -    ///      d.addSource(s);
   2.638 -    ///      d.start();
   2.639 -    ///    }
   2.640 -    ///  }
   2.641 -    ///\endcode
   2.642 -    void run() {
   2.643 -      init();
   2.644 -      for (NodeIt it(*_graph); it != INVALID; ++it) {
   2.645 -        if (!reached(it)) {
   2.646 -          addSource(it);
   2.647 -          start();
   2.648 -        }
   2.649 -      }
   2.650 -    }
   2.651 -    
   2.652 -    ///@}
   2.653 -
   2.654 -    /// \name Query Functions
   2.655 -    /// The result of the maximum cardinality search algorithm can be 
   2.656 -    /// obtained using these functions.
   2.657 -    /// \n
   2.658 -    /// Before the use of these functions, either run() or start() must be 
   2.659 -    /// called.
   2.660 -    
   2.661 -    ///@{
   2.662 -
   2.663 -    /// \brief The cardinality of a node.
   2.664 -    ///
   2.665 -    /// Returns the cardinality of a node.
   2.666 -    /// \pre \ref run() must be called before using this function.
   2.667 -    /// \warning If node \c v in unreachable from the root the return value
   2.668 -    /// of this funcion is undefined.
   2.669 -    Value cardinality(Node node) const { return (*_cardinality)[node]; }
   2.670 -
   2.671 -    /// \brief Returns a reference to the NodeMap of cardinalities.
   2.672 -    ///
   2.673 -    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
   2.674 -    /// must be called before using this function.
   2.675 -    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
   2.676 - 
   2.677 -    /// \brief Checks if a node is reachable from the root.
   2.678 -    ///
   2.679 -    /// Returns \c true if \c v is reachable from the root.
   2.680 -    /// \warning The source nodes are inditated as unreached.
   2.681 -    /// \pre \ref run() must be called before using this function.
   2.682 -    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   2.683 -
   2.684 -    /// \brief Checks if a node is processed.
   2.685 -    ///
   2.686 -    /// Returns \c true if \c v is processed, i.e. the shortest
   2.687 -    /// path to \c v has already found.
   2.688 -    /// \pre \ref run() must be called before using this function.
   2.689 -    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   2.690 -    
   2.691 -    ///@}
   2.692 -  };
   2.693 -
   2.694 -  /// \brief Default traits class of MinimalCut class.
   2.695 -  ///
   2.696 -  /// Default traits class of MinimalCut class.
   2.697 -  /// \param Graph Graph type.
   2.698 -  /// \param CapacityMap Type of length map.
   2.699 -  template <typename _Graph, typename _CapacityMap>
   2.700 -  struct MinimalCutDefaultTraits {
   2.701 -    /// \brief The type of the capacity of the edges.
   2.702 -    typedef typename _CapacityMap::Value Value;
   2.703 -
   2.704 -    /// The graph type the algorithm runs on. 
   2.705 -    typedef _Graph Graph;
   2.706 -
   2.707 -    /// The WorkGraph type which is an EraseableGraph
   2.708 -    typedef ListUGraph WorkGraph;
   2.709 -
   2.710 -    /// \brief Instantiates a WorkGraph.
   2.711 -    ///
   2.712 -    /// This function instantiates a \ref WorkGraph. 
   2.713 -    static WorkGraph *createWorkGraph() {
   2.714 -      return new WorkGraph();
   2.715 -    }
   2.716 -
   2.717 -    /// \brief The type of the map that stores the edge capacities.
   2.718 -    ///
   2.719 -    /// The type of the map that stores the edge capacities.
   2.720 -    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
   2.721 -    typedef _CapacityMap CapacityMap;
   2.722 -
   2.723 -    /// \brief Instantiates a CapacityMap.
   2.724 -    ///
   2.725 -    /// This function instantiates a \ref CapacityMap.
   2.726 -#ifdef DOXYGEN
   2.727 -    static CapacityMap *createCapacityMap(const Graph& graph) 
   2.728 -#else
   2.729 -    static CapacityMap *createCapacityMap(const Graph&)
   2.730 -#endif
   2.731 -    {
   2.732 -      throw UninitializedParameter();
   2.733 -    }
   2.734 -
   2.735 -    /// \brief The WorkCapacityMap type
   2.736 -    ///
   2.737 -    /// The type of the map that stores the working edge capacities.
   2.738 -    typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
   2.739 -
   2.740 -    /// \brief Instantiates a WorkCapacityMap.
   2.741 -    ///
   2.742 -    /// This function instantiates a \ref WorkCapacityMap. 
   2.743 -    static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
   2.744 -      return new WorkCapacityMap(graph);
   2.745 -    }
   2.746 -
   2.747 -    /// \brief The cross reference type used by heap.
   2.748 -    ///
   2.749 -    /// The cross reference type used by heap.
   2.750 -    /// Usually it is \c Graph::NodeMap<int>.
   2.751 -    typedef WorkGraph::NodeMap<int> HeapCrossRef;
   2.752 -
   2.753 -    /// \brief Instantiates a HeapCrossRef.
   2.754 -    ///
   2.755 -    /// This function instantiates a \ref HeapCrossRef. 
   2.756 -    /// \param graph is the graph, to which we would like to define the 
   2.757 -    /// HeapCrossRef.
   2.758 -    static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
   2.759 -      return new HeapCrossRef(graph);
   2.760 -    }
   2.761 -    
   2.762 -    /// \brief The heap type used by MinimalCut algorithm.
   2.763 -    ///
   2.764 -    /// The heap type used by MinimalCut algorithm. It should
   2.765 -    /// maximalize the priorities and the heap's key type is
   2.766 -    /// the work graph's node.
   2.767 -    ///
   2.768 -    /// \sa BinHeap
   2.769 -    /// \sa MinimalCut
   2.770 -    typedef typename _minimal_cut_bits
   2.771 -    ::HeapSelector<CapacityMap>
   2.772 -    ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
   2.773 -    ::Heap Heap;
   2.774 -    
   2.775 -    /// \brief Instantiates a Heap.
   2.776 -    ///
   2.777 -    /// This function instantiates a \ref Heap. 
   2.778 -    /// \param crossref The cross reference of the heap.
   2.779 -    static Heap *createHeap(HeapCrossRef& crossref) {
   2.780 -      return new Heap(crossref);
   2.781 -    }
   2.782 -
   2.783 -    /// \brief Map from the WorkGraph's node type to the Graph's node type.
   2.784 -    ///
   2.785 -    /// Map from the WorkGraph's node type to the Graph's node type.
   2.786 -    typedef typename WorkGraph
   2.787 -    ::template NodeMap<typename Graph::Node> NodeRefMap;
   2.788 -
   2.789 -    /// \brief Instantiates a NodeRefMap.
   2.790 -    ///
   2.791 -    /// This function instantiates a \ref NodeRefMap. 
   2.792 -    static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
   2.793 -      return new NodeRefMap(graph);
   2.794 -    }
   2.795 -
   2.796 -    /// \brief Map from the Graph's node type to the Graph's node type.
   2.797 -    ///
   2.798 -    /// Map from the Graph's node type to the Graph's node type.
   2.799 -    typedef typename Graph
   2.800 -    ::template NodeMap<typename Graph::Node> ListRefMap;
   2.801 -
   2.802 -    /// \brief Instantiates a ListRefMap.
   2.803 -    ///
   2.804 -    /// This function instantiates a \ref ListRefMap. 
   2.805 -    static ListRefMap *createListRefMap(const Graph& graph) {
   2.806 -      return new ListRefMap(graph);
   2.807 -    }
   2.808 -    
   2.809 -
   2.810 -  };
   2.811 -
   2.812 -  namespace _minimal_cut_bits {
   2.813 -    template <typename _Key>
   2.814 -    class LastTwoMap {
   2.815 -    public:
   2.816 -      typedef _Key Key;
   2.817 -      typedef bool Value;
   2.818 -
   2.819 -      LastTwoMap(int _num) : num(_num) {}
   2.820 -      void set(const Key& key, bool val) {
   2.821 -        if (!val) return;
   2.822 -        --num;
   2.823 -        if (num > 1) return;
   2.824 -        keys[num] = key;
   2.825 -      }
   2.826 -      
   2.827 -      Key operator[](int index) const { return keys[index]; }
   2.828 -    private:
   2.829 -      Key keys[2];
   2.830 -      int num;
   2.831 -    };
   2.832 -  }
   2.833 -
   2.834 -  /// \ingroup topology
   2.835 -  ///
   2.836 -  /// \brief Calculates the minimal cut in an undirected graph.
   2.837 -  ///
   2.838 -  /// Calculates the minimal cut in an undirected graph. 
   2.839 -  /// The algorithm separates the graph's nodes to two partitions with the 
   2.840 -  /// minimal sum of edge capacities between the two partitions. The
   2.841 -  /// algorithm can be used to test the network reliability specifically
   2.842 -  /// to test how many links have to be destroyed in the network to split it 
   2.843 -  /// at least two distinict subnetwork.
   2.844 -  ///
   2.845 -  /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci 
   2.846 -  /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity 
   2.847 -  /// map is used then it uses LinearHeap which results O(n*e) time complexity.
   2.848 -#ifdef DOXYGEN
   2.849 -  template <typename _Graph, typename _CapacityMap, typename _Traits>
   2.850 -#else
   2.851 -  template <typename _Graph = ListUGraph, 
   2.852 -	    typename _CapacityMap = typename _Graph::template UEdgeMap<int>, 
   2.853 -	    typename _Traits = MinimalCutDefaultTraits<_Graph, _CapacityMap> >
   2.854 -#endif
   2.855 -  class MinimalCut {
   2.856 -  public:
   2.857 -    /// \brief \ref Exception for uninitialized parameters.
   2.858 -    ///
   2.859 -    /// This error represents problems in the initialization
   2.860 -    /// of the parameters of the algorithms.
   2.861 -    class UninitializedParameter : public lemon::UninitializedParameter {
   2.862 -    public:
   2.863 -      virtual const char* exceptionName() const {
   2.864 -	return "lemon::MinimalCut::UninitializedParameter";
   2.865 -      }
   2.866 -    };
   2.867 -
   2.868 -
   2.869 -  private:
   2.870 -
   2.871 -    typedef _Traits Traits;
   2.872 -    /// The type of the underlying graph.
   2.873 -    typedef typename Traits::Graph Graph;
   2.874 -    
   2.875 -    /// The type of the capacity of the edges.
   2.876 -    typedef typename Traits::CapacityMap::Value Value;
   2.877 -    /// The type of the map that stores the edge capacities.
   2.878 -    typedef typename Traits::CapacityMap CapacityMap;
   2.879 -    /// The type of the work graph
   2.880 -    typedef typename Traits::WorkGraph WorkGraph;
   2.881 -    /// The type of the work capacity map
   2.882 -    typedef typename Traits::WorkCapacityMap WorkCapacityMap;
   2.883 -    /// The cross reference type used for the current heap.
   2.884 -    typedef typename Traits::HeapCrossRef HeapCrossRef;
   2.885 -    /// The heap type used by the max cardinality algorithm.
   2.886 -    typedef typename Traits::Heap Heap;
   2.887 -    /// The node refrefernces between the original and work graph type.
   2.888 -    typedef typename Traits::NodeRefMap NodeRefMap;
   2.889 -    /// The list node refrefernces in the original graph type.
   2.890 -    typedef typename Traits::ListRefMap ListRefMap;
   2.891 -
   2.892 -  public:
   2.893 -
   2.894 -    ///\name Named template parameters
   2.895 -
   2.896 -    ///@{
   2.897 -
   2.898 -    struct DefNeutralCapacityTraits : public Traits {
   2.899 -      typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
   2.900 -      static CapacityMap *createCapacityMap(const Graph&) {
   2.901 -	return new CapacityMap();
   2.902 -      }
   2.903 -    };
   2.904 -    /// \brief \ref named-templ-param "Named parameter" for setting  
   2.905 -    /// the capacity type to constMap<UEdge, int, 1>()
   2.906 -    ///
   2.907 -    /// \ref named-templ-param "Named parameter" for setting 
   2.908 -    /// the capacity type to constMap<UEdge, int, 1>()
   2.909 -    struct DefNeutralCapacity
   2.910 -      : public MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 
   2.911 -      typedef MinimalCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
   2.912 -    };
   2.913 -
   2.914 -
   2.915 -    template <class H, class CR>
   2.916 -    struct DefHeapTraits : public Traits {
   2.917 -      typedef CR HeapCrossRef;
   2.918 -      typedef H Heap;
   2.919 -      static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
   2.920 -	throw UninitializedParameter();
   2.921 -      }
   2.922 -      static Heap *createHeap(HeapCrossRef &) {
   2.923 -	throw UninitializedParameter();
   2.924 -      }
   2.925 -    };
   2.926 -    /// \brief \ref named-templ-param "Named parameter" for setting heap 
   2.927 -    /// and cross reference type
   2.928 -    ///
   2.929 -    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   2.930 -    /// reference type
   2.931 -    template <class H, class CR = typename Graph::template NodeMap<int> >
   2.932 -    struct DefHeap
   2.933 -      : public MinimalCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 
   2.934 -      typedef MinimalCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
   2.935 -    };
   2.936 -
   2.937 -    template <class H, class CR>
   2.938 -    struct DefStandardHeapTraits : public Traits {
   2.939 -      typedef CR HeapCrossRef;
   2.940 -      typedef H Heap;
   2.941 -      static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
   2.942 -	return new HeapCrossRef(graph);
   2.943 -      }
   2.944 -      static Heap *createHeap(HeapCrossRef &crossref) {
   2.945 -	return new Heap(crossref);
   2.946 -      }
   2.947 -    };
   2.948 -
   2.949 -    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   2.950 -    /// cross reference type with automatic allocation
   2.951 -    ///
   2.952 -    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   2.953 -    /// reference type. It can allocate the heap and the cross reference 
   2.954 -    /// object if the cross reference's constructor waits for the graph as 
   2.955 -    /// parameter and the heap's constructor waits for the cross reference.
   2.956 -    template <class H, class CR = typename Graph::template NodeMap<int> >
   2.957 -    struct DefStandardHeap
   2.958 -      : public MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 
   2.959 -      typedef MinimalCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 
   2.960 -      Create;
   2.961 -    };
   2.962 -
   2.963 -    ///@}
   2.964 -
   2.965 -
   2.966 -  private:
   2.967 -    /// Pointer to the underlying graph.
   2.968 -    const Graph *_graph;
   2.969 -    /// Pointer to the capacity map
   2.970 -    const CapacityMap *_capacity;
   2.971 -    /// \brief Indicates if \ref _capacity is locally allocated 
   2.972 -    /// (\c true) or not.
   2.973 -    bool local_capacity;
   2.974 -
   2.975 -    /// Pointer to the work graph.
   2.976 -    WorkGraph *_work_graph;
   2.977 -    /// \brief Indicates if \ref _work_graph is locally allocated 
   2.978 -    /// (\c true) or not.
   2.979 -    bool local_work_graph;
   2.980 -    /// Pointer to the work capacity map
   2.981 -    WorkCapacityMap *_work_capacity;
   2.982 -    /// \brief Indicates if \ref _work_capacity is locally allocated 
   2.983 -    /// (\c true) or not.
   2.984 -    bool local_work_capacity;
   2.985 -    /// Pointer to the heap cross references.
   2.986 -    HeapCrossRef *_heap_cross_ref;
   2.987 -    /// \brief Indicates if \ref _heap_cross_ref is locally allocated 
   2.988 -    /// (\c true) or not.
   2.989 -    bool local_heap_cross_ref;
   2.990 -    /// Pointer to the heap.
   2.991 -    Heap *_heap;
   2.992 -    /// Indicates if \ref _heap is locally allocated (\c true) or not.
   2.993 -    bool local_heap;
   2.994 -
   2.995 -    /// The minimal cut value.
   2.996 -    Value _minimal_cut;
   2.997 -    /// The number of the nodes of the work graph.
   2.998 -    int _node_num;
   2.999 -    /// The first and last node of the min cut in the next list;
  2.1000 -    typename Graph::Node _first_node, _last_node;
  2.1001 -
  2.1002 -    /// \brief The first and last element in the list associated
  2.1003 -    /// to the work graph node.
  2.1004 -    NodeRefMap *_first, *_last;
  2.1005 -    /// \brief The next node in the node lists.
  2.1006 -    ListRefMap *_next;
  2.1007 -    
  2.1008 -    void create_structures() {
  2.1009 -      if (!_capacity) {
  2.1010 -        local_capacity = true;
  2.1011 -        _capacity = Traits::createCapacityMap(*_graph);
  2.1012 -      }
  2.1013 -      if(!_work_graph) {
  2.1014 -	local_work_graph = true;
  2.1015 -	_work_graph = Traits::createWorkGraph();
  2.1016 -      }
  2.1017 -      if(!_work_capacity) {
  2.1018 -	local_work_capacity = true;
  2.1019 -	_work_capacity = Traits::createWorkCapacityMap(*_work_graph);
  2.1020 -      }
  2.1021 -
  2.1022 -      _first = Traits::createNodeRefMap(*_work_graph);
  2.1023 -      _last = Traits::createNodeRefMap(*_work_graph);
  2.1024 -
  2.1025 -      _next = Traits::createListRefMap(*_graph);
  2.1026 -
  2.1027 -      typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
  2.1028 -
  2.1029 -      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  2.1030 -        _next->set(it, INVALID);
  2.1031 -        typename WorkGraph::Node node = _work_graph->addNode();
  2.1032 -        _first->set(node, it);
  2.1033 -        _last->set(node, it);
  2.1034 -        ref.set(it, node);
  2.1035 -      }
  2.1036 -
  2.1037 -      for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
  2.1038 -        if (_graph->source(it) == _graph->target(it)) continue;
  2.1039 -        typename WorkGraph::UEdge uedge = 
  2.1040 -          _work_graph->addEdge(ref[_graph->source(it)], 
  2.1041 -                               ref[_graph->target(it)]);
  2.1042 -        _work_capacity->set(uedge, (*_capacity)[it]);
  2.1043 -        
  2.1044 -      }
  2.1045 -
  2.1046 -      if (!_heap_cross_ref) {
  2.1047 -	local_heap_cross_ref = true;
  2.1048 -	_heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
  2.1049 -      }
  2.1050 -      if (!_heap) {
  2.1051 -	local_heap = true;
  2.1052 -	_heap = Traits::createHeap(*_heap_cross_ref);
  2.1053 -      }
  2.1054 -    }
  2.1055 -
  2.1056 -  public :
  2.1057 -
  2.1058 -    typedef MinimalCut Create;
  2.1059 -
  2.1060 -
  2.1061 -    /// \brief Constructor.
  2.1062 -    ///
  2.1063 -    ///\param graph the graph the algorithm will run on.
  2.1064 -    ///\param capacity the capacity map used by the algorithm.
  2.1065 -    MinimalCut(const Graph& graph, const CapacityMap& capacity) 
  2.1066 -      : _graph(&graph), 
  2.1067 -        _capacity(&capacity), local_capacity(false),
  2.1068 -        _work_graph(0), local_work_graph(false),
  2.1069 -        _work_capacity(0), local_work_capacity(false),
  2.1070 -        _heap_cross_ref(0), local_heap_cross_ref(false),
  2.1071 -        _heap(0), local_heap(false),
  2.1072 -        _first(0), _last(0), _next(0) {}
  2.1073 -
  2.1074 -    /// \brief Constructor.
  2.1075 -    ///
  2.1076 -    /// This constructor can be used only when the Traits class
  2.1077 -    /// defines how can we instantiate a local capacity map.
  2.1078 -    /// If the DefNeutralCapacity used the algorithm automatically
  2.1079 -    /// construct the capacity map.
  2.1080 -    ///
  2.1081 -    ///\param graph the graph the algorithm will run on.
  2.1082 -    MinimalCut(const Graph& graph) 
  2.1083 -      : _graph(&graph), 
  2.1084 -        _capacity(0), local_capacity(false),
  2.1085 -        _work_graph(0), local_work_graph(false),
  2.1086 -        _work_capacity(0), local_work_capacity(false),
  2.1087 -        _heap_cross_ref(0), local_heap_cross_ref(false),
  2.1088 -        _heap(0), local_heap(false),
  2.1089 -        _first(0), _last(0), _next(0) {}
  2.1090 -
  2.1091 -    /// \brief Destructor.
  2.1092 -    ///
  2.1093 -    /// Destructor.
  2.1094 -    ~MinimalCut() {
  2.1095 -      if (local_heap) delete _heap;
  2.1096 -      if (local_heap_cross_ref) delete _heap_cross_ref;
  2.1097 -      if (_first) delete _first;
  2.1098 -      if (_last) delete _last;
  2.1099 -      if (_next) delete _next;
  2.1100 -      if (local_work_capacity) delete _work_capacity;
  2.1101 -      if (local_work_graph) delete _work_graph;
  2.1102 -      if (local_capacity) delete _capacity;
  2.1103 -    }
  2.1104 -
  2.1105 -    /// \brief Sets the heap and the cross reference used by algorithm.
  2.1106 -    ///
  2.1107 -    /// Sets the heap and the cross reference used by algorithm.
  2.1108 -    /// If you don't use this function before calling \ref run(),
  2.1109 -    /// it will allocate one. The destuctor deallocates this
  2.1110 -    /// automatically allocated heap and cross reference, of course.
  2.1111 -    /// \return <tt> (*this) </tt>
  2.1112 -    MinimalCut &heap(Heap& heap, HeapCrossRef &crossRef)
  2.1113 -    {
  2.1114 -      if (local_heap_cross_ref) {
  2.1115 -	delete _heap_cross_ref;
  2.1116 -	local_heap_cross_ref=false;
  2.1117 -      }
  2.1118 -      _heap_cross_ref = &crossRef;
  2.1119 -      if (local_heap) {
  2.1120 -	delete _heap;
  2.1121 -	local_heap=false;
  2.1122 -      }
  2.1123 -      _heap = &heap;
  2.1124 -      return *this;
  2.1125 -    }
  2.1126 -
  2.1127 -    /// \brief Sets the work graph.
  2.1128 -    ///
  2.1129 -    /// Sets the work graph used by algorithm.
  2.1130 -    /// If you don't use this function before calling \ref run(),
  2.1131 -    /// it will allocate one. The destuctor deallocates this
  2.1132 -    /// automatically allocated graph, of course.
  2.1133 -    /// \return <tt> (*this) </tt>
  2.1134 -    MinimalCut &workGraph(WorkGraph& work_graph)
  2.1135 -    {
  2.1136 -      if(local_work_graph) {
  2.1137 -	delete _work_graph;
  2.1138 -	local_work_graph=false;
  2.1139 -      }
  2.1140 -      _work_graph = &work_graph;
  2.1141 -      return *this;
  2.1142 -    }
  2.1143 -
  2.1144 -    /// \brief Sets the work capacity map.
  2.1145 -    ///
  2.1146 -    /// Sets the work capacity map used by algorithm.
  2.1147 -    /// If you don't use this function before calling \ref run(),
  2.1148 -    /// it will allocate one. The destuctor deallocates this
  2.1149 -    /// automatically allocated graph, of course.
  2.1150 -    /// \return <tt> (*this) </tt>
  2.1151 -    MinimalCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
  2.1152 -    {
  2.1153 -      if(local_work_capacity) {
  2.1154 -	delete _work_capacity;
  2.1155 -	local_work_capacity=false;
  2.1156 -      }
  2.1157 -      _work_capacity = &work_capacity_map;
  2.1158 -      return *this;
  2.1159 -    }
  2.1160 -
  2.1161 -    /// \name Execution control
  2.1162 -    /// The simplest way to execute the algorithm is to use
  2.1163 -    /// one of the member functions called \c run().
  2.1164 -    /// \n
  2.1165 -    /// If you need more control on the execution,
  2.1166 -    /// first you must call \ref init() and then call the start()
  2.1167 -    /// or proper times the processNextPhase() member functions.
  2.1168 -
  2.1169 -    ///@{
  2.1170 -
  2.1171 -    /// \brief Initializes the internal data structures.
  2.1172 -    ///
  2.1173 -    /// Initializes the internal data structures.
  2.1174 -    void init() {
  2.1175 -      create_structures();
  2.1176 -      _first_node = _last_node = INVALID;
  2.1177 -      _node_num = countNodes(*_graph);
  2.1178 -    }
  2.1179 -
  2.1180 -    /// \brief Processes the next phase
  2.1181 -    ///
  2.1182 -    /// Processes the next phase in the algorithm. The function
  2.1183 -    /// should be called countNodes(graph) - 1 times to get
  2.1184 -    /// surely the minimal cut in the graph. The  
  2.1185 -    ///
  2.1186 -    ///\return %True when the algorithm finished.
  2.1187 -    bool processNextPhase() {
  2.1188 -      if (_node_num <= 1) return true;
  2.1189 -      using namespace _minimal_cut_bits;
  2.1190 -
  2.1191 -      typedef typename WorkGraph::Node Node;
  2.1192 -      typedef typename WorkGraph::NodeIt NodeIt;
  2.1193 -      typedef typename WorkGraph::UEdge UEdge;
  2.1194 -      typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
  2.1195 -      
  2.1196 -      typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
  2.1197 -      template DefHeap<Heap, HeapCrossRef>::
  2.1198 -      template DefCardinalityMap<NullMap<Node, Value> >::
  2.1199 -      template DefProcessedMap<LastTwoMap<Node> >::
  2.1200 -      Create MaxCardinalitySearch;
  2.1201 -      
  2.1202 -      MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
  2.1203 -      for (NodeIt it(*_work_graph); it != INVALID; ++it) {
  2.1204 -        _heap_cross_ref->set(it, Heap::PRE_HEAP);
  2.1205 -      }
  2.1206 -      mcs.heap(*_heap, *_heap_cross_ref);
  2.1207 -
  2.1208 -      LastTwoMap<Node> last_two_nodes(_node_num);
  2.1209 -      mcs.processedMap(last_two_nodes);
  2.1210 -
  2.1211 -      NullMap<Node, Value> cardinality;
  2.1212 -      mcs.cardinalityMap(cardinality);
  2.1213 -
  2.1214 -      mcs.run();
  2.1215 -
  2.1216 -      Node new_node = _work_graph->addNode();
  2.1217 -
  2.1218 -      typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
  2.1219 -      
  2.1220 -      Node first_node = last_two_nodes[0];
  2.1221 -      Node second_node = last_two_nodes[1];
  2.1222 -      
  2.1223 -      _next->set((*_last)[first_node], (*_first)[second_node]);
  2.1224 -      _first->set(new_node, (*_first)[first_node]);
  2.1225 -      _last->set(new_node, (*_last)[second_node]);
  2.1226 -
  2.1227 -      Value current_cut = 0;      
  2.1228 -      for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
  2.1229 -        Node node = _work_graph->runningNode(it);
  2.1230 -        current_cut += (*_work_capacity)[it];
  2.1231 -        if (node == second_node) continue;
  2.1232 -        if (edges[node] == INVALID) {
  2.1233 -          edges[node] = _work_graph->addEdge(new_node, node);
  2.1234 -          (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
  2.1235 -        } else {
  2.1236 -          (*_work_capacity)[edges[node]] += (*_work_capacity)[it];          
  2.1237 -        }
  2.1238 -      }
  2.1239 -
  2.1240 -      if (_first_node == INVALID || current_cut < _minimal_cut) {
  2.1241 -        _first_node = (*_first)[first_node];
  2.1242 -        _last_node = (*_last)[first_node];
  2.1243 -        _minimal_cut = current_cut;
  2.1244 -      }
  2.1245 -
  2.1246 -      _work_graph->erase(first_node);
  2.1247 -
  2.1248 -      for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
  2.1249 -        Node node = _work_graph->runningNode(it);
  2.1250 -        if (edges[node] == INVALID) {
  2.1251 -          edges[node] = _work_graph->addEdge(new_node, node);
  2.1252 -          (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
  2.1253 -        } else {
  2.1254 -          (*_work_capacity)[edges[node]] += (*_work_capacity)[it];          
  2.1255 -        }
  2.1256 -      }
  2.1257 -      _work_graph->erase(second_node);
  2.1258 -
  2.1259 -      --_node_num;
  2.1260 -      return _node_num == 1;
  2.1261 -    }
  2.1262 -
  2.1263 -    /// \brief Executes the algorithm.
  2.1264 -    ///
  2.1265 -    /// Executes the algorithm.
  2.1266 -    ///
  2.1267 -    /// \pre init() must be called
  2.1268 -    void start() {
  2.1269 -      while (!processNextPhase());
  2.1270 -    }
  2.1271 -
  2.1272 -
  2.1273 -    /// \brief Runs %MinimalCut algorithm.
  2.1274 -    ///
  2.1275 -    /// This method runs the %Minimal cut algorithm
  2.1276 -    ///
  2.1277 -    /// \note mc.run(s) is just a shortcut of the following code.
  2.1278 -    ///\code
  2.1279 -    ///  mc.init();
  2.1280 -    ///  mc.start();
  2.1281 -    ///\endcode
  2.1282 -    void run() {
  2.1283 -      init();
  2.1284 -      start();
  2.1285 -    }
  2.1286 -
  2.1287 -    ///@}
  2.1288 -
  2.1289 -    /// \name Query Functions
  2.1290 -    /// The result of the %MinimalCut algorithm can be obtained using these
  2.1291 -    /// functions.\n
  2.1292 -    /// Before the use of these functions,
  2.1293 -    /// either run() or start() must be called.
  2.1294 -    
  2.1295 -    ///@{
  2.1296 -
  2.1297 -    /// \brief Returns the minimal cut value.
  2.1298 -    ///
  2.1299 -    /// Returns the minimal cut value if the algorithm finished.
  2.1300 -    /// After the first processNextPhase() it is a value of a
  2.1301 -    /// valid cut in the graph.
  2.1302 -    Value minCut() const {
  2.1303 -      return _minimal_cut;
  2.1304 -    }
  2.1305 -
  2.1306 -    /// \brief Returns a minimal cut in a NodeMap.
  2.1307 -    ///
  2.1308 -    /// It sets the nodes of one of the two partitions to true in
  2.1309 -    /// the given BoolNodeMap. The map contains a valid cut if the
  2.1310 -    /// map have been setted false previously. 
  2.1311 -    template <typename NodeMap>
  2.1312 -    Value quickMinCut(NodeMap& nodeMap) const { 
  2.1313 -      for (typename Graph::Node it = _first_node; 
  2.1314 -           it != _last_node; it = (*_next)[it]) {
  2.1315 -             nodeMap.set(it, true);
  2.1316 -           }
  2.1317 -      nodeMap.set(_last_node, true);
  2.1318 -      return minCut();
  2.1319 -    }
  2.1320 -
  2.1321 -    /// \brief Returns a minimal cut in a NodeMap.
  2.1322 -    ///
  2.1323 -    /// It sets the nodes of one of the two partitions to true and
  2.1324 -    /// the other partition to false. The function first set all of the
  2.1325 -    /// nodes to false and after it call the quickMinCut() member.
  2.1326 -    template <typename NodeMap>
  2.1327 -    Value minCut(NodeMap& nodeMap) const { 
  2.1328 -      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  2.1329 -        nodeMap.set(it, false);      
  2.1330 -      }
  2.1331 -      quickMinCut(nodeMap);
  2.1332 -      return minCut();
  2.1333 -    }
  2.1334 -
  2.1335 -    /// \brief Returns a minimal cut in an EdgeMap.
  2.1336 -    ///
  2.1337 -    /// If an undirected edge is cut edge then it will be
  2.1338 -    /// setted to true and the others will be setted to false in the given map.
  2.1339 -    template <typename EdgeMap>
  2.1340 -    Value cutEdges(EdgeMap& edgeMap) const {
  2.1341 -      typename Graph::template NodeMap<bool> cut(*_graph, false);
  2.1342 -      quickMinCut(cut);
  2.1343 -      for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
  2.1344 -        edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
  2.1345 -      }
  2.1346 -      return minCut();
  2.1347 -    }
  2.1348 -
  2.1349 -    ///@}
  2.1350 -
  2.1351 -  };
  2.1352 -}
  2.1353 -
  2.1354 -#endif
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/minimum_cut.h	Tue Feb 14 10:41:16 2006 +0000
     3.3 @@ -0,0 +1,1351 @@
     3.4 +/* -*- C++ -*-
     3.5 + * lemon/minimum_cut.h - Part of LEMON, a generic C++ optimization library
     3.6 + *
     3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
     3.9 + *
    3.10 + * Permission to use, modify and distribute this software is granted
    3.11 + * provided that this copyright notice appears in all copies. For
    3.12 + * precise terms see the accompanying LICENSE file.
    3.13 + *
    3.14 + * This software is provided "AS IS" with no warranty of any kind,
    3.15 + * express or implied, and with no claim as to its suitability for any
    3.16 + * purpose.
    3.17 + *
    3.18 + */
    3.19 +
    3.20 +#ifndef LEMON_MINIMUM_CUT_H
    3.21 +#define LEMON_MINIMUM_CUT_H
    3.22 +
    3.23 +
    3.24 +/// \ingroup topology
    3.25 +/// \file
    3.26 +/// \brief Maximum cardinality search and minimum cut in undirected graphs.
    3.27 +
    3.28 +#include <lemon/list_graph.h>
    3.29 +#include <lemon/bin_heap.h>
    3.30 +#include <lemon/linear_heap.h>
    3.31 +
    3.32 +#include <lemon/invalid.h>
    3.33 +#include <lemon/error.h>
    3.34 +#include <lemon/maps.h>
    3.35 +
    3.36 +#include <functional>
    3.37 +
    3.38 +namespace lemon {
    3.39 +
    3.40 +  namespace _minimum_cut_bits {
    3.41 +
    3.42 +    template <typename CapacityMap>
    3.43 +    struct HeapSelector {
    3.44 +      template <typename Key, typename Value, typename Ref>
    3.45 +      struct Selector {
    3.46 +        typedef BinHeap<Key, Value, Ref, std::greater<Value> > Heap;
    3.47 +      };
    3.48 +    };
    3.49 +
    3.50 +    template <typename CapacityKey>
    3.51 +    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
    3.52 +      template <typename Key, typename Value, typename Ref>
    3.53 +      struct Selector {
    3.54 +        typedef LinearHeap<Key, Ref, false > Heap;
    3.55 +      };
    3.56 +    };
    3.57 +
    3.58 +  }
    3.59 +
    3.60 +  /// \brief Default traits class of MaxCardinalitySearch class.
    3.61 +  ///
    3.62 +  /// Default traits class of MaxCardinalitySearch class.
    3.63 +  /// \param Graph Graph type.
    3.64 +  /// \param CapacityMap Type of length map.
    3.65 +  template <typename _Graph, typename _CapacityMap>
    3.66 +  struct MaxCardinalitySearchDefaultTraits {
    3.67 +    /// The graph type the algorithm runs on. 
    3.68 +    typedef _Graph Graph;
    3.69 +
    3.70 +    /// \brief The type of the map that stores the edge capacities.
    3.71 +    ///
    3.72 +    /// The type of the map that stores the edge capacities.
    3.73 +    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
    3.74 +    typedef _CapacityMap CapacityMap;
    3.75 +
    3.76 +    /// \brief The type of the capacity of the edges.
    3.77 +    typedef typename CapacityMap::Value Value;
    3.78 +
    3.79 +    /// \brief The cross reference type used by heap.
    3.80 +    ///
    3.81 +    /// The cross reference type used by heap.
    3.82 +    /// Usually it is \c Graph::NodeMap<int>.
    3.83 +    typedef typename Graph::template NodeMap<int> HeapCrossRef;
    3.84 +
    3.85 +    /// \brief Instantiates a HeapCrossRef.
    3.86 +    ///
    3.87 +    /// This function instantiates a \ref HeapCrossRef. 
    3.88 +    /// \param graph is the graph, to which we would like to define the 
    3.89 +    /// HeapCrossRef.
    3.90 +    static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
    3.91 +      return new HeapCrossRef(graph);
    3.92 +    }
    3.93 +    
    3.94 +    /// \brief The heap type used by MaxCardinalitySearch algorithm.
    3.95 +    ///
    3.96 +    /// The heap type used by MaxCardinalitySearch algorithm. It should
    3.97 +    /// maximalize the priorities. The default heap type is
    3.98 +    /// the \ref BinHeap, but it is specialized when the
    3.99 +    /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
   3.100 +    /// to LinearHeap.
   3.101 +    ///
   3.102 +    /// \sa MaxCardinalitySearch
   3.103 +    typedef typename _minimum_cut_bits
   3.104 +    ::HeapSelector<CapacityMap>
   3.105 +    ::template Selector<typename Graph::Node, Value, HeapCrossRef>
   3.106 +    ::Heap Heap;
   3.107 +
   3.108 +    /// \brief Instantiates a Heap.
   3.109 +    ///
   3.110 +    /// This function instantiates a \ref Heap. 
   3.111 +    /// \param crossref The cross reference of the heap.
   3.112 +    static Heap *createHeap(HeapCrossRef& crossref) {
   3.113 +      return new Heap(crossref);
   3.114 +    }
   3.115 +
   3.116 +    /// \brief The type of the map that stores whether a nodes is processed.
   3.117 +    ///
   3.118 +    /// The type of the map that stores whether a nodes is processed.
   3.119 +    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   3.120 +    /// By default it is a NullMap.
   3.121 +    typedef NullMap<typename Graph::Node, bool> ProcessedMap;
   3.122 +
   3.123 +    /// \brief Instantiates a ProcessedMap.
   3.124 +    ///
   3.125 +    /// This function instantiates a \ref ProcessedMap. 
   3.126 +    /// \param g is the graph, to which
   3.127 +    /// we would like to define the \ref ProcessedMap
   3.128 +#ifdef DOXYGEN
   3.129 +    static ProcessedMap *createProcessedMap(const Graph &graph)
   3.130 +#else
   3.131 +    static ProcessedMap *createProcessedMap(const Graph &)
   3.132 +#endif
   3.133 +    {
   3.134 +      return new ProcessedMap();
   3.135 +    }
   3.136 +
   3.137 +    /// \brief The type of the map that stores the cardinalties of the nodes.
   3.138 +    /// 
   3.139 +    /// The type of the map that stores the cardinalities of the nodes.
   3.140 +    /// It must meet the \ref concept::WriteMap "WriteMap" concept.
   3.141 +    typedef typename Graph::template NodeMap<Value> CardinalityMap;
   3.142 +
   3.143 +    /// \brief Instantiates a CardinalityMap.
   3.144 +    ///
   3.145 +    /// This function instantiates a \ref CardinalityMap. 
   3.146 +    /// \param graph is the graph, to which we would like to define the \ref 
   3.147 +    /// CardinalityMap
   3.148 +    static CardinalityMap *createCardinalityMap(const Graph &graph) {
   3.149 +      return new CardinalityMap(graph);
   3.150 +    }
   3.151 +
   3.152 +  };
   3.153 +  
   3.154 +  /// \ingroup topology
   3.155 +  ///
   3.156 +  /// \brief Maximum Cardinality Search algorithm class.
   3.157 +  ///
   3.158 +  /// This class provides an efficient implementation of Maximum Cardinality 
   3.159 +  /// Search algorithm. The maximum cardinality search chooses first time any 
   3.160 +  /// node of the graph. Then every time chooses that node which connected
   3.161 +  /// to the processed nodes at most in the sum of capacities on the out 
   3.162 +  /// edges. If there is a cut in the graph the algorithm should choose
   3.163 +  /// again any unprocessed node of the graph. Each nodes cardinality is
   3.164 +  /// the sum of capacities on the out edges to the nodes which are processed
   3.165 +  /// before the given node.
   3.166 +  ///
   3.167 +  /// The edge capacities are passed to the algorithm using a
   3.168 +  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any 
   3.169 +  /// kind of capacity.
   3.170 +  ///
   3.171 +  /// The type of the capacity is determined by the \ref 
   3.172 +  /// concept::ReadMap::Value "Value" of the capacity map.
   3.173 +  ///
   3.174 +  /// It is also possible to change the underlying priority heap.
   3.175 +  ///
   3.176 +  ///
   3.177 +  /// \param _Graph The graph type the algorithm runs on. The default value
   3.178 +  /// is \ref ListGraph. The value of Graph is not used directly by
   3.179 +  /// the search algorithm, it is only passed to 
   3.180 +  /// \ref MaxCardinalitySearchDefaultTraits.
   3.181 +  /// \param _CapacityMap This read-only EdgeMap determines the capacities of 
   3.182 +  /// the edges. It is read once for each edge, so the map may involve in
   3.183 +  /// relatively time consuming process to compute the edge capacity if
   3.184 +  /// it is necessary. The default map type is \ref
   3.185 +  /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
   3.186 +  /// of CapacityMap is not used directly by search algorithm, it is only 
   3.187 +  /// passed to \ref MaxCardinalitySearchDefaultTraits.  
   3.188 +  /// \param _Traits Traits class to set various data types used by the 
   3.189 +  /// algorithm.  The default traits class is 
   3.190 +  /// \ref MaxCardinalitySearchDefaultTraits 
   3.191 +  /// "MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>".  
   3.192 +  /// See \ref MaxCardinalitySearchDefaultTraits 
   3.193 +  /// for the documentation of a MaxCardinalitySearch traits class.
   3.194 +  ///
   3.195 +  /// \author Balazs Dezso
   3.196 +
   3.197 +#ifdef DOXYGEN
   3.198 +  template <typename _Graph, typename _CapacityMap, typename _Traits>
   3.199 +#else
   3.200 +  template <typename _Graph = ListUGraph,
   3.201 +	    typename _CapacityMap = typename _Graph::template EdgeMap<int>,
   3.202 +	    typename _Traits = 
   3.203 +            MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap> >
   3.204 +#endif
   3.205 +  class MaxCardinalitySearch {
   3.206 +  public:
   3.207 +    /// \brief \ref Exception for uninitialized parameters.
   3.208 +    ///
   3.209 +    /// This error represents problems in the initialization
   3.210 +    /// of the parameters of the algorithms.
   3.211 +    class UninitializedParameter : public lemon::UninitializedParameter {
   3.212 +    public:
   3.213 +      virtual const char* exceptionName() const {
   3.214 +	return "lemon::MaxCardinalitySearch::UninitializedParameter";
   3.215 +      }
   3.216 +    };
   3.217 +
   3.218 +    typedef _Traits Traits;
   3.219 +    ///The type of the underlying graph.
   3.220 +    typedef typename Traits::Graph Graph;
   3.221 +    
   3.222 +    ///The type of the capacity of the edges.
   3.223 +    typedef typename Traits::CapacityMap::Value Value;
   3.224 +    ///The type of the map that stores the edge capacities.
   3.225 +    typedef typename Traits::CapacityMap CapacityMap;
   3.226 +    ///The type of the map indicating if a node is processed.
   3.227 +    typedef typename Traits::ProcessedMap ProcessedMap;
   3.228 +    ///The type of the map that stores the cardinalities of the nodes.
   3.229 +    typedef typename Traits::CardinalityMap CardinalityMap;
   3.230 +    ///The cross reference type used for the current heap.
   3.231 +    typedef typename Traits::HeapCrossRef HeapCrossRef;
   3.232 +    ///The heap type used by the algorithm. It maximize the priorities.
   3.233 +    typedef typename Traits::Heap Heap;
   3.234 +  private:
   3.235 +    /// Pointer to the underlying graph.
   3.236 +    const Graph *_graph;
   3.237 +    /// Pointer to the capacity map
   3.238 +    const CapacityMap *_capacity;
   3.239 +    ///Pointer to the map of cardinality.
   3.240 +    CardinalityMap *_cardinality;
   3.241 +    ///Indicates if \ref _cardinality is locally allocated (\c true) or not.
   3.242 +    bool local_cardinality;
   3.243 +    ///Pointer to the map of processed status of the nodes.
   3.244 +    ProcessedMap *_processed;
   3.245 +    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   3.246 +    bool local_processed;
   3.247 +    ///Pointer to the heap cross references.
   3.248 +    HeapCrossRef *_heap_cross_ref;
   3.249 +    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   3.250 +    bool local_heap_cross_ref;
   3.251 +    ///Pointer to the heap.
   3.252 +    Heap *_heap;
   3.253 +    ///Indicates if \ref _heap is locally allocated (\c true) or not.
   3.254 +    bool local_heap;
   3.255 +
   3.256 +  public :
   3.257 +
   3.258 +    typedef MaxCardinalitySearch Create;
   3.259 + 
   3.260 +    ///\name Named template parameters
   3.261 +
   3.262 +    ///@{
   3.263 +
   3.264 +    template <class T>
   3.265 +    struct DefCardinalityMapTraits : public Traits {
   3.266 +      typedef T CardinalityMap;
   3.267 +      static CardinalityMap *createCardinalityMap(const Graph &) 
   3.268 +      {
   3.269 +	throw UninitializedParameter();
   3.270 +      }
   3.271 +    };
   3.272 +    /// \brief \ref named-templ-param "Named parameter" for setting 
   3.273 +    /// CardinalityMap type
   3.274 +    ///
   3.275 +    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
   3.276 +    /// type
   3.277 +    template <class T>
   3.278 +    struct DefCardinalityMap 
   3.279 +      : public MaxCardinalitySearch<Graph, CapacityMap, 
   3.280 +                                    DefCardinalityMapTraits<T> > { 
   3.281 +      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   3.282 +                                   DefCardinalityMapTraits<T> > Create;
   3.283 +    };
   3.284 +    
   3.285 +    template <class T>
   3.286 +    struct DefProcessedMapTraits : public Traits {
   3.287 +      typedef T ProcessedMap;
   3.288 +      static ProcessedMap *createProcessedMap(const Graph &) {
   3.289 +	throw UninitializedParameter();
   3.290 +      }
   3.291 +    };
   3.292 +    /// \brief \ref named-templ-param "Named parameter" for setting 
   3.293 +    /// ProcessedMap type
   3.294 +    ///
   3.295 +    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
   3.296 +    ///
   3.297 +    template <class T>
   3.298 +    struct DefProcessedMap 
   3.299 +      : public MaxCardinalitySearch<Graph, CapacityMap, 
   3.300 +                                    DefProcessedMapTraits<T> > { 
   3.301 +      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   3.302 +                                   DefProcessedMapTraits<T> > Create;
   3.303 +    };
   3.304 +    
   3.305 +    template <class H, class CR>
   3.306 +    struct DefHeapTraits : public Traits {
   3.307 +      typedef CR HeapCrossRef;
   3.308 +      typedef H Heap;
   3.309 +      static HeapCrossRef *createHeapCrossRef(const Graph &) {
   3.310 +	throw UninitializedParameter();
   3.311 +      }
   3.312 +      static Heap *createHeap(HeapCrossRef &) {
   3.313 +	throw UninitializedParameter();
   3.314 +      }
   3.315 +    };
   3.316 +    /// \brief \ref named-templ-param "Named parameter" for setting heap 
   3.317 +    /// and cross reference type
   3.318 +    ///
   3.319 +    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   3.320 +    /// reference type
   3.321 +    template <class H, class CR = typename Graph::template NodeMap<int> >
   3.322 +    struct DefHeap
   3.323 +      : public MaxCardinalitySearch<Graph, CapacityMap, 
   3.324 +                                    DefHeapTraits<H, CR> > { 
   3.325 +      typedef MaxCardinalitySearch< Graph, CapacityMap, 
   3.326 +                                    DefHeapTraits<H, CR> > Create;
   3.327 +    };
   3.328 +
   3.329 +    template <class H, class CR>
   3.330 +    struct DefStandardHeapTraits : public Traits {
   3.331 +      typedef CR HeapCrossRef;
   3.332 +      typedef H Heap;
   3.333 +      static HeapCrossRef *createHeapCrossRef(const Graph &graph) {
   3.334 +	return new HeapCrossRef(graph);
   3.335 +      }
   3.336 +      static Heap *createHeap(HeapCrossRef &crossref) {
   3.337 +	return new Heap(crossref);
   3.338 +      }
   3.339 +    };
   3.340 +
   3.341 +    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   3.342 +    /// cross reference type with automatic allocation
   3.343 +    ///
   3.344 +    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   3.345 +    /// reference type. It can allocate the heap and the cross reference 
   3.346 +    /// object if the cross reference's constructor waits for the graph as 
   3.347 +    /// parameter and the heap's constructor waits for the cross reference.
   3.348 +    template <class H, class CR = typename Graph::template NodeMap<int> >
   3.349 +    struct DefStandardHeap
   3.350 +      : public MaxCardinalitySearch<Graph, CapacityMap, 
   3.351 +                                    DefStandardHeapTraits<H, CR> > { 
   3.352 +      typedef MaxCardinalitySearch<Graph, CapacityMap, 
   3.353 +                                   DefStandardHeapTraits<H, CR> > 
   3.354 +      Create;
   3.355 +    };
   3.356 +    
   3.357 +    ///@}
   3.358 +
   3.359 +
   3.360 +  protected:
   3.361 +
   3.362 +    MaxCardinalitySearch() {}
   3.363 +
   3.364 +  public:      
   3.365 +    
   3.366 +    /// \brief Constructor.
   3.367 +    ///
   3.368 +    ///\param _graph the graph the algorithm will run on.
   3.369 +    ///\param _capacity the capacity map used by the algorithm.
   3.370 +    MaxCardinalitySearch(const Graph& graph, const CapacityMap& capacity) :
   3.371 +      _graph(&graph), _capacity(&capacity),
   3.372 +      _cardinality(0), local_cardinality(false),
   3.373 +      _processed(0), local_processed(false),
   3.374 +      _heap_cross_ref(0), local_heap_cross_ref(false),
   3.375 +      _heap(0), local_heap(false)
   3.376 +    { }
   3.377 +    
   3.378 +    /// \brief Destructor.
   3.379 +    ~MaxCardinalitySearch() {
   3.380 +      if(local_cardinality) delete _cardinality;
   3.381 +      if(local_processed) delete _processed;
   3.382 +      if(local_heap_cross_ref) delete _heap_cross_ref;
   3.383 +      if(local_heap) delete _heap;
   3.384 +    }
   3.385 +
   3.386 +    /// \brief Sets the capacity map.
   3.387 +    ///
   3.388 +    /// Sets the capacity map.
   3.389 +    /// \return <tt> (*this) </tt>
   3.390 +    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
   3.391 +      _capacity = &m;
   3.392 +      return *this;
   3.393 +    }
   3.394 +
   3.395 +    /// \brief Sets the map storing the cardinalities calculated by the 
   3.396 +    /// algorithm.
   3.397 +    ///
   3.398 +    /// Sets the map storing the cardinalities calculated by the algorithm.
   3.399 +    /// If you don't use this function before calling \ref run(),
   3.400 +    /// it will allocate one. The destuctor deallocates this
   3.401 +    /// automatically allocated map, of course.
   3.402 +    /// \return <tt> (*this) </tt>
   3.403 +    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
   3.404 +      if(local_cardinality) {
   3.405 +	delete _cardinality;
   3.406 +	local_cardinality=false;
   3.407 +      }
   3.408 +      _cardinality = &m;
   3.409 +      return *this;
   3.410 +    }
   3.411 +
   3.412 +    /// \brief Sets the map storing the processed nodes.
   3.413 +    ///
   3.414 +    /// Sets the map storing the processed nodes.
   3.415 +    /// If you don't use this function before calling \ref run(),
   3.416 +    /// it will allocate one. The destuctor deallocates this
   3.417 +    /// automatically allocated map, of course.
   3.418 +    /// \return <tt> (*this) </tt>
   3.419 +    MaxCardinalitySearch &processedMap(ProcessedMap &m) 
   3.420 +    {
   3.421 +      if(local_processed) {
   3.422 +	delete _processed;
   3.423 +	local_processed=false;
   3.424 +      }
   3.425 +      _processed = &m;
   3.426 +      return *this;
   3.427 +    }
   3.428 +
   3.429 +    /// \brief Sets the heap and the cross reference used by algorithm.
   3.430 +    ///
   3.431 +    /// Sets the heap and the cross reference used by algorithm.
   3.432 +    /// If you don't use this function before calling \ref run(),
   3.433 +    /// it will allocate one. The destuctor deallocates this
   3.434 +    /// automatically allocated map, of course.
   3.435 +    /// \return <tt> (*this) </tt>
   3.436 +    MaxCardinalitySearch &heap(Heap& heap, HeapCrossRef &crossRef) {
   3.437 +      if(local_heap_cross_ref) {
   3.438 +	delete _heap_cross_ref;
   3.439 +	local_heap_cross_ref = false;
   3.440 +      }
   3.441 +      _heap_cross_ref = &crossRef;
   3.442 +      if(local_heap) {
   3.443 +	delete _heap;
   3.444 +	local_heap = false;
   3.445 +      }
   3.446 +      _heap = &heap;
   3.447 +      return *this;
   3.448 +    }
   3.449 +
   3.450 +  private:
   3.451 +
   3.452 +    typedef typename Graph::Node Node;
   3.453 +    typedef typename Graph::NodeIt NodeIt;
   3.454 +    typedef typename Graph::Edge Edge;
   3.455 +    typedef typename Graph::InEdgeIt InEdgeIt;
   3.456 +
   3.457 +    void create_maps() {
   3.458 +      if(!_cardinality) {
   3.459 +	local_cardinality = true;
   3.460 +	_cardinality = Traits::createCardinalityMap(*_graph);
   3.461 +      }
   3.462 +      if(!_processed) {
   3.463 +	local_processed = true;
   3.464 +	_processed = Traits::createProcessedMap(*_graph);
   3.465 +      }
   3.466 +      if (!_heap_cross_ref) {
   3.467 +	local_heap_cross_ref = true;
   3.468 +	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
   3.469 +      }
   3.470 +      if (!_heap) {
   3.471 +	local_heap = true;
   3.472 +	_heap = Traits::createHeap(*_heap_cross_ref);
   3.473 +      }
   3.474 +    }
   3.475 +    
   3.476 +    void finalizeNodeData(Node node, Value capacity) {
   3.477 +      _processed->set(node, true);
   3.478 +      _cardinality->set(node, capacity);
   3.479 +    }
   3.480 +
   3.481 +  public:
   3.482 +    /// \name Execution control
   3.483 +    /// The simplest way to execute the algorithm is to use
   3.484 +    /// one of the member functions called \c run(...).
   3.485 +    /// \n
   3.486 +    /// If you need more control on the execution,
   3.487 +    /// first you must call \ref init(), then you can add several source nodes
   3.488 +    /// with \ref addSource().
   3.489 +    /// Finally \ref start() will perform the actual path
   3.490 +    /// computation.
   3.491 +
   3.492 +    ///@{
   3.493 +
   3.494 +    /// \brief Initializes the internal data structures.
   3.495 +    ///
   3.496 +    /// Initializes the internal data structures.
   3.497 +    void init() {
   3.498 +      create_maps();
   3.499 +      _heap->clear();
   3.500 +      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
   3.501 +	_processed->set(it, false);
   3.502 +	_heap_cross_ref->set(it, Heap::PRE_HEAP);
   3.503 +      }
   3.504 +    }
   3.505 +    
   3.506 +    /// \brief Adds a new source node.
   3.507 +    /// 
   3.508 +    /// Adds a new source node to the priority heap.
   3.509 +    ///
   3.510 +    /// It checks if the node has not yet been added to the heap.
   3.511 +    void addSource(Node source, Value capacity = 0) {
   3.512 +      if(_heap->state(source) == Heap::PRE_HEAP) {
   3.513 +	_heap->push(source, capacity);
   3.514 +      } 
   3.515 +    }
   3.516 +    
   3.517 +    /// \brief Processes the next node in the priority heap
   3.518 +    ///
   3.519 +    /// Processes the next node in the priority heap.
   3.520 +    ///
   3.521 +    /// \return The processed node.
   3.522 +    ///
   3.523 +    /// \warning The priority heap must not be empty!
   3.524 +    Node processNextNode() {
   3.525 +      Node node = _heap->top(); 
   3.526 +      finalizeNodeData(node, _heap->prio());
   3.527 +      _heap->pop();
   3.528 +      
   3.529 +      for (InEdgeIt it(*_graph, node); it != INVALID; ++it) {
   3.530 +	Node source = _graph->source(it); 
   3.531 +	switch (_heap->state(source)) {
   3.532 +	case Heap::PRE_HEAP:
   3.533 +	  _heap->push(source, (*_capacity)[it]); 
   3.534 +	  break;
   3.535 +	case Heap::IN_HEAP:
   3.536 +	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); 
   3.537 +	  break;
   3.538 +	case Heap::POST_HEAP:
   3.539 +	  break;
   3.540 +	}
   3.541 +      }
   3.542 +      return node;
   3.543 +    }
   3.544 +
   3.545 +    /// \brief Next node to be processed.
   3.546 +    ///
   3.547 +    /// Next node to be processed.
   3.548 +    ///
   3.549 +    /// \return The next node to be processed or INVALID if the 
   3.550 +    /// priority heap is empty.
   3.551 +    Node nextNode() { 
   3.552 +      return _heap->empty() ? _heap->top() : INVALID;
   3.553 +    }
   3.554 + 
   3.555 +    /// \brief Returns \c false if there are nodes
   3.556 +    /// to be processed in the priority heap
   3.557 +    ///
   3.558 +    /// Returns \c false if there are nodes
   3.559 +    /// to be processed in the priority heap
   3.560 +    bool emptyQueue() { return _heap->empty(); }
   3.561 +    /// \brief Returns the number of the nodes to be processed 
   3.562 +    /// in the priority heap
   3.563 +    ///
   3.564 +    /// Returns the number of the nodes to be processed in the priority heap
   3.565 +    int queueSize() { return _heap->size(); }
   3.566 +    
   3.567 +    /// \brief Executes the algorithm.
   3.568 +    ///
   3.569 +    /// Executes the algorithm.
   3.570 +    ///
   3.571 +    ///\pre init() must be called and at least one node should be added
   3.572 +    /// with addSource() before using this function.
   3.573 +    ///
   3.574 +    /// This method runs the Maximum Cardinality Search algorithm from the 
   3.575 +    /// source node(s).
   3.576 +    void start() {
   3.577 +      while ( !_heap->empty() ) processNextNode();
   3.578 +    }
   3.579 +    
   3.580 +    /// \brief Executes the algorithm until \c dest is reached.
   3.581 +    ///
   3.582 +    /// Executes the algorithm until \c dest is reached.
   3.583 +    ///
   3.584 +    /// \pre init() must be called and at least one node should be added
   3.585 +    /// with addSource() before using this function.
   3.586 +    ///
   3.587 +    /// This method runs the %MaxCardinalitySearch algorithm from the source 
   3.588 +    /// nodes.
   3.589 +    void start(Node dest) {
   3.590 +      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   3.591 +      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
   3.592 +    }
   3.593 +    
   3.594 +    /// \brief Executes the algorithm until a condition is met.
   3.595 +    ///
   3.596 +    /// Executes the algorithm until a condition is met.
   3.597 +    ///
   3.598 +    /// \pre init() must be called and at least one node should be added
   3.599 +    /// with addSource() before using this function.
   3.600 +    ///
   3.601 +    /// \param nm must be a bool (or convertible) node map. The algorithm
   3.602 +    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
   3.603 +    template <typename NodeBoolMap>
   3.604 +    void start(const NodeBoolMap &nm) {
   3.605 +      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   3.606 +      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
   3.607 +    }
   3.608 +    
   3.609 +    /// \brief Runs the maximal cardinality search algorithm from node \c s.
   3.610 +    ///
   3.611 +    /// This method runs the %MaxCardinalitySearch algorithm from a root 
   3.612 +    /// node \c s.
   3.613 +    ///
   3.614 +    ///\note d.run(s) is just a shortcut of the following code.
   3.615 +    ///\code
   3.616 +    ///  d.init();
   3.617 +    ///  d.addSource(s);
   3.618 +    ///  d.start();
   3.619 +    ///\endcode
   3.620 +    void run(Node s) {
   3.621 +      init();
   3.622 +      addSource(s);
   3.623 +      start();
   3.624 +    }
   3.625 +
   3.626 +    /// \brief Runs the maximal cardinality search algorithm for the 
   3.627 +    /// whole graph.
   3.628 +    ///
   3.629 +    /// This method runs the %MaxCardinalitySearch algorithm from all 
   3.630 +    /// unprocessed node of the graph.
   3.631 +    ///
   3.632 +    ///\note d.run(s) is just a shortcut of the following code.
   3.633 +    ///\code
   3.634 +    ///  d.init();
   3.635 +    ///  for (NodeIt it(graph); it != INVALID; ++it) {
   3.636 +    ///    if (!d.reached(it)) {
   3.637 +    ///      d.addSource(s);
   3.638 +    ///      d.start();
   3.639 +    ///    }
   3.640 +    ///  }
   3.641 +    ///\endcode
   3.642 +    void run() {
   3.643 +      init();
   3.644 +      for (NodeIt it(*_graph); it != INVALID; ++it) {
   3.645 +        if (!reached(it)) {
   3.646 +          addSource(it);
   3.647 +          start();
   3.648 +        }
   3.649 +      }
   3.650 +    }
   3.651 +    
   3.652 +    ///@}
   3.653 +
   3.654 +    /// \name Query Functions
   3.655 +    /// The result of the maximum cardinality search algorithm can be 
   3.656 +    /// obtained using these functions.
   3.657 +    /// \n
   3.658 +    /// Before the use of these functions, either run() or start() must be 
   3.659 +    /// called.
   3.660 +    
   3.661 +    ///@{
   3.662 +
   3.663 +    /// \brief The cardinality of a node.
   3.664 +    ///
   3.665 +    /// Returns the cardinality of a node.
   3.666 +    /// \pre \ref run() must be called before using this function.
   3.667 +    /// \warning If node \c v in unreachable from the root the return value
   3.668 +    /// of this funcion is undefined.
   3.669 +    Value cardinality(Node node) const { return (*_cardinality)[node]; }
   3.670 +
   3.671 +    /// \brief Returns a reference to the NodeMap of cardinalities.
   3.672 +    ///
   3.673 +    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
   3.674 +    /// must be called before using this function.
   3.675 +    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
   3.676 + 
   3.677 +    /// \brief Checks if a node is reachable from the root.
   3.678 +    ///
   3.679 +    /// Returns \c true if \c v is reachable from the root.
   3.680 +    /// \warning The source nodes are inditated as unreached.
   3.681 +    /// \pre \ref run() must be called before using this function.
   3.682 +    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   3.683 +
   3.684 +    /// \brief Checks if a node is processed.
   3.685 +    ///
   3.686 +    /// Returns \c true if \c v is processed, i.e. the shortest
   3.687 +    /// path to \c v has already found.
   3.688 +    /// \pre \ref run() must be called before using this function.
   3.689 +    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   3.690 +    
   3.691 +    ///@}
   3.692 +  };
   3.693 +
   3.694 +  /// \brief Default traits class of MinimumCut class.
   3.695 +  ///
   3.696 +  /// Default traits class of MinimumCut class.
   3.697 +  /// \param Graph Graph type.
   3.698 +  /// \param CapacityMap Type of length map.
   3.699 +  template <typename _Graph, typename _CapacityMap>
   3.700 +  struct MinimumCutDefaultTraits {
   3.701 +    /// \brief The type of the capacity of the edges.
   3.702 +    typedef typename _CapacityMap::Value Value;
   3.703 +
   3.704 +    /// The graph type the algorithm runs on. 
   3.705 +    typedef _Graph Graph;
   3.706 +
   3.707 +    /// The WorkGraph type which is an EraseableGraph
   3.708 +    typedef ListUGraph WorkGraph;
   3.709 +
   3.710 +    /// \brief Instantiates a WorkGraph.
   3.711 +    ///
   3.712 +    /// This function instantiates a \ref WorkGraph. 
   3.713 +    static WorkGraph *createWorkGraph() {
   3.714 +      return new WorkGraph();
   3.715 +    }
   3.716 +
   3.717 +    /// \brief The type of the map that stores the edge capacities.
   3.718 +    ///
   3.719 +    /// The type of the map that stores the edge capacities.
   3.720 +    /// It must meet the \ref concept::ReadMap "ReadMap" concept.
   3.721 +    typedef _CapacityMap CapacityMap;
   3.722 +
   3.723 +    /// \brief Instantiates a CapacityMap.
   3.724 +    ///
   3.725 +    /// This function instantiates a \ref CapacityMap.
   3.726 +#ifdef DOXYGEN
   3.727 +    static CapacityMap *createCapacityMap(const Graph& graph) 
   3.728 +#else
   3.729 +    static CapacityMap *createCapacityMap(const Graph&)
   3.730 +#endif
   3.731 +    {
   3.732 +      throw UninitializedParameter();
   3.733 +    }
   3.734 +
   3.735 +    /// \brief The WorkCapacityMap type
   3.736 +    ///
   3.737 +    /// The type of the map that stores the working edge capacities.
   3.738 +    typedef WorkGraph::UEdgeMap<Value> WorkCapacityMap;
   3.739 +
   3.740 +    /// \brief Instantiates a WorkCapacityMap.
   3.741 +    ///
   3.742 +    /// This function instantiates a \ref WorkCapacityMap. 
   3.743 +    static WorkCapacityMap *createWorkCapacityMap(const WorkGraph& graph) {
   3.744 +      return new WorkCapacityMap(graph);
   3.745 +    }
   3.746 +
   3.747 +    /// \brief The cross reference type used by heap.
   3.748 +    ///
   3.749 +    /// The cross reference type used by heap.
   3.750 +    /// Usually it is \c Graph::NodeMap<int>.
   3.751 +    typedef WorkGraph::NodeMap<int> HeapCrossRef;
   3.752 +
   3.753 +    /// \brief Instantiates a HeapCrossRef.
   3.754 +    ///
   3.755 +    /// This function instantiates a \ref HeapCrossRef. 
   3.756 +    /// \param graph is the graph, to which we would like to define the 
   3.757 +    /// HeapCrossRef.
   3.758 +    static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
   3.759 +      return new HeapCrossRef(graph);
   3.760 +    }
   3.761 +    
   3.762 +    /// \brief The heap type used by MinimumCut algorithm.
   3.763 +    ///
   3.764 +    /// The heap type used by MinimumCut algorithm. It should
   3.765 +    /// maximalize the priorities and the heap's key type is
   3.766 +    /// the work graph's node.
   3.767 +    ///
   3.768 +    /// \sa BinHeap
   3.769 +    /// \sa MinimumCut
   3.770 +    typedef typename _minimum_cut_bits
   3.771 +    ::HeapSelector<CapacityMap>
   3.772 +    ::template Selector<typename WorkGraph::Node, Value, HeapCrossRef>
   3.773 +    ::Heap Heap;
   3.774 +    
   3.775 +    /// \brief Instantiates a Heap.
   3.776 +    ///
   3.777 +    /// This function instantiates a \ref Heap. 
   3.778 +    /// \param crossref The cross reference of the heap.
   3.779 +    static Heap *createHeap(HeapCrossRef& crossref) {
   3.780 +      return new Heap(crossref);
   3.781 +    }
   3.782 +
   3.783 +    /// \brief Map from the WorkGraph's node type to the Graph's node type.
   3.784 +    ///
   3.785 +    /// Map from the WorkGraph's node type to the Graph's node type.
   3.786 +    typedef typename WorkGraph
   3.787 +    ::template NodeMap<typename Graph::Node> NodeRefMap;
   3.788 +
   3.789 +    /// \brief Instantiates a NodeRefMap.
   3.790 +    ///
   3.791 +    /// This function instantiates a \ref NodeRefMap. 
   3.792 +    static NodeRefMap *createNodeRefMap(const WorkGraph& graph) {
   3.793 +      return new NodeRefMap(graph);
   3.794 +    }
   3.795 +
   3.796 +    /// \brief Map from the Graph's node type to the Graph's node type.
   3.797 +    ///
   3.798 +    /// Map from the Graph's node type to the Graph's node type.
   3.799 +    typedef typename Graph
   3.800 +    ::template NodeMap<typename Graph::Node> ListRefMap;
   3.801 +
   3.802 +    /// \brief Instantiates a ListRefMap.
   3.803 +    ///
   3.804 +    /// This function instantiates a \ref ListRefMap. 
   3.805 +    static ListRefMap *createListRefMap(const Graph& graph) {
   3.806 +      return new ListRefMap(graph);
   3.807 +    }
   3.808 +    
   3.809 +
   3.810 +  };
   3.811 +
   3.812 +  namespace _minimum_cut_bits {
   3.813 +    template <typename _Key>
   3.814 +    class LastTwoMap {
   3.815 +    public:
   3.816 +      typedef _Key Key;
   3.817 +      typedef bool Value;
   3.818 +
   3.819 +      LastTwoMap(int _num) : num(_num) {}
   3.820 +      void set(const Key& key, bool val) {
   3.821 +        if (!val) return;
   3.822 +        --num;
   3.823 +        if (num > 1) return;
   3.824 +        keys[num] = key;
   3.825 +      }
   3.826 +      
   3.827 +      Key operator[](int index) const { return keys[index]; }
   3.828 +    private:
   3.829 +      Key keys[2];
   3.830 +      int num;
   3.831 +    };
   3.832 +  }
   3.833 +
   3.834 +  /// \ingroup topology
   3.835 +  ///
   3.836 +  /// \brief Calculates the minimum cut in an undirected graph.
   3.837 +  ///
   3.838 +  /// Calculates the minimum cut in an undirected graph. 
   3.839 +  /// The algorithm separates the graph's nodes to two partitions with the 
   3.840 +  /// minimum sum of edge capacities between the two partitions. The
   3.841 +  /// algorithm can be used to test the network reliability specifically
   3.842 +  /// to test how many links have to be destroyed in the network to split it 
   3.843 +  /// at least two distinict subnetwork.
   3.844 +  ///
   3.845 +  /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci 
   3.846 +  /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity 
   3.847 +  /// map is used then it uses LinearHeap which results O(n*e) time complexity.
   3.848 +#ifdef DOXYGEN
   3.849 +  template <typename _Graph, typename _CapacityMap, typename _Traits>
   3.850 +#else
   3.851 +  template <typename _Graph = ListUGraph, 
   3.852 +	    typename _CapacityMap = typename _Graph::template UEdgeMap<int>, 
   3.853 +	    typename _Traits = MinimumCutDefaultTraits<_Graph, _CapacityMap> >
   3.854 +#endif
   3.855 +  class MinimumCut {
   3.856 +  public:
   3.857 +    /// \brief \ref Exception for uninitialized parameters.
   3.858 +    ///
   3.859 +    /// This error represents problems in the initialization
   3.860 +    /// of the parameters of the algorithms.
   3.861 +    class UninitializedParameter : public lemon::UninitializedParameter {
   3.862 +    public:
   3.863 +      virtual const char* exceptionName() const {
   3.864 +	return "lemon::MinimumCut::UninitializedParameter";
   3.865 +      }
   3.866 +    };
   3.867 +
   3.868 +
   3.869 +  private:
   3.870 +
   3.871 +    typedef _Traits Traits;
   3.872 +    /// The type of the underlying graph.
   3.873 +    typedef typename Traits::Graph Graph;
   3.874 +    
   3.875 +    /// The type of the capacity of the edges.
   3.876 +    typedef typename Traits::CapacityMap::Value Value;
   3.877 +    /// The type of the map that stores the edge capacities.
   3.878 +    typedef typename Traits::CapacityMap CapacityMap;
   3.879 +    /// The type of the work graph
   3.880 +    typedef typename Traits::WorkGraph WorkGraph;
   3.881 +    /// The type of the work capacity map
   3.882 +    typedef typename Traits::WorkCapacityMap WorkCapacityMap;
   3.883 +    /// The cross reference type used for the current heap.
   3.884 +    typedef typename Traits::HeapCrossRef HeapCrossRef;
   3.885 +    /// The heap type used by the max cardinality algorithm.
   3.886 +    typedef typename Traits::Heap Heap;
   3.887 +    /// The node refrefernces between the original and work graph type.
   3.888 +    typedef typename Traits::NodeRefMap NodeRefMap;
   3.889 +    /// The list node refrefernces in the original graph type.
   3.890 +    typedef typename Traits::ListRefMap ListRefMap;
   3.891 +
   3.892 +  public:
   3.893 +
   3.894 +    ///\name Named template parameters
   3.895 +
   3.896 +    ///@{
   3.897 +
   3.898 +    struct DefNeutralCapacityTraits : public Traits {
   3.899 +      typedef ConstMap<typename Graph::UEdge, Const<int, 1> > CapacityMap;
   3.900 +      static CapacityMap *createCapacityMap(const Graph&) {
   3.901 +	return new CapacityMap();
   3.902 +      }
   3.903 +    };
   3.904 +    /// \brief \ref named-templ-param "Named parameter" for setting  
   3.905 +    /// the capacity type to constMap<UEdge, int, 1>()
   3.906 +    ///
   3.907 +    /// \ref named-templ-param "Named parameter" for setting 
   3.908 +    /// the capacity type to constMap<UEdge, int, 1>()
   3.909 +    struct DefNeutralCapacity
   3.910 +      : public MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> { 
   3.911 +      typedef MinimumCut<Graph, CapacityMap, DefNeutralCapacityTraits> Create;
   3.912 +    };
   3.913 +
   3.914 +
   3.915 +    template <class H, class CR>
   3.916 +    struct DefHeapTraits : public Traits {
   3.917 +      typedef CR HeapCrossRef;
   3.918 +      typedef H Heap;
   3.919 +      static HeapCrossRef *createHeapCrossRef(const WorkGraph &) {
   3.920 +	throw UninitializedParameter();
   3.921 +      }
   3.922 +      static Heap *createHeap(HeapCrossRef &) {
   3.923 +	throw UninitializedParameter();
   3.924 +      }
   3.925 +    };
   3.926 +    /// \brief \ref named-templ-param "Named parameter" for setting heap 
   3.927 +    /// and cross reference type
   3.928 +    ///
   3.929 +    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   3.930 +    /// reference type
   3.931 +    template <class H, class CR = typename Graph::template NodeMap<int> >
   3.932 +    struct DefHeap
   3.933 +      : public MinimumCut<Graph, CapacityMap, DefHeapTraits<H, CR> > { 
   3.934 +      typedef MinimumCut< Graph, CapacityMap, DefHeapTraits<H, CR> > Create;
   3.935 +    };
   3.936 +
   3.937 +    template <class H, class CR>
   3.938 +    struct DefStandardHeapTraits : public Traits {
   3.939 +      typedef CR HeapCrossRef;
   3.940 +      typedef H Heap;
   3.941 +      static HeapCrossRef *createHeapCrossRef(const WorkGraph &graph) {
   3.942 +	return new HeapCrossRef(graph);
   3.943 +      }
   3.944 +      static Heap *createHeap(HeapCrossRef &crossref) {
   3.945 +	return new Heap(crossref);
   3.946 +      }
   3.947 +    };
   3.948 +
   3.949 +    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
   3.950 +    /// cross reference type with automatic allocation
   3.951 +    ///
   3.952 +    /// \ref named-templ-param "Named parameter" for setting heap and cross 
   3.953 +    /// reference type. It can allocate the heap and the cross reference 
   3.954 +    /// object if the cross reference's constructor waits for the graph as 
   3.955 +    /// parameter and the heap's constructor waits for the cross reference.
   3.956 +    template <class H, class CR = typename Graph::template NodeMap<int> >
   3.957 +    struct DefStandardHeap
   3.958 +      : public MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > { 
   3.959 +      typedef MinimumCut<Graph, CapacityMap, DefStandardHeapTraits<H, CR> > 
   3.960 +      Create;
   3.961 +    };
   3.962 +
   3.963 +    ///@}
   3.964 +
   3.965 +
   3.966 +  private:
   3.967 +    /// Pointer to the underlying graph.
   3.968 +    const Graph *_graph;
   3.969 +    /// Pointer to the capacity map
   3.970 +    const CapacityMap *_capacity;
   3.971 +    /// \brief Indicates if \ref _capacity is locally allocated 
   3.972 +    /// (\c true) or not.
   3.973 +    bool local_capacity;
   3.974 +
   3.975 +    /// Pointer to the work graph.
   3.976 +    WorkGraph *_work_graph;
   3.977 +    /// \brief Indicates if \ref _work_graph is locally allocated 
   3.978 +    /// (\c true) or not.
   3.979 +    bool local_work_graph;
   3.980 +    /// Pointer to the work capacity map
   3.981 +    WorkCapacityMap *_work_capacity;
   3.982 +    /// \brief Indicates if \ref _work_capacity is locally allocated 
   3.983 +    /// (\c true) or not.
   3.984 +    bool local_work_capacity;
   3.985 +    /// Pointer to the heap cross references.
   3.986 +    HeapCrossRef *_heap_cross_ref;
   3.987 +    /// \brief Indicates if \ref _heap_cross_ref is locally allocated 
   3.988 +    /// (\c true) or not.
   3.989 +    bool local_heap_cross_ref;
   3.990 +    /// Pointer to the heap.
   3.991 +    Heap *_heap;
   3.992 +    /// Indicates if \ref _heap is locally allocated (\c true) or not.
   3.993 +    bool local_heap;
   3.994 +
   3.995 +    /// The minimum cut value.
   3.996 +    Value _minimum_cut;
   3.997 +    /// The number of the nodes of the work graph.
   3.998 +    int _node_num;
   3.999 +    /// The first and last node of the min cut in the next list;
  3.1000 +    typename Graph::Node _first_node, _last_node;
  3.1001 +
  3.1002 +    /// \brief The first and last element in the list associated
  3.1003 +    /// to the work graph node.
  3.1004 +    NodeRefMap *_first, *_last;
  3.1005 +    /// \brief The next node in the node lists.
  3.1006 +    ListRefMap *_next;
  3.1007 +    
  3.1008 +    void create_structures() {
  3.1009 +      if (!_capacity) {
  3.1010 +        local_capacity = true;
  3.1011 +        _capacity = Traits::createCapacityMap(*_graph);
  3.1012 +      }
  3.1013 +      if(!_work_graph) {
  3.1014 +	local_work_graph = true;
  3.1015 +	_work_graph = Traits::createWorkGraph();
  3.1016 +      }
  3.1017 +      if(!_work_capacity) {
  3.1018 +	local_work_capacity = true;
  3.1019 +	_work_capacity = Traits::createWorkCapacityMap(*_work_graph);
  3.1020 +      }
  3.1021 +
  3.1022 +      _first = Traits::createNodeRefMap(*_work_graph);
  3.1023 +      _last = Traits::createNodeRefMap(*_work_graph);
  3.1024 +
  3.1025 +      _next = Traits::createListRefMap(*_graph);
  3.1026 +
  3.1027 +      typename Graph::template NodeMap<typename WorkGraph::Node> ref(*_graph);
  3.1028 +
  3.1029 +      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  3.1030 +        _next->set(it, INVALID);
  3.1031 +        typename WorkGraph::Node node = _work_graph->addNode();
  3.1032 +        _first->set(node, it);
  3.1033 +        _last->set(node, it);
  3.1034 +        ref.set(it, node);
  3.1035 +      }
  3.1036 +
  3.1037 +      for (typename Graph::UEdgeIt it(*_graph); it != INVALID; ++it) {
  3.1038 +        if (_graph->source(it) == _graph->target(it)) continue;
  3.1039 +        typename WorkGraph::UEdge uedge = 
  3.1040 +          _work_graph->addEdge(ref[_graph->source(it)], 
  3.1041 +                               ref[_graph->target(it)]);
  3.1042 +        _work_capacity->set(uedge, (*_capacity)[it]);
  3.1043 +        
  3.1044 +      }
  3.1045 +
  3.1046 +      if (!_heap_cross_ref) {
  3.1047 +	local_heap_cross_ref = true;
  3.1048 +	_heap_cross_ref = Traits::createHeapCrossRef(*_work_graph);
  3.1049 +      }
  3.1050 +      if (!_heap) {
  3.1051 +	local_heap = true;
  3.1052 +	_heap = Traits::createHeap(*_heap_cross_ref);
  3.1053 +      }
  3.1054 +    }
  3.1055 +
  3.1056 +  public :
  3.1057 +
  3.1058 +    typedef MinimumCut Create;
  3.1059 +
  3.1060 +
  3.1061 +    /// \brief Constructor.
  3.1062 +    ///
  3.1063 +    ///\param graph the graph the algorithm will run on.
  3.1064 +    ///\param capacity the capacity map used by the algorithm.
  3.1065 +    MinimumCut(const Graph& graph, const CapacityMap& capacity) 
  3.1066 +      : _graph(&graph), 
  3.1067 +        _capacity(&capacity), local_capacity(false),
  3.1068 +        _work_graph(0), local_work_graph(false),
  3.1069 +        _work_capacity(0), local_work_capacity(false),
  3.1070 +        _heap_cross_ref(0), local_heap_cross_ref(false),
  3.1071 +        _heap(0), local_heap(false),
  3.1072 +        _first(0), _last(0), _next(0) {}
  3.1073 +
  3.1074 +    /// \brief Constructor.
  3.1075 +    ///
  3.1076 +    /// This constructor can be used only when the Traits class
  3.1077 +    /// defines how can we instantiate a local capacity map.
  3.1078 +    /// If the DefNeutralCapacity used the algorithm automatically
  3.1079 +    /// construct the capacity map.
  3.1080 +    ///
  3.1081 +    ///\param graph the graph the algorithm will run on.
  3.1082 +    MinimumCut(const Graph& graph) 
  3.1083 +      : _graph(&graph), 
  3.1084 +        _capacity(0), local_capacity(false),
  3.1085 +        _work_graph(0), local_work_graph(false),
  3.1086 +        _work_capacity(0), local_work_capacity(false),
  3.1087 +        _heap_cross_ref(0), local_heap_cross_ref(false),
  3.1088 +        _heap(0), local_heap(false),
  3.1089 +        _first(0), _last(0), _next(0) {}
  3.1090 +
  3.1091 +    /// \brief Destructor.
  3.1092 +    ///
  3.1093 +    /// Destructor.
  3.1094 +    ~MinimumCut() {
  3.1095 +      if (local_heap) delete _heap;
  3.1096 +      if (local_heap_cross_ref) delete _heap_cross_ref;
  3.1097 +      if (_first) delete _first;
  3.1098 +      if (_last) delete _last;
  3.1099 +      if (_next) delete _next;
  3.1100 +      if (local_work_capacity) delete _work_capacity;
  3.1101 +      if (local_work_graph) delete _work_graph;
  3.1102 +      if (local_capacity) delete _capacity;
  3.1103 +    }
  3.1104 +
  3.1105 +    /// \brief Sets the heap and the cross reference used by algorithm.
  3.1106 +    ///
  3.1107 +    /// Sets the heap and the cross reference used by algorithm.
  3.1108 +    /// If you don't use this function before calling \ref run(),
  3.1109 +    /// it will allocate one. The destuctor deallocates this
  3.1110 +    /// automatically allocated heap and cross reference, of course.
  3.1111 +    /// \return <tt> (*this) </tt>
  3.1112 +    MinimumCut &heap(Heap& heap, HeapCrossRef &crossRef)
  3.1113 +    {
  3.1114 +      if (local_heap_cross_ref) {
  3.1115 +	delete _heap_cross_ref;
  3.1116 +	local_heap_cross_ref=false;
  3.1117 +      }
  3.1118 +      _heap_cross_ref = &crossRef;
  3.1119 +      if (local_heap) {
  3.1120 +	delete _heap;
  3.1121 +	local_heap=false;
  3.1122 +      }
  3.1123 +      _heap = &heap;
  3.1124 +      return *this;
  3.1125 +    }
  3.1126 +
  3.1127 +    /// \brief Sets the work graph.
  3.1128 +    ///
  3.1129 +    /// Sets the work graph used by algorithm.
  3.1130 +    /// If you don't use this function before calling \ref run(),
  3.1131 +    /// it will allocate one. The destuctor deallocates this
  3.1132 +    /// automatically allocated graph, of course.
  3.1133 +    /// \return <tt> (*this) </tt>
  3.1134 +    MinimumCut &workGraph(WorkGraph& work_graph)
  3.1135 +    {
  3.1136 +      if(local_work_graph) {
  3.1137 +	delete _work_graph;
  3.1138 +	local_work_graph=false;
  3.1139 +      }
  3.1140 +      _work_graph = &work_graph;
  3.1141 +      return *this;
  3.1142 +    }
  3.1143 +
  3.1144 +    /// \brief Sets the work capacity map.
  3.1145 +    ///
  3.1146 +    /// Sets the work capacity map used by algorithm.
  3.1147 +    /// If you don't use this function before calling \ref run(),
  3.1148 +    /// it will allocate one. The destuctor deallocates this
  3.1149 +    /// automatically allocated graph, of course.
  3.1150 +    /// \return <tt> (*this) </tt>
  3.1151 +    MinimumCut &workCapacityMap(WorkCapacityMap& work_capacity_map)
  3.1152 +    {
  3.1153 +      if(local_work_capacity) {
  3.1154 +	delete _work_capacity;
  3.1155 +	local_work_capacity=false;
  3.1156 +      }
  3.1157 +      _work_capacity = &work_capacity_map;
  3.1158 +      return *this;
  3.1159 +    }
  3.1160 +
  3.1161 +    /// \name Execution control
  3.1162 +    /// The simplest way to execute the algorithm is to use
  3.1163 +    /// one of the member functions called \c run().
  3.1164 +    /// \n
  3.1165 +    /// If you need more control on the execution,
  3.1166 +    /// first you must call \ref init() and then call the start()
  3.1167 +    /// or proper times the processNextPhase() member functions.
  3.1168 +
  3.1169 +    ///@{
  3.1170 +
  3.1171 +    /// \brief Initializes the internal data structures.
  3.1172 +    ///
  3.1173 +    /// Initializes the internal data structures.
  3.1174 +    void init() {
  3.1175 +      create_structures();
  3.1176 +      _first_node = _last_node = INVALID;
  3.1177 +      _node_num = countNodes(*_graph);
  3.1178 +    }
  3.1179 +
  3.1180 +    /// \brief Processes the next phase
  3.1181 +    ///
  3.1182 +    /// Processes the next phase in the algorithm. The function
  3.1183 +    /// should be called countNodes(graph) - 1 times to get
  3.1184 +    /// surely the minimum cut in the graph. The  
  3.1185 +    ///
  3.1186 +    ///\return %True when the algorithm finished.
  3.1187 +    bool processNextPhase() {
  3.1188 +      if (_node_num <= 1) return true;
  3.1189 +      using namespace _minimum_cut_bits;
  3.1190 +
  3.1191 +      typedef typename WorkGraph::Node Node;
  3.1192 +      typedef typename WorkGraph::NodeIt NodeIt;
  3.1193 +      typedef typename WorkGraph::UEdge UEdge;
  3.1194 +      typedef typename WorkGraph::IncEdgeIt IncEdgeIt;
  3.1195 +      
  3.1196 +      typedef typename MaxCardinalitySearch<WorkGraph, WorkCapacityMap>::
  3.1197 +      template DefHeap<Heap, HeapCrossRef>::
  3.1198 +      template DefCardinalityMap<NullMap<Node, Value> >::
  3.1199 +      template DefProcessedMap<LastTwoMap<Node> >::
  3.1200 +      Create MaxCardinalitySearch;
  3.1201 +      
  3.1202 +      MaxCardinalitySearch mcs(*_work_graph, *_work_capacity);
  3.1203 +      for (NodeIt it(*_work_graph); it != INVALID; ++it) {
  3.1204 +        _heap_cross_ref->set(it, Heap::PRE_HEAP);
  3.1205 +      }
  3.1206 +      mcs.heap(*_heap, *_heap_cross_ref);
  3.1207 +
  3.1208 +      LastTwoMap<Node> last_two_nodes(_node_num);
  3.1209 +      mcs.processedMap(last_two_nodes);
  3.1210 +
  3.1211 +      NullMap<Node, Value> cardinality;
  3.1212 +      mcs.cardinalityMap(cardinality);
  3.1213 +
  3.1214 +      mcs.run();
  3.1215 +
  3.1216 +      Node new_node = _work_graph->addNode();
  3.1217 +
  3.1218 +      typename WorkGraph::template NodeMap<UEdge> edges(*_work_graph, INVALID);
  3.1219 +      
  3.1220 +      Node first_node = last_two_nodes[0];
  3.1221 +      Node second_node = last_two_nodes[1];
  3.1222 +      
  3.1223 +      _next->set((*_last)[first_node], (*_first)[second_node]);
  3.1224 +      _first->set(new_node, (*_first)[first_node]);
  3.1225 +      _last->set(new_node, (*_last)[second_node]);
  3.1226 +
  3.1227 +      Value current_cut = 0;      
  3.1228 +      for (IncEdgeIt it(*_work_graph, first_node); it != INVALID; ++it) {
  3.1229 +        Node node = _work_graph->runningNode(it);
  3.1230 +        current_cut += (*_work_capacity)[it];
  3.1231 +        if (node == second_node) continue;
  3.1232 +        if (edges[node] == INVALID) {
  3.1233 +          edges[node] = _work_graph->addEdge(new_node, node);
  3.1234 +          (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
  3.1235 +        } else {
  3.1236 +          (*_work_capacity)[edges[node]] += (*_work_capacity)[it];          
  3.1237 +        }
  3.1238 +      }
  3.1239 +
  3.1240 +      if (_first_node == INVALID || current_cut < _minimum_cut) {
  3.1241 +        _first_node = (*_first)[first_node];
  3.1242 +        _last_node = (*_last)[first_node];
  3.1243 +        _minimum_cut = current_cut;
  3.1244 +      }
  3.1245 +
  3.1246 +      _work_graph->erase(first_node);
  3.1247 +
  3.1248 +      for (IncEdgeIt it(*_work_graph, second_node); it != INVALID; ++it) {
  3.1249 +        Node node = _work_graph->runningNode(it);
  3.1250 +        if (edges[node] == INVALID) {
  3.1251 +          edges[node] = _work_graph->addEdge(new_node, node);
  3.1252 +          (*_work_capacity)[edges[node]] = (*_work_capacity)[it];
  3.1253 +        } else {
  3.1254 +          (*_work_capacity)[edges[node]] += (*_work_capacity)[it];          
  3.1255 +        }
  3.1256 +      }
  3.1257 +      _work_graph->erase(second_node);
  3.1258 +
  3.1259 +      --_node_num;
  3.1260 +      return _node_num == 1;
  3.1261 +    }
  3.1262 +
  3.1263 +    /// \brief Executes the algorithm.
  3.1264 +    ///
  3.1265 +    /// Executes the algorithm.
  3.1266 +    ///
  3.1267 +    /// \pre init() must be called
  3.1268 +    void start() {
  3.1269 +      while (!processNextPhase());
  3.1270 +    }
  3.1271 +
  3.1272 +
  3.1273 +    /// \brief Runs %MinimumCut algorithm.
  3.1274 +    ///
  3.1275 +    /// This method runs the %Minimum cut algorithm
  3.1276 +    ///
  3.1277 +    /// \note mc.run(s) is just a shortcut of the following code.
  3.1278 +    ///\code
  3.1279 +    ///  mc.init();
  3.1280 +    ///  mc.start();
  3.1281 +    ///\endcode
  3.1282 +    void run() {
  3.1283 +      init();
  3.1284 +      start();
  3.1285 +    }
  3.1286 +
  3.1287 +    ///@}
  3.1288 +
  3.1289 +    /// \name Query Functions
  3.1290 +    /// The result of the %MinimumCut algorithm can be obtained using these
  3.1291 +    /// functions.\n
  3.1292 +    /// Before the use of these functions,
  3.1293 +    /// either run() or start() must be called.
  3.1294 +    
  3.1295 +    ///@{
  3.1296 +
  3.1297 +    /// \brief Returns the minimum cut value.
  3.1298 +    ///
  3.1299 +    /// Returns the minimum cut value if the algorithm finished.
  3.1300 +    /// After the first processNextPhase() it is a value of a
  3.1301 +    /// valid cut in the graph.
  3.1302 +    Value minCut() const {
  3.1303 +      return _minimum_cut;
  3.1304 +    }
  3.1305 +
  3.1306 +    /// \brief Returns a minimum cut in a NodeMap.
  3.1307 +    ///
  3.1308 +    /// It sets the nodes of one of the two partitions to true in
  3.1309 +    /// the given BoolNodeMap. The map contains a valid cut if the
  3.1310 +    /// map have been setted false previously. 
  3.1311 +    template <typename NodeMap>
  3.1312 +    Value quickMinCut(NodeMap& nodeMap) const { 
  3.1313 +      for (typename Graph::Node it = _first_node; 
  3.1314 +           it != _last_node; it = (*_next)[it]) {
  3.1315 +             nodeMap.set(it, true);
  3.1316 +           }
  3.1317 +      nodeMap.set(_last_node, true);
  3.1318 +      return minCut();
  3.1319 +    }
  3.1320 +
  3.1321 +    /// \brief Returns a minimum cut in a NodeMap.
  3.1322 +    ///
  3.1323 +    /// It sets the nodes of one of the two partitions to true and
  3.1324 +    /// the other partition to false. The function first set all of the
  3.1325 +    /// nodes to false and after it call the quickMinCut() member.
  3.1326 +    template <typename NodeMap>
  3.1327 +    Value minCut(NodeMap& nodeMap) const { 
  3.1328 +      for (typename Graph::NodeIt it(*_graph); it != INVALID; ++it) {
  3.1329 +        nodeMap.set(it, false);      
  3.1330 +      }
  3.1331 +      quickMinCut(nodeMap);
  3.1332 +      return minCut();
  3.1333 +    }
  3.1334 +
  3.1335 +    /// \brief Returns a minimum cut in an EdgeMap.
  3.1336 +    ///
  3.1337 +    /// If an undirected edge is cut edge then it will be
  3.1338 +    /// setted to true and the others will be setted to false in the given map.
  3.1339 +    template <typename EdgeMap>
  3.1340 +    Value cutEdges(EdgeMap& edgeMap) const {
  3.1341 +      typename Graph::template NodeMap<bool> cut(*_graph, false);
  3.1342 +      quickMinCut(cut);
  3.1343 +      for (typename Graph::EdgeIt it(*_graph); it != INVALID; ++it) {
  3.1344 +        edgeMap.set(it, cut[_graph->source(it)] ^ cut[_graph->target(it)]);
  3.1345 +      }
  3.1346 +      return minCut();
  3.1347 +    }
  3.1348 +
  3.1349 +    ///@}
  3.1350 +
  3.1351 +  };
  3.1352 +}
  3.1353 +
  3.1354 +#endif