lemon/max_cardinality_search.h
changeset 1184 3c00344f49c9
parent 1092 dceba191c00d
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/max_cardinality_search.h	Wed Oct 17 19:14:07 2018 +0200
     1.3 @@ -0,0 +1,794 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2013
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_MAX_CARDINALITY_SEARCH_H
    1.23 +#define LEMON_MAX_CARDINALITY_SEARCH_H
    1.24 +
    1.25 +
    1.26 +/// \ingroup search
    1.27 +/// \file
    1.28 +/// \brief Maximum cardinality search in undirected digraphs.
    1.29 +
    1.30 +#include <lemon/bin_heap.h>
    1.31 +#include <lemon/bucket_heap.h>
    1.32 +
    1.33 +#include <lemon/error.h>
    1.34 +#include <lemon/maps.h>
    1.35 +
    1.36 +#include <functional>
    1.37 +
    1.38 +namespace lemon {
    1.39 +
    1.40 +  /// \brief Default traits class of MaxCardinalitySearch class.
    1.41 +  ///
    1.42 +  /// Default traits class of MaxCardinalitySearch class.
    1.43 +  /// \param Digraph Digraph type.
    1.44 +  /// \param CapacityMap Type of capacity map.
    1.45 +  template <typename GR, typename CAP>
    1.46 +  struct MaxCardinalitySearchDefaultTraits {
    1.47 +    /// The digraph type the algorithm runs on.
    1.48 +    typedef GR Digraph;
    1.49 +
    1.50 +    template <typename CM>
    1.51 +    struct CapMapSelector {
    1.52 +
    1.53 +      typedef CM CapacityMap;
    1.54 +
    1.55 +      static CapacityMap *createCapacityMap(const Digraph& g) {
    1.56 +        return new CapacityMap(g);
    1.57 +      }
    1.58 +    };
    1.59 +
    1.60 +    template <typename CM>
    1.61 +    struct CapMapSelector<ConstMap<CM, Const<int, 1> > > {
    1.62 +
    1.63 +      typedef ConstMap<CM, Const<int, 1> > CapacityMap;
    1.64 +
    1.65 +      static CapacityMap *createCapacityMap(const Digraph&) {
    1.66 +        return new CapacityMap;
    1.67 +      }
    1.68 +    };
    1.69 +
    1.70 +    /// \brief The type of the map that stores the arc capacities.
    1.71 +    ///
    1.72 +    /// The type of the map that stores the arc capacities.
    1.73 +    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    1.74 +    typedef typename CapMapSelector<CAP>::CapacityMap CapacityMap;
    1.75 +
    1.76 +    /// \brief The type of the capacity of the arcs.
    1.77 +    typedef typename CapacityMap::Value Value;
    1.78 +
    1.79 +    /// \brief Instantiates a CapacityMap.
    1.80 +    ///
    1.81 +    /// This function instantiates a \ref CapacityMap.
    1.82 +    /// \param digraph is the digraph, to which we would like to define
    1.83 +    /// the CapacityMap.
    1.84 +    static CapacityMap *createCapacityMap(const Digraph& digraph) {
    1.85 +      return CapMapSelector<CapacityMap>::createCapacityMap(digraph);
    1.86 +    }
    1.87 +
    1.88 +    /// \brief The cross reference type used by heap.
    1.89 +    ///
    1.90 +    /// The cross reference type used by heap.
    1.91 +    /// Usually it is \c Digraph::NodeMap<int>.
    1.92 +    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    1.93 +
    1.94 +    /// \brief Instantiates a HeapCrossRef.
    1.95 +    ///
    1.96 +    /// This function instantiates a \ref HeapCrossRef.
    1.97 +    /// \param digraph is the digraph, to which we would like to define the
    1.98 +    /// HeapCrossRef.
    1.99 +    static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
   1.100 +      return new HeapCrossRef(digraph);
   1.101 +    }
   1.102 +
   1.103 +    template <typename CapacityMap>
   1.104 +    struct HeapSelector {
   1.105 +      template <typename Value, typename Ref>
   1.106 +      struct Selector {
   1.107 +        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
   1.108 +      };
   1.109 +    };
   1.110 +
   1.111 +    template <typename CapacityKey>
   1.112 +    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
   1.113 +      template <typename Value, typename Ref>
   1.114 +      struct Selector {
   1.115 +        typedef BucketHeap<Ref, false > Heap;
   1.116 +      };
   1.117 +    };
   1.118 +
   1.119 +    /// \brief The heap type used by MaxCardinalitySearch algorithm.
   1.120 +    ///
   1.121 +    /// The heap type used by MaxCardinalitySearch algorithm. It should
   1.122 +    /// maximalize the priorities. The default heap type is
   1.123 +    /// the \ref BinHeap, but it is specialized when the
   1.124 +    /// CapacityMap is ConstMap<Digraph::Node, Const<int, 1> >
   1.125 +    /// to BucketHeap.
   1.126 +    ///
   1.127 +    /// \sa MaxCardinalitySearch
   1.128 +    typedef typename HeapSelector<CapacityMap>
   1.129 +    ::template Selector<Value, HeapCrossRef>
   1.130 +    ::Heap Heap;
   1.131 +
   1.132 +    /// \brief Instantiates a Heap.
   1.133 +    ///
   1.134 +    /// This function instantiates a \ref Heap.
   1.135 +    /// \param crossref The cross reference of the heap.
   1.136 +    static Heap *createHeap(HeapCrossRef& crossref) {
   1.137 +      return new Heap(crossref);
   1.138 +    }
   1.139 +
   1.140 +    /// \brief The type of the map that stores whether a node is processed.
   1.141 +    ///
   1.142 +    /// The type of the map that stores whether a node is processed.
   1.143 +    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.144 +    /// By default it is a NullMap.
   1.145 +    typedef NullMap<typename Digraph::Node, bool> ProcessedMap;
   1.146 +
   1.147 +    /// \brief Instantiates a ProcessedMap.
   1.148 +    ///
   1.149 +    /// This function instantiates a \ref ProcessedMap.
   1.150 +    /// \param digraph is the digraph, to which
   1.151 +    /// we would like to define the \ref ProcessedMap
   1.152 +#ifdef DOXYGEN
   1.153 +    static ProcessedMap *createProcessedMap(const Digraph &digraph)
   1.154 +#else
   1.155 +    static ProcessedMap *createProcessedMap(const Digraph &)
   1.156 +#endif
   1.157 +    {
   1.158 +      return new ProcessedMap();
   1.159 +    }
   1.160 +
   1.161 +    /// \brief The type of the map that stores the cardinalities of the nodes.
   1.162 +    ///
   1.163 +    /// The type of the map that stores the cardinalities of the nodes.
   1.164 +    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.165 +    typedef typename Digraph::template NodeMap<Value> CardinalityMap;
   1.166 +
   1.167 +    /// \brief Instantiates a CardinalityMap.
   1.168 +    ///
   1.169 +    /// This function instantiates a \ref CardinalityMap.
   1.170 +    /// \param digraph is the digraph, to which we would like to
   1.171 +    /// define the \ref CardinalityMap
   1.172 +    static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
   1.173 +      return new CardinalityMap(digraph);
   1.174 +    }
   1.175 +
   1.176 +
   1.177 +  };
   1.178 +
   1.179 +  /// \ingroup search
   1.180 +  ///
   1.181 +  /// \brief Maximum Cardinality Search algorithm class.
   1.182 +  ///
   1.183 +  /// This class provides an efficient implementation of Maximum Cardinality
   1.184 +  /// Search algorithm. The maximum cardinality search first chooses any
   1.185 +  /// node of the digraph. Then every time it chooses one unprocessed node
   1.186 +  /// with maximum cardinality, i.e the sum of capacities on out arcs
   1.187 +  /// to the nodes
   1.188 +  /// which were previusly processed.
   1.189 +  /// If there is a cut in the digraph the algorithm should choose
   1.190 +  /// again any unprocessed node of the digraph.
   1.191 +
   1.192 +  /// The arc capacities are passed to the algorithm using a
   1.193 +  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
   1.194 +  /// kind of capacity.
   1.195 +  ///
   1.196 +  /// The type of the capacity is determined by the \ref
   1.197 +  /// concepts::ReadMap::Value "Value" of the capacity map.
   1.198 +  ///
   1.199 +  /// It is also possible to change the underlying priority heap.
   1.200 +  ///
   1.201 +  ///
   1.202 +  /// \param GR The digraph type the algorithm runs on. The value of
   1.203 +  /// Digraph is not used directly by the search algorithm, it
   1.204 +  /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
   1.205 +  /// \param CAP This read-only ArcMap determines the capacities of
   1.206 +  /// the arcs. It is read once for each arc, so the map may involve in
   1.207 +  /// relatively time consuming process to compute the arc capacity if
   1.208 +  /// it is necessary. The default map type is \ref
   1.209 +  /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
   1.210 +  /// of CapacityMap is not used directly by search algorithm, it is only
   1.211 +  /// passed to \ref MaxCardinalitySearchDefaultTraits.
   1.212 +  /// \param TR Traits class to set various data types used by the
   1.213 +  /// algorithm.  The default traits class is
   1.214 +  /// \ref MaxCardinalitySearchDefaultTraits
   1.215 +  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".
   1.216 +  /// See \ref MaxCardinalitySearchDefaultTraits
   1.217 +  /// for the documentation of a MaxCardinalitySearch traits class.
   1.218 +
   1.219 +#ifdef DOXYGEN
   1.220 +  template <typename GR, typename CAP, typename TR>
   1.221 +#else
   1.222 +  template <typename GR, typename CAP =
   1.223 +            ConstMap<typename GR::Arc, Const<int,1> >,
   1.224 +            typename TR =
   1.225 +            MaxCardinalitySearchDefaultTraits<GR, CAP> >
   1.226 +#endif
   1.227 +  class MaxCardinalitySearch {
   1.228 +  public:
   1.229 +
   1.230 +    typedef TR Traits;
   1.231 +    ///The type of the underlying digraph.
   1.232 +    typedef typename Traits::Digraph Digraph;
   1.233 +
   1.234 +    ///The type of the capacity of the arcs.
   1.235 +    typedef typename Traits::CapacityMap::Value Value;
   1.236 +    ///The type of the map that stores the arc capacities.
   1.237 +    typedef typename Traits::CapacityMap CapacityMap;
   1.238 +    ///The type of the map indicating if a node is processed.
   1.239 +    typedef typename Traits::ProcessedMap ProcessedMap;
   1.240 +    ///The type of the map that stores the cardinalities of the nodes.
   1.241 +    typedef typename Traits::CardinalityMap CardinalityMap;
   1.242 +    ///The cross reference type used for the current heap.
   1.243 +    typedef typename Traits::HeapCrossRef HeapCrossRef;
   1.244 +    ///The heap type used by the algorithm. It maximizes the priorities.
   1.245 +    typedef typename Traits::Heap Heap;
   1.246 +  private:
   1.247 +    // Pointer to the underlying digraph.
   1.248 +    const Digraph *_graph;
   1.249 +    // Pointer to the capacity map
   1.250 +    const CapacityMap *_capacity;
   1.251 +    // Indicates if \ref _capacity is locally allocated (\c true) or not.
   1.252 +    bool local_capacity;
   1.253 +    // Pointer to the map of cardinality.
   1.254 +    CardinalityMap *_cardinality;
   1.255 +    // Indicates if \ref _cardinality is locally allocated (\c true) or not.
   1.256 +    bool local_cardinality;
   1.257 +    // Pointer to the map of processed status of the nodes.
   1.258 +    ProcessedMap *_processed;
   1.259 +    // Indicates if \ref _processed is locally allocated (\c true) or not.
   1.260 +    bool local_processed;
   1.261 +    // Pointer to the heap cross references.
   1.262 +    HeapCrossRef *_heap_cross_ref;
   1.263 +    // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   1.264 +    bool local_heap_cross_ref;
   1.265 +    // Pointer to the heap.
   1.266 +    Heap *_heap;
   1.267 +    // Indicates if \ref _heap is locally allocated (\c true) or not.
   1.268 +    bool local_heap;
   1.269 +
   1.270 +  public :
   1.271 +
   1.272 +    typedef MaxCardinalitySearch Create;
   1.273 +
   1.274 +    ///\name Named template parameters
   1.275 +
   1.276 +    ///@{
   1.277 +
   1.278 +    template <class T>
   1.279 +    struct DefCapacityMapTraits : public Traits {
   1.280 +      typedef T CapacityMap;
   1.281 +      static CapacityMap *createCapacityMap(const Digraph &) {
   1.282 +               LEMON_ASSERT(false,"Uninitialized parameter.");
   1.283 +        return 0;
   1.284 +      }
   1.285 +    };
   1.286 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.287 +    /// CapacityMap type
   1.288 +    ///
   1.289 +    /// \ref named-templ-param "Named parameter" for setting CapacityMap type
   1.290 +    /// for the algorithm.
   1.291 +    template <class T>
   1.292 +    struct SetCapacityMap
   1.293 +      : public MaxCardinalitySearch<Digraph, CapacityMap,
   1.294 +                                    DefCapacityMapTraits<T> > {
   1.295 +      typedef MaxCardinalitySearch<Digraph, CapacityMap,
   1.296 +                                   DefCapacityMapTraits<T> > Create;
   1.297 +    };
   1.298 +
   1.299 +    template <class T>
   1.300 +    struct DefCardinalityMapTraits : public Traits {
   1.301 +      typedef T CardinalityMap;
   1.302 +      static CardinalityMap *createCardinalityMap(const Digraph &)
   1.303 +      {
   1.304 +        LEMON_ASSERT(false,"Uninitialized parameter.");
   1.305 +        return 0;
   1.306 +      }
   1.307 +    };
   1.308 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.309 +    /// CardinalityMap type
   1.310 +    ///
   1.311 +    /// \ref named-templ-param "Named parameter" for setting CardinalityMap
   1.312 +    /// type for the algorithm.
   1.313 +    template <class T>
   1.314 +    struct SetCardinalityMap
   1.315 +      : public MaxCardinalitySearch<Digraph, CapacityMap,
   1.316 +                                    DefCardinalityMapTraits<T> > {
   1.317 +      typedef MaxCardinalitySearch<Digraph, CapacityMap,
   1.318 +                                   DefCardinalityMapTraits<T> > Create;
   1.319 +    };
   1.320 +
   1.321 +    template <class T>
   1.322 +    struct DefProcessedMapTraits : public Traits {
   1.323 +      typedef T ProcessedMap;
   1.324 +      static ProcessedMap *createProcessedMap(const Digraph &) {
   1.325 +               LEMON_ASSERT(false,"Uninitialized parameter.");
   1.326 +        return 0;
   1.327 +      }
   1.328 +    };
   1.329 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.330 +    /// ProcessedMap type
   1.331 +    ///
   1.332 +    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
   1.333 +    /// for the algorithm.
   1.334 +    template <class T>
   1.335 +    struct SetProcessedMap
   1.336 +      : public MaxCardinalitySearch<Digraph, CapacityMap,
   1.337 +                                    DefProcessedMapTraits<T> > {
   1.338 +      typedef MaxCardinalitySearch<Digraph, CapacityMap,
   1.339 +                                   DefProcessedMapTraits<T> > Create;
   1.340 +    };
   1.341 +
   1.342 +    template <class H, class CR>
   1.343 +    struct DefHeapTraits : public Traits {
   1.344 +      typedef CR HeapCrossRef;
   1.345 +      typedef H Heap;
   1.346 +      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
   1.347 +             LEMON_ASSERT(false,"Uninitialized parameter.");
   1.348 +        return 0;
   1.349 +      }
   1.350 +      static Heap *createHeap(HeapCrossRef &) {
   1.351 +               LEMON_ASSERT(false,"Uninitialized parameter.");
   1.352 +        return 0;
   1.353 +      }
   1.354 +    };
   1.355 +    /// \brief \ref named-templ-param "Named parameter" for setting heap
   1.356 +    /// and cross reference type
   1.357 +    ///
   1.358 +    /// \ref named-templ-param "Named parameter" for setting heap and cross
   1.359 +    /// reference type for the algorithm.
   1.360 +    template <class H, class CR = typename Digraph::template NodeMap<int> >
   1.361 +    struct SetHeap
   1.362 +      : public MaxCardinalitySearch<Digraph, CapacityMap,
   1.363 +                                    DefHeapTraits<H, CR> > {
   1.364 +      typedef MaxCardinalitySearch< Digraph, CapacityMap,
   1.365 +                                    DefHeapTraits<H, CR> > Create;
   1.366 +    };
   1.367 +
   1.368 +    template <class H, class CR>
   1.369 +    struct DefStandardHeapTraits : public Traits {
   1.370 +      typedef CR HeapCrossRef;
   1.371 +      typedef H Heap;
   1.372 +      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
   1.373 +        return new HeapCrossRef(digraph);
   1.374 +      }
   1.375 +      static Heap *createHeap(HeapCrossRef &crossref) {
   1.376 +        return new Heap(crossref);
   1.377 +      }
   1.378 +    };
   1.379 +
   1.380 +    /// \brief \ref named-templ-param "Named parameter" for setting heap and
   1.381 +    /// cross reference type with automatic allocation
   1.382 +    ///
   1.383 +    /// \ref named-templ-param "Named parameter" for setting heap and cross
   1.384 +    /// reference type. It can allocate the heap and the cross reference
   1.385 +    /// object if the cross reference's constructor waits for the digraph as
   1.386 +    /// parameter and the heap's constructor waits for the cross reference.
   1.387 +    template <class H, class CR = typename Digraph::template NodeMap<int> >
   1.388 +    struct SetStandardHeap
   1.389 +      : public MaxCardinalitySearch<Digraph, CapacityMap,
   1.390 +                                    DefStandardHeapTraits<H, CR> > {
   1.391 +      typedef MaxCardinalitySearch<Digraph, CapacityMap,
   1.392 +                                   DefStandardHeapTraits<H, CR> >
   1.393 +      Create;
   1.394 +    };
   1.395 +
   1.396 +    ///@}
   1.397 +
   1.398 +
   1.399 +  protected:
   1.400 +
   1.401 +    MaxCardinalitySearch() {}
   1.402 +
   1.403 +  public:
   1.404 +
   1.405 +    /// \brief Constructor.
   1.406 +    ///
   1.407 +    ///\param digraph the digraph the algorithm will run on.
   1.408 +    ///\param capacity the capacity map used by the algorithm.
   1.409 +    MaxCardinalitySearch(const Digraph& digraph,
   1.410 +                         const CapacityMap& capacity) :
   1.411 +      _graph(&digraph),
   1.412 +      _capacity(&capacity), local_capacity(false),
   1.413 +      _cardinality(0), local_cardinality(false),
   1.414 +      _processed(0), local_processed(false),
   1.415 +      _heap_cross_ref(0), local_heap_cross_ref(false),
   1.416 +      _heap(0), local_heap(false)
   1.417 +    { }
   1.418 +
   1.419 +    /// \brief Constructor.
   1.420 +    ///
   1.421 +    ///\param digraph the digraph the algorithm will run on.
   1.422 +    ///
   1.423 +    ///A constant 1 capacity map will be allocated.
   1.424 +    MaxCardinalitySearch(const Digraph& digraph) :
   1.425 +      _graph(&digraph),
   1.426 +      _capacity(0), local_capacity(false),
   1.427 +      _cardinality(0), local_cardinality(false),
   1.428 +      _processed(0), local_processed(false),
   1.429 +      _heap_cross_ref(0), local_heap_cross_ref(false),
   1.430 +      _heap(0), local_heap(false)
   1.431 +    { }
   1.432 +
   1.433 +    /// \brief Destructor.
   1.434 +    ~MaxCardinalitySearch() {
   1.435 +      if(local_capacity) delete _capacity;
   1.436 +      if(local_cardinality) delete _cardinality;
   1.437 +      if(local_processed) delete _processed;
   1.438 +      if(local_heap_cross_ref) delete _heap_cross_ref;
   1.439 +      if(local_heap) delete _heap;
   1.440 +    }
   1.441 +
   1.442 +    /// \brief Sets the capacity map.
   1.443 +    ///
   1.444 +    /// Sets the capacity map.
   1.445 +    /// \return <tt> (*this) </tt>
   1.446 +    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
   1.447 +      if (local_capacity) {
   1.448 +        delete _capacity;
   1.449 +        local_capacity=false;
   1.450 +      }
   1.451 +      _capacity=&m;
   1.452 +      return *this;
   1.453 +    }
   1.454 +
   1.455 +    /// \brief Returns a const reference to the capacity map.
   1.456 +    ///
   1.457 +    /// Returns a const reference to the capacity map used by
   1.458 +    /// the algorithm.
   1.459 +    const CapacityMap &capacityMap() const {
   1.460 +      return *_capacity;
   1.461 +    }
   1.462 +
   1.463 +    /// \brief Sets the map storing the cardinalities calculated by the
   1.464 +    /// algorithm.
   1.465 +    ///
   1.466 +    /// Sets the map storing the cardinalities calculated by the algorithm.
   1.467 +    /// If you don't use this function before calling \ref run(),
   1.468 +    /// it will allocate one. The destuctor deallocates this
   1.469 +    /// automatically allocated map, of course.
   1.470 +    /// \return <tt> (*this) </tt>
   1.471 +    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
   1.472 +      if(local_cardinality) {
   1.473 +        delete _cardinality;
   1.474 +        local_cardinality=false;
   1.475 +      }
   1.476 +      _cardinality = &m;
   1.477 +      return *this;
   1.478 +    }
   1.479 +
   1.480 +    /// \brief Sets the map storing the processed nodes.
   1.481 +    ///
   1.482 +    /// Sets the map storing the processed nodes.
   1.483 +    /// If you don't use this function before calling \ref run(),
   1.484 +    /// it will allocate one. The destuctor deallocates this
   1.485 +    /// automatically allocated map, of course.
   1.486 +    /// \return <tt> (*this) </tt>
   1.487 +    MaxCardinalitySearch &processedMap(ProcessedMap &m)
   1.488 +    {
   1.489 +      if(local_processed) {
   1.490 +        delete _processed;
   1.491 +        local_processed=false;
   1.492 +      }
   1.493 +      _processed = &m;
   1.494 +      return *this;
   1.495 +    }
   1.496 +
   1.497 +    /// \brief Returns a const reference to the cardinality map.
   1.498 +    ///
   1.499 +    /// Returns a const reference to the cardinality map used by
   1.500 +    /// the algorithm.
   1.501 +    const ProcessedMap &processedMap() const {
   1.502 +      return *_processed;
   1.503 +    }
   1.504 +
   1.505 +    /// \brief Sets the heap and the cross reference used by algorithm.
   1.506 +    ///
   1.507 +    /// Sets the heap and the cross reference used by algorithm.
   1.508 +    /// If you don't use this function before calling \ref run(),
   1.509 +    /// it will allocate one. The destuctor deallocates this
   1.510 +    /// automatically allocated map, of course.
   1.511 +    /// \return <tt> (*this) </tt>
   1.512 +    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
   1.513 +      if(local_heap_cross_ref) {
   1.514 +        delete _heap_cross_ref;
   1.515 +        local_heap_cross_ref = false;
   1.516 +      }
   1.517 +      _heap_cross_ref = &cr;
   1.518 +      if(local_heap) {
   1.519 +        delete _heap;
   1.520 +        local_heap = false;
   1.521 +      }
   1.522 +      _heap = &hp;
   1.523 +      return *this;
   1.524 +    }
   1.525 +
   1.526 +    /// \brief Returns a const reference to the heap.
   1.527 +    ///
   1.528 +    /// Returns a const reference to the heap used by
   1.529 +    /// the algorithm.
   1.530 +    const Heap &heap() const {
   1.531 +      return *_heap;
   1.532 +    }
   1.533 +
   1.534 +    /// \brief Returns a const reference to the cross reference.
   1.535 +    ///
   1.536 +    /// Returns a const reference to the cross reference
   1.537 +    /// of the heap.
   1.538 +    const HeapCrossRef &heapCrossRef() const {
   1.539 +      return *_heap_cross_ref;
   1.540 +    }
   1.541 +
   1.542 +  private:
   1.543 +
   1.544 +    typedef typename Digraph::Node Node;
   1.545 +    typedef typename Digraph::NodeIt NodeIt;
   1.546 +    typedef typename Digraph::Arc Arc;
   1.547 +    typedef typename Digraph::InArcIt InArcIt;
   1.548 +
   1.549 +    void create_maps() {
   1.550 +      if(!_capacity) {
   1.551 +        local_capacity = true;
   1.552 +        _capacity = Traits::createCapacityMap(*_graph);
   1.553 +      }
   1.554 +      if(!_cardinality) {
   1.555 +        local_cardinality = true;
   1.556 +        _cardinality = Traits::createCardinalityMap(*_graph);
   1.557 +      }
   1.558 +      if(!_processed) {
   1.559 +        local_processed = true;
   1.560 +        _processed = Traits::createProcessedMap(*_graph);
   1.561 +      }
   1.562 +      if (!_heap_cross_ref) {
   1.563 +        local_heap_cross_ref = true;
   1.564 +        _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
   1.565 +      }
   1.566 +      if (!_heap) {
   1.567 +        local_heap = true;
   1.568 +        _heap = Traits::createHeap(*_heap_cross_ref);
   1.569 +      }
   1.570 +    }
   1.571 +
   1.572 +    void finalizeNodeData(Node node, Value capacity) {
   1.573 +      _processed->set(node, true);
   1.574 +      _cardinality->set(node, capacity);
   1.575 +    }
   1.576 +
   1.577 +  public:
   1.578 +    /// \name Execution control
   1.579 +    /// The simplest way to execute the algorithm is to use
   1.580 +    /// one of the member functions called \ref run().
   1.581 +    /// \n
   1.582 +    /// If you need more control on the execution,
   1.583 +    /// first you must call \ref init(), then you can add several source nodes
   1.584 +    /// with \ref addSource().
   1.585 +    /// Finally \ref start() will perform the computation.
   1.586 +
   1.587 +    ///@{
   1.588 +
   1.589 +    /// \brief Initializes the internal data structures.
   1.590 +    ///
   1.591 +    /// Initializes the internal data structures, and clears the heap.
   1.592 +    void init() {
   1.593 +      create_maps();
   1.594 +      _heap->clear();
   1.595 +      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
   1.596 +        _processed->set(it, false);
   1.597 +        _heap_cross_ref->set(it, Heap::PRE_HEAP);
   1.598 +      }
   1.599 +    }
   1.600 +
   1.601 +    /// \brief Adds a new source node.
   1.602 +    ///
   1.603 +    /// Adds a new source node to the priority heap.
   1.604 +    ///
   1.605 +    /// It checks if the node has not yet been added to the heap.
   1.606 +    void addSource(Node source, Value capacity = 0) {
   1.607 +      if(_heap->state(source) == Heap::PRE_HEAP) {
   1.608 +        _heap->push(source, capacity);
   1.609 +      }
   1.610 +    }
   1.611 +
   1.612 +    /// \brief Processes the next node in the priority heap
   1.613 +    ///
   1.614 +    /// Processes the next node in the priority heap.
   1.615 +    ///
   1.616 +    /// \return The processed node.
   1.617 +    ///
   1.618 +    /// \warning The priority heap must not be empty!
   1.619 +    Node processNextNode() {
   1.620 +      Node node = _heap->top();
   1.621 +      finalizeNodeData(node, _heap->prio());
   1.622 +      _heap->pop();
   1.623 +
   1.624 +      for (InArcIt it(*_graph, node); it != INVALID; ++it) {
   1.625 +        Node source = _graph->source(it);
   1.626 +        switch (_heap->state(source)) {
   1.627 +        case Heap::PRE_HEAP:
   1.628 +          _heap->push(source, (*_capacity)[it]);
   1.629 +          break;
   1.630 +        case Heap::IN_HEAP:
   1.631 +          _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
   1.632 +          break;
   1.633 +        case Heap::POST_HEAP:
   1.634 +          break;
   1.635 +        }
   1.636 +      }
   1.637 +      return node;
   1.638 +    }
   1.639 +
   1.640 +    /// \brief Next node to be processed.
   1.641 +    ///
   1.642 +    /// Next node to be processed.
   1.643 +    ///
   1.644 +    /// \return The next node to be processed or INVALID if the
   1.645 +    /// priority heap is empty.
   1.646 +    Node nextNode() {
   1.647 +      return !_heap->empty() ? _heap->top() : INVALID;
   1.648 +    }
   1.649 +
   1.650 +    /// \brief Returns \c false if there are nodes
   1.651 +    /// to be processed in the priority heap
   1.652 +    ///
   1.653 +    /// Returns \c false if there are nodes
   1.654 +    /// to be processed in the priority heap
   1.655 +    bool emptyQueue() { return _heap->empty(); }
   1.656 +    /// \brief Returns the number of the nodes to be processed
   1.657 +    /// in the priority heap
   1.658 +    ///
   1.659 +    /// Returns the number of the nodes to be processed in the priority heap
   1.660 +    int emptySize() { return _heap->size(); }
   1.661 +
   1.662 +    /// \brief Executes the algorithm.
   1.663 +    ///
   1.664 +    /// Executes the algorithm.
   1.665 +    ///
   1.666 +    ///\pre init() must be called and at least one node should be added
   1.667 +    /// with addSource() before using this function.
   1.668 +    ///
   1.669 +    /// This method runs the Maximum Cardinality Search algorithm from the
   1.670 +    /// source node(s).
   1.671 +    void start() {
   1.672 +      while ( !_heap->empty() ) processNextNode();
   1.673 +    }
   1.674 +
   1.675 +    /// \brief Executes the algorithm until \c dest is reached.
   1.676 +    ///
   1.677 +    /// Executes the algorithm until \c dest is reached.
   1.678 +    ///
   1.679 +    /// \pre init() must be called and at least one node should be added
   1.680 +    /// with addSource() before using this function.
   1.681 +    ///
   1.682 +    /// This method runs the %MaxCardinalitySearch algorithm from the source
   1.683 +    /// nodes.
   1.684 +    void start(Node dest) {
   1.685 +      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   1.686 +      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
   1.687 +    }
   1.688 +
   1.689 +    /// \brief Executes the algorithm until a condition is met.
   1.690 +    ///
   1.691 +    /// Executes the algorithm until a condition is met.
   1.692 +    ///
   1.693 +    /// \pre init() must be called and at least one node should be added
   1.694 +    /// with addSource() before using this function.
   1.695 +    ///
   1.696 +    /// \param nm must be a bool (or convertible) node map. The algorithm
   1.697 +    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
   1.698 +    template <typename NodeBoolMap>
   1.699 +    void start(const NodeBoolMap &nm) {
   1.700 +      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
   1.701 +      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
   1.702 +    }
   1.703 +
   1.704 +    /// \brief Runs the maximum cardinality search algorithm from node \c s.
   1.705 +    ///
   1.706 +    /// This method runs the %MaxCardinalitySearch algorithm from a root
   1.707 +    /// node \c s.
   1.708 +    ///
   1.709 +    ///\note d.run(s) is just a shortcut of the following code.
   1.710 +    ///\code
   1.711 +    ///  d.init();
   1.712 +    ///  d.addSource(s);
   1.713 +    ///  d.start();
   1.714 +    ///\endcode
   1.715 +    void run(Node s) {
   1.716 +      init();
   1.717 +      addSource(s);
   1.718 +      start();
   1.719 +    }
   1.720 +
   1.721 +    /// \brief Runs the maximum cardinality search algorithm for the
   1.722 +    /// whole digraph.
   1.723 +    ///
   1.724 +    /// This method runs the %MaxCardinalitySearch algorithm from all
   1.725 +    /// unprocessed node of the digraph.
   1.726 +    ///
   1.727 +    ///\note d.run(s) is just a shortcut of the following code.
   1.728 +    ///\code
   1.729 +    ///  d.init();
   1.730 +    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
   1.731 +    ///    if (!d.reached(it)) {
   1.732 +    ///      d.addSource(s);
   1.733 +    ///      d.start();
   1.734 +    ///    }
   1.735 +    ///  }
   1.736 +    ///\endcode
   1.737 +    void run() {
   1.738 +      init();
   1.739 +      for (NodeIt it(*_graph); it != INVALID; ++it) {
   1.740 +        if (!reached(it)) {
   1.741 +          addSource(it);
   1.742 +          start();
   1.743 +        }
   1.744 +      }
   1.745 +    }
   1.746 +
   1.747 +    ///@}
   1.748 +
   1.749 +    /// \name Query Functions
   1.750 +    /// The results of the maximum cardinality search algorithm can be
   1.751 +    /// obtained using these functions.
   1.752 +    /// \n
   1.753 +    /// Before the use of these functions, either run() or start() must be
   1.754 +    /// called.
   1.755 +
   1.756 +    ///@{
   1.757 +
   1.758 +    /// \brief The cardinality of a node.
   1.759 +    ///
   1.760 +    /// Returns the cardinality of a node.
   1.761 +    /// \pre \ref run() must be called before using this function.
   1.762 +    /// \warning If node \c v in unreachable from the root the return value
   1.763 +    /// of this funcion is undefined.
   1.764 +    Value cardinality(Node node) const { return (*_cardinality)[node]; }
   1.765 +
   1.766 +    /// \brief The current cardinality of a node.
   1.767 +    ///
   1.768 +    /// Returns the current cardinality of a node.
   1.769 +    /// \pre the given node should be reached but not processed
   1.770 +    Value currentCardinality(Node node) const { return (*_heap)[node]; }
   1.771 +
   1.772 +    /// \brief Returns a reference to the NodeMap of cardinalities.
   1.773 +    ///
   1.774 +    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
   1.775 +    /// must be called before using this function.
   1.776 +    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
   1.777 +
   1.778 +    /// \brief Checks if a node is reachable from the root.
   1.779 +    ///
   1.780 +    /// Returns \c true if \c v is reachable from the root.
   1.781 +    /// \warning The source nodes are initated as unreached.
   1.782 +    /// \pre \ref run() must be called before using this function.
   1.783 +    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   1.784 +
   1.785 +    /// \brief Checks if a node is processed.
   1.786 +    ///
   1.787 +    /// Returns \c true if \c v is processed, i.e. the shortest
   1.788 +    /// path to \c v has already found.
   1.789 +    /// \pre \ref run() must be called before using this function.
   1.790 +    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   1.791 +
   1.792 +    ///@}
   1.793 +  };
   1.794 +
   1.795 +}
   1.796 +
   1.797 +#endif