lemon/max_cardinality_search.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 13:16:27 +0100
changeset 1050 d9d1cb759951
parent 916 70bee017b584
child 1092 dceba191c00d
permissions -rw-r--r--
Add images to the doc of two groups (#459)
thoneyvazul@916
     1
/* -*- C++ -*-
thoneyvazul@916
     2
 *
thoneyvazul@916
     3
 * This file is a part of LEMON, a generic C++ optimization library
thoneyvazul@916
     4
 *
thoneyvazul@916
     5
 * Copyright (C) 2003-2010
thoneyvazul@916
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
thoneyvazul@916
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
thoneyvazul@916
     8
 *
thoneyvazul@916
     9
 * Permission to use, modify and distribute this software is granted
thoneyvazul@916
    10
 * provided that this copyright notice appears in all copies. For
thoneyvazul@916
    11
 * precise terms see the accompanying LICENSE file.
thoneyvazul@916
    12
 *
thoneyvazul@916
    13
 * This software is provided "AS IS" with no warranty of any kind,
thoneyvazul@916
    14
 * express or implied, and with no claim as to its suitability for any
thoneyvazul@916
    15
 * purpose.
thoneyvazul@916
    16
 *
thoneyvazul@916
    17
 */
thoneyvazul@916
    18
thoneyvazul@916
    19
#ifndef LEMON_MAX_CARDINALITY_SEARCH_H
thoneyvazul@916
    20
#define LEMON_MAX_CARDINALITY_SEARCH_H
thoneyvazul@916
    21
thoneyvazul@916
    22
thoneyvazul@916
    23
/// \ingroup search
thoneyvazul@916
    24
/// \file 
thoneyvazul@916
    25
/// \brief Maximum cardinality search in undirected digraphs.
thoneyvazul@916
    26
thoneyvazul@916
    27
#include <lemon/bin_heap.h>
thoneyvazul@916
    28
#include <lemon/bucket_heap.h>
thoneyvazul@916
    29
thoneyvazul@916
    30
#include <lemon/error.h>
thoneyvazul@916
    31
#include <lemon/maps.h>
thoneyvazul@916
    32
thoneyvazul@916
    33
#include <functional>
thoneyvazul@916
    34
thoneyvazul@916
    35
namespace lemon {
thoneyvazul@916
    36
thoneyvazul@916
    37
  /// \brief Default traits class of MaxCardinalitySearch class.
thoneyvazul@916
    38
  ///
thoneyvazul@916
    39
  /// Default traits class of MaxCardinalitySearch class.
thoneyvazul@916
    40
  /// \param Digraph Digraph type.
thoneyvazul@916
    41
  /// \param CapacityMap Type of capacity map.
thoneyvazul@916
    42
  template <typename GR, typename CAP>
thoneyvazul@916
    43
  struct MaxCardinalitySearchDefaultTraits {
thoneyvazul@916
    44
    /// The digraph type the algorithm runs on. 
thoneyvazul@916
    45
    typedef GR Digraph;
thoneyvazul@916
    46
thoneyvazul@916
    47
    template <typename CM>
thoneyvazul@916
    48
    struct CapMapSelector {
thoneyvazul@916
    49
thoneyvazul@916
    50
      typedef CM CapacityMap;
thoneyvazul@916
    51
thoneyvazul@916
    52
      static CapacityMap *createCapacityMap(const Digraph& g) {
thoneyvazul@916
    53
	return new CapacityMap(g);
thoneyvazul@916
    54
      }
thoneyvazul@916
    55
    };
thoneyvazul@916
    56
thoneyvazul@916
    57
    template <typename CM>
thoneyvazul@916
    58
    struct CapMapSelector<ConstMap<CM, Const<int, 1> > > {
thoneyvazul@916
    59
thoneyvazul@916
    60
      typedef ConstMap<CM, Const<int, 1> > CapacityMap;
thoneyvazul@916
    61
thoneyvazul@916
    62
      static CapacityMap *createCapacityMap(const Digraph&) {
thoneyvazul@916
    63
	return new CapacityMap;
thoneyvazul@916
    64
      }
thoneyvazul@916
    65
    };
thoneyvazul@916
    66
thoneyvazul@916
    67
    /// \brief The type of the map that stores the arc capacities.
thoneyvazul@916
    68
    ///
thoneyvazul@916
    69
    /// The type of the map that stores the arc capacities.
thoneyvazul@916
    70
    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
thoneyvazul@916
    71
    typedef typename CapMapSelector<CAP>::CapacityMap CapacityMap;
thoneyvazul@916
    72
thoneyvazul@916
    73
    /// \brief The type of the capacity of the arcs.
thoneyvazul@916
    74
    typedef typename CapacityMap::Value Value;
thoneyvazul@916
    75
thoneyvazul@916
    76
    /// \brief Instantiates a CapacityMap.
thoneyvazul@916
    77
    ///
thoneyvazul@916
    78
    /// This function instantiates a \ref CapacityMap.
thoneyvazul@916
    79
    /// \param digraph is the digraph, to which we would like to define
thoneyvazul@916
    80
    /// the CapacityMap.
thoneyvazul@916
    81
    static CapacityMap *createCapacityMap(const Digraph& digraph) {
thoneyvazul@916
    82
      return CapMapSelector<CapacityMap>::createCapacityMap(digraph);
thoneyvazul@916
    83
    }
thoneyvazul@916
    84
thoneyvazul@916
    85
    /// \brief The cross reference type used by heap.
thoneyvazul@916
    86
    ///
thoneyvazul@916
    87
    /// The cross reference type used by heap.
thoneyvazul@916
    88
    /// Usually it is \c Digraph::NodeMap<int>.
thoneyvazul@916
    89
    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
thoneyvazul@916
    90
thoneyvazul@916
    91
    /// \brief Instantiates a HeapCrossRef.
thoneyvazul@916
    92
    ///
thoneyvazul@916
    93
    /// This function instantiates a \ref HeapCrossRef. 
thoneyvazul@916
    94
    /// \param digraph is the digraph, to which we would like to define the 
thoneyvazul@916
    95
    /// HeapCrossRef.
thoneyvazul@916
    96
    static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
thoneyvazul@916
    97
      return new HeapCrossRef(digraph);
thoneyvazul@916
    98
    }
thoneyvazul@916
    99
    
thoneyvazul@916
   100
    template <typename CapacityMap>
thoneyvazul@916
   101
    struct HeapSelector {
thoneyvazul@916
   102
      template <typename Value, typename Ref>
thoneyvazul@916
   103
      struct Selector { 
thoneyvazul@916
   104
        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
thoneyvazul@916
   105
      };
thoneyvazul@916
   106
    };
thoneyvazul@916
   107
thoneyvazul@916
   108
    template <typename CapacityKey>
thoneyvazul@916
   109
    struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
thoneyvazul@916
   110
      template <typename Value, typename Ref>
thoneyvazul@916
   111
      struct Selector {
thoneyvazul@916
   112
        typedef BucketHeap<Ref, false > Heap;
thoneyvazul@916
   113
      };
thoneyvazul@916
   114
    };
thoneyvazul@916
   115
thoneyvazul@916
   116
    /// \brief The heap type used by MaxCardinalitySearch algorithm.
thoneyvazul@916
   117
    ///
thoneyvazul@916
   118
    /// The heap type used by MaxCardinalitySearch algorithm. It should
thoneyvazul@916
   119
    /// maximalize the priorities. The default heap type is
thoneyvazul@916
   120
    /// the \ref BinHeap, but it is specialized when the
thoneyvazul@916
   121
    /// CapacityMap is ConstMap<Digraph::Node, Const<int, 1> >
thoneyvazul@916
   122
    /// to BucketHeap.
thoneyvazul@916
   123
    ///
thoneyvazul@916
   124
    /// \sa MaxCardinalitySearch
thoneyvazul@916
   125
    typedef typename HeapSelector<CapacityMap>
thoneyvazul@916
   126
    ::template Selector<Value, HeapCrossRef>
thoneyvazul@916
   127
    ::Heap Heap;
thoneyvazul@916
   128
thoneyvazul@916
   129
    /// \brief Instantiates a Heap.
thoneyvazul@916
   130
    ///
thoneyvazul@916
   131
    /// This function instantiates a \ref Heap. 
thoneyvazul@916
   132
    /// \param crossref The cross reference of the heap.
thoneyvazul@916
   133
    static Heap *createHeap(HeapCrossRef& crossref) {
thoneyvazul@916
   134
      return new Heap(crossref);
thoneyvazul@916
   135
    }
thoneyvazul@916
   136
thoneyvazul@916
   137
    /// \brief The type of the map that stores whether a node is processed.
thoneyvazul@916
   138
    ///
thoneyvazul@916
   139
    /// The type of the map that stores whether a node is processed.
thoneyvazul@916
   140
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
thoneyvazul@916
   141
    /// By default it is a NullMap.
thoneyvazul@916
   142
    typedef NullMap<typename Digraph::Node, bool> ProcessedMap;
thoneyvazul@916
   143
thoneyvazul@916
   144
    /// \brief Instantiates a ProcessedMap.
thoneyvazul@916
   145
    ///
thoneyvazul@916
   146
    /// This function instantiates a \ref ProcessedMap. 
thoneyvazul@916
   147
    /// \param digraph is the digraph, to which
thoneyvazul@916
   148
    /// we would like to define the \ref ProcessedMap
thoneyvazul@916
   149
#ifdef DOXYGEN
thoneyvazul@916
   150
    static ProcessedMap *createProcessedMap(const Digraph &digraph)
thoneyvazul@916
   151
#else
thoneyvazul@916
   152
    static ProcessedMap *createProcessedMap(const Digraph &)
thoneyvazul@916
   153
#endif
thoneyvazul@916
   154
    {
thoneyvazul@916
   155
      return new ProcessedMap();
thoneyvazul@916
   156
    }
thoneyvazul@916
   157
thoneyvazul@916
   158
    /// \brief The type of the map that stores the cardinalities of the nodes.
thoneyvazul@916
   159
    /// 
thoneyvazul@916
   160
    /// The type of the map that stores the cardinalities of the nodes.
thoneyvazul@916
   161
    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
thoneyvazul@916
   162
    typedef typename Digraph::template NodeMap<Value> CardinalityMap;
thoneyvazul@916
   163
thoneyvazul@916
   164
    /// \brief Instantiates a CardinalityMap.
thoneyvazul@916
   165
    ///
thoneyvazul@916
   166
    /// This function instantiates a \ref CardinalityMap. 
thoneyvazul@916
   167
    /// \param digraph is the digraph, to which we would like to define the \ref 
thoneyvazul@916
   168
    /// CardinalityMap
thoneyvazul@916
   169
    static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
thoneyvazul@916
   170
      return new CardinalityMap(digraph);
thoneyvazul@916
   171
    }
thoneyvazul@916
   172
thoneyvazul@916
   173
thoneyvazul@916
   174
  };
thoneyvazul@916
   175
  
thoneyvazul@916
   176
  /// \ingroup search
thoneyvazul@916
   177
  ///
thoneyvazul@916
   178
  /// \brief Maximum Cardinality Search algorithm class.
thoneyvazul@916
   179
  ///
thoneyvazul@916
   180
  /// This class provides an efficient implementation of Maximum Cardinality 
thoneyvazul@916
   181
  /// Search algorithm. The maximum cardinality search first chooses any 
thoneyvazul@916
   182
  /// node of the digraph. Then every time it chooses one unprocessed node
thoneyvazul@916
   183
  /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
thoneyvazul@916
   184
  /// which were previusly processed.
thoneyvazul@916
   185
  /// If there is a cut in the digraph the algorithm should choose
thoneyvazul@916
   186
  /// again any unprocessed node of the digraph.
thoneyvazul@916
   187
thoneyvazul@916
   188
  /// The arc capacities are passed to the algorithm using a
thoneyvazul@916
   189
  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
thoneyvazul@916
   190
  /// kind of capacity.
thoneyvazul@916
   191
  ///
thoneyvazul@916
   192
  /// The type of the capacity is determined by the \ref 
thoneyvazul@916
   193
  /// concepts::ReadMap::Value "Value" of the capacity map.
thoneyvazul@916
   194
  ///
thoneyvazul@916
   195
  /// It is also possible to change the underlying priority heap.
thoneyvazul@916
   196
  ///
thoneyvazul@916
   197
  ///
thoneyvazul@916
   198
  /// \param GR The digraph type the algorithm runs on. The value of
thoneyvazul@916
   199
  /// Digraph is not used directly by the search algorithm, it 
thoneyvazul@916
   200
  /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
thoneyvazul@916
   201
  /// \param CAP This read-only ArcMap determines the capacities of 
thoneyvazul@916
   202
  /// the arcs. It is read once for each arc, so the map may involve in
thoneyvazul@916
   203
  /// relatively time consuming process to compute the arc capacity if
thoneyvazul@916
   204
  /// it is necessary. The default map type is \ref
thoneyvazul@916
   205
  /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
thoneyvazul@916
   206
  /// of CapacityMap is not used directly by search algorithm, it is only 
thoneyvazul@916
   207
  /// passed to \ref MaxCardinalitySearchDefaultTraits.  
thoneyvazul@916
   208
  /// \param TR Traits class to set various data types used by the 
thoneyvazul@916
   209
  /// algorithm.  The default traits class is 
thoneyvazul@916
   210
  /// \ref MaxCardinalitySearchDefaultTraits 
thoneyvazul@916
   211
  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".  
thoneyvazul@916
   212
  /// See \ref MaxCardinalitySearchDefaultTraits 
thoneyvazul@916
   213
  /// for the documentation of a MaxCardinalitySearch traits class.
thoneyvazul@916
   214
thoneyvazul@916
   215
#ifdef DOXYGEN
thoneyvazul@916
   216
  template <typename GR, typename CAP, typename TR>
thoneyvazul@916
   217
#else
thoneyvazul@916
   218
  template <typename GR, typename CAP = 
thoneyvazul@916
   219
	    ConstMap<typename GR::Arc, Const<int,1> >,
thoneyvazul@916
   220
	    typename TR = 
thoneyvazul@916
   221
            MaxCardinalitySearchDefaultTraits<GR, CAP> >
thoneyvazul@916
   222
#endif
thoneyvazul@916
   223
  class MaxCardinalitySearch {
thoneyvazul@916
   224
  public:
thoneyvazul@916
   225
thoneyvazul@916
   226
    typedef TR Traits;
thoneyvazul@916
   227
    ///The type of the underlying digraph.
thoneyvazul@916
   228
    typedef typename Traits::Digraph Digraph;
thoneyvazul@916
   229
    
thoneyvazul@916
   230
    ///The type of the capacity of the arcs.
thoneyvazul@916
   231
    typedef typename Traits::CapacityMap::Value Value;
thoneyvazul@916
   232
    ///The type of the map that stores the arc capacities.
thoneyvazul@916
   233
    typedef typename Traits::CapacityMap CapacityMap;
thoneyvazul@916
   234
    ///The type of the map indicating if a node is processed.
thoneyvazul@916
   235
    typedef typename Traits::ProcessedMap ProcessedMap;
thoneyvazul@916
   236
    ///The type of the map that stores the cardinalities of the nodes.
thoneyvazul@916
   237
    typedef typename Traits::CardinalityMap CardinalityMap;
thoneyvazul@916
   238
    ///The cross reference type used for the current heap.
thoneyvazul@916
   239
    typedef typename Traits::HeapCrossRef HeapCrossRef;
thoneyvazul@916
   240
    ///The heap type used by the algorithm. It maximizes the priorities.
thoneyvazul@916
   241
    typedef typename Traits::Heap Heap;
thoneyvazul@916
   242
  private:
thoneyvazul@916
   243
    // Pointer to the underlying digraph.
thoneyvazul@916
   244
    const Digraph *_graph;
thoneyvazul@916
   245
    // Pointer to the capacity map
thoneyvazul@916
   246
    const CapacityMap *_capacity;
thoneyvazul@916
   247
    // Indicates if \ref _capacity is locally allocated (\c true) or not.
thoneyvazul@916
   248
    bool local_capacity;
thoneyvazul@916
   249
    // Pointer to the map of cardinality.
thoneyvazul@916
   250
    CardinalityMap *_cardinality;
thoneyvazul@916
   251
    // Indicates if \ref _cardinality is locally allocated (\c true) or not.
thoneyvazul@916
   252
    bool local_cardinality;
thoneyvazul@916
   253
    // Pointer to the map of processed status of the nodes.
thoneyvazul@916
   254
    ProcessedMap *_processed;
thoneyvazul@916
   255
    // Indicates if \ref _processed is locally allocated (\c true) or not.
thoneyvazul@916
   256
    bool local_processed;
thoneyvazul@916
   257
    // Pointer to the heap cross references.
thoneyvazul@916
   258
    HeapCrossRef *_heap_cross_ref;
thoneyvazul@916
   259
    // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
thoneyvazul@916
   260
    bool local_heap_cross_ref;
thoneyvazul@916
   261
    // Pointer to the heap.
thoneyvazul@916
   262
    Heap *_heap;
thoneyvazul@916
   263
    // Indicates if \ref _heap is locally allocated (\c true) or not.
thoneyvazul@916
   264
    bool local_heap;
thoneyvazul@916
   265
thoneyvazul@916
   266
  public :
thoneyvazul@916
   267
thoneyvazul@916
   268
    typedef MaxCardinalitySearch Create;
thoneyvazul@916
   269
 
thoneyvazul@916
   270
    ///\name Named template parameters
thoneyvazul@916
   271
thoneyvazul@916
   272
    ///@{
thoneyvazul@916
   273
thoneyvazul@916
   274
    template <class T>
thoneyvazul@916
   275
    struct DefCapacityMapTraits : public Traits {
thoneyvazul@916
   276
      typedef T CapacityMap;
thoneyvazul@916
   277
      static CapacityMap *createCapacityMap(const Digraph &) {
thoneyvazul@916
   278
       	LEMON_ASSERT(false,"Uninitialized parameter.");
thoneyvazul@916
   279
	return 0;
thoneyvazul@916
   280
      }
thoneyvazul@916
   281
    };
thoneyvazul@916
   282
    /// \brief \ref named-templ-param "Named parameter" for setting 
thoneyvazul@916
   283
    /// CapacityMap type
thoneyvazul@916
   284
    ///
thoneyvazul@916
   285
    /// \ref named-templ-param "Named parameter" for setting CapacityMap type
thoneyvazul@916
   286
    /// for the algorithm.
thoneyvazul@916
   287
    template <class T>
thoneyvazul@916
   288
    struct SetCapacityMap 
thoneyvazul@916
   289
      : public MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   290
                                    DefCapacityMapTraits<T> > { 
thoneyvazul@916
   291
      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   292
                                   DefCapacityMapTraits<T> > Create;
thoneyvazul@916
   293
    };
thoneyvazul@916
   294
thoneyvazul@916
   295
    template <class T>
thoneyvazul@916
   296
    struct DefCardinalityMapTraits : public Traits {
thoneyvazul@916
   297
      typedef T CardinalityMap;
thoneyvazul@916
   298
      static CardinalityMap *createCardinalityMap(const Digraph &) 
thoneyvazul@916
   299
      {
thoneyvazul@916
   300
	LEMON_ASSERT(false,"Uninitialized parameter.");
thoneyvazul@916
   301
	return 0;
thoneyvazul@916
   302
      }
thoneyvazul@916
   303
    };
thoneyvazul@916
   304
    /// \brief \ref named-templ-param "Named parameter" for setting 
thoneyvazul@916
   305
    /// CardinalityMap type
thoneyvazul@916
   306
    ///
thoneyvazul@916
   307
    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
thoneyvazul@916
   308
    /// type for the algorithm.
thoneyvazul@916
   309
    template <class T>
thoneyvazul@916
   310
    struct SetCardinalityMap 
thoneyvazul@916
   311
      : public MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   312
                                    DefCardinalityMapTraits<T> > { 
thoneyvazul@916
   313
      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   314
                                   DefCardinalityMapTraits<T> > Create;
thoneyvazul@916
   315
    };
thoneyvazul@916
   316
    
thoneyvazul@916
   317
    template <class T>
thoneyvazul@916
   318
    struct DefProcessedMapTraits : public Traits {
thoneyvazul@916
   319
      typedef T ProcessedMap;
thoneyvazul@916
   320
      static ProcessedMap *createProcessedMap(const Digraph &) {
thoneyvazul@916
   321
       	LEMON_ASSERT(false,"Uninitialized parameter.");
thoneyvazul@916
   322
	return 0;
thoneyvazul@916
   323
      }
thoneyvazul@916
   324
    };
thoneyvazul@916
   325
    /// \brief \ref named-templ-param "Named parameter" for setting 
thoneyvazul@916
   326
    /// ProcessedMap type
thoneyvazul@916
   327
    ///
thoneyvazul@916
   328
    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
thoneyvazul@916
   329
    /// for the algorithm.
thoneyvazul@916
   330
    template <class T>
thoneyvazul@916
   331
    struct SetProcessedMap 
thoneyvazul@916
   332
      : public MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   333
                                    DefProcessedMapTraits<T> > { 
thoneyvazul@916
   334
      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   335
                                   DefProcessedMapTraits<T> > Create;
thoneyvazul@916
   336
    };
thoneyvazul@916
   337
    
thoneyvazul@916
   338
    template <class H, class CR>
thoneyvazul@916
   339
    struct DefHeapTraits : public Traits {
thoneyvazul@916
   340
      typedef CR HeapCrossRef;
thoneyvazul@916
   341
      typedef H Heap;
thoneyvazul@916
   342
      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
thoneyvazul@916
   343
     	LEMON_ASSERT(false,"Uninitialized parameter.");
thoneyvazul@916
   344
	return 0;
thoneyvazul@916
   345
      }
thoneyvazul@916
   346
      static Heap *createHeap(HeapCrossRef &) {
thoneyvazul@916
   347
       	LEMON_ASSERT(false,"Uninitialized parameter.");
thoneyvazul@916
   348
	return 0;
thoneyvazul@916
   349
      }
thoneyvazul@916
   350
    };
thoneyvazul@916
   351
    /// \brief \ref named-templ-param "Named parameter" for setting heap 
thoneyvazul@916
   352
    /// and cross reference type
thoneyvazul@916
   353
    ///
thoneyvazul@916
   354
    /// \ref named-templ-param "Named parameter" for setting heap and cross 
thoneyvazul@916
   355
    /// reference type for the algorithm.
thoneyvazul@916
   356
    template <class H, class CR = typename Digraph::template NodeMap<int> >
thoneyvazul@916
   357
    struct SetHeap
thoneyvazul@916
   358
      : public MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   359
                                    DefHeapTraits<H, CR> > { 
thoneyvazul@916
   360
      typedef MaxCardinalitySearch< Digraph, CapacityMap, 
thoneyvazul@916
   361
                                    DefHeapTraits<H, CR> > Create;
thoneyvazul@916
   362
    };
thoneyvazul@916
   363
thoneyvazul@916
   364
    template <class H, class CR>
thoneyvazul@916
   365
    struct DefStandardHeapTraits : public Traits {
thoneyvazul@916
   366
      typedef CR HeapCrossRef;
thoneyvazul@916
   367
      typedef H Heap;
thoneyvazul@916
   368
      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
thoneyvazul@916
   369
	return new HeapCrossRef(digraph);
thoneyvazul@916
   370
      }
thoneyvazul@916
   371
      static Heap *createHeap(HeapCrossRef &crossref) {
thoneyvazul@916
   372
	return new Heap(crossref);
thoneyvazul@916
   373
      }
thoneyvazul@916
   374
    };
thoneyvazul@916
   375
thoneyvazul@916
   376
    /// \brief \ref named-templ-param "Named parameter" for setting heap and 
thoneyvazul@916
   377
    /// cross reference type with automatic allocation
thoneyvazul@916
   378
    ///
thoneyvazul@916
   379
    /// \ref named-templ-param "Named parameter" for setting heap and cross 
thoneyvazul@916
   380
    /// reference type. It can allocate the heap and the cross reference 
thoneyvazul@916
   381
    /// object if the cross reference's constructor waits for the digraph as 
thoneyvazul@916
   382
    /// parameter and the heap's constructor waits for the cross reference.
thoneyvazul@916
   383
    template <class H, class CR = typename Digraph::template NodeMap<int> >
thoneyvazul@916
   384
    struct SetStandardHeap
thoneyvazul@916
   385
      : public MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   386
                                    DefStandardHeapTraits<H, CR> > { 
thoneyvazul@916
   387
      typedef MaxCardinalitySearch<Digraph, CapacityMap, 
thoneyvazul@916
   388
                                   DefStandardHeapTraits<H, CR> > 
thoneyvazul@916
   389
      Create;
thoneyvazul@916
   390
    };
thoneyvazul@916
   391
    
thoneyvazul@916
   392
    ///@}
thoneyvazul@916
   393
thoneyvazul@916
   394
thoneyvazul@916
   395
  protected:
thoneyvazul@916
   396
thoneyvazul@916
   397
    MaxCardinalitySearch() {}
thoneyvazul@916
   398
thoneyvazul@916
   399
  public:      
thoneyvazul@916
   400
    
thoneyvazul@916
   401
    /// \brief Constructor.
thoneyvazul@916
   402
    ///
thoneyvazul@916
   403
    ///\param digraph the digraph the algorithm will run on.
thoneyvazul@916
   404
    ///\param capacity the capacity map used by the algorithm.
thoneyvazul@916
   405
    MaxCardinalitySearch(const Digraph& digraph,
alpar@977
   406
			 const CapacityMap& capacity) :
thoneyvazul@916
   407
      _graph(&digraph),
thoneyvazul@916
   408
      _capacity(&capacity), local_capacity(false),
thoneyvazul@916
   409
      _cardinality(0), local_cardinality(false),
thoneyvazul@916
   410
      _processed(0), local_processed(false),
thoneyvazul@916
   411
      _heap_cross_ref(0), local_heap_cross_ref(false),
thoneyvazul@916
   412
      _heap(0), local_heap(false)
thoneyvazul@916
   413
    { }
thoneyvazul@916
   414
alpar@977
   415
    /// \brief Constructor.
alpar@977
   416
    ///
alpar@977
   417
    ///\param digraph the digraph the algorithm will run on.
alpar@977
   418
    ///
alpar@977
   419
    ///A constant 1 capacity map will be allocated.
alpar@977
   420
    MaxCardinalitySearch(const Digraph& digraph) :
alpar@977
   421
      _graph(&digraph),
alpar@977
   422
      _capacity(0), local_capacity(false),
alpar@977
   423
      _cardinality(0), local_cardinality(false),
alpar@977
   424
      _processed(0), local_processed(false),
alpar@977
   425
      _heap_cross_ref(0), local_heap_cross_ref(false),
alpar@977
   426
      _heap(0), local_heap(false)
alpar@977
   427
    { }
alpar@977
   428
thoneyvazul@916
   429
    /// \brief Destructor.
thoneyvazul@916
   430
    ~MaxCardinalitySearch() {
thoneyvazul@916
   431
      if(local_capacity) delete _capacity;
thoneyvazul@916
   432
      if(local_cardinality) delete _cardinality;
thoneyvazul@916
   433
      if(local_processed) delete _processed;
thoneyvazul@916
   434
      if(local_heap_cross_ref) delete _heap_cross_ref;
thoneyvazul@916
   435
      if(local_heap) delete _heap;
thoneyvazul@916
   436
    }
thoneyvazul@916
   437
thoneyvazul@916
   438
    /// \brief Sets the capacity map.
thoneyvazul@916
   439
    ///
thoneyvazul@916
   440
    /// Sets the capacity map.
thoneyvazul@916
   441
    /// \return <tt> (*this) </tt>
thoneyvazul@916
   442
    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
thoneyvazul@916
   443
      if (local_capacity) {
thoneyvazul@916
   444
	delete _capacity;
thoneyvazul@916
   445
	local_capacity=false;
thoneyvazul@916
   446
      }
thoneyvazul@916
   447
      _capacity=&m;
thoneyvazul@916
   448
      return *this;
thoneyvazul@916
   449
    }
thoneyvazul@916
   450
thoneyvazul@916
   451
    /// \brief Returns a const reference to the capacity map.
thoneyvazul@916
   452
    ///
thoneyvazul@916
   453
    /// Returns a const reference to the capacity map used by
thoneyvazul@916
   454
    /// the algorithm.
thoneyvazul@916
   455
    const CapacityMap &capacityMap() const {
thoneyvazul@916
   456
      return *_capacity;
thoneyvazul@916
   457
    }
thoneyvazul@916
   458
thoneyvazul@916
   459
    /// \brief Sets the map storing the cardinalities calculated by the 
thoneyvazul@916
   460
    /// algorithm.
thoneyvazul@916
   461
    ///
thoneyvazul@916
   462
    /// Sets the map storing the cardinalities calculated by the algorithm.
thoneyvazul@916
   463
    /// If you don't use this function before calling \ref run(),
thoneyvazul@916
   464
    /// it will allocate one. The destuctor deallocates this
thoneyvazul@916
   465
    /// automatically allocated map, of course.
thoneyvazul@916
   466
    /// \return <tt> (*this) </tt>
thoneyvazul@916
   467
    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
thoneyvazul@916
   468
      if(local_cardinality) {
thoneyvazul@916
   469
	delete _cardinality;
thoneyvazul@916
   470
	local_cardinality=false;
thoneyvazul@916
   471
      }
thoneyvazul@916
   472
      _cardinality = &m;
thoneyvazul@916
   473
      return *this;
thoneyvazul@916
   474
    }
thoneyvazul@916
   475
thoneyvazul@916
   476
    /// \brief Sets the map storing the processed nodes.
thoneyvazul@916
   477
    ///
thoneyvazul@916
   478
    /// Sets the map storing the processed nodes.
thoneyvazul@916
   479
    /// If you don't use this function before calling \ref run(),
thoneyvazul@916
   480
    /// it will allocate one. The destuctor deallocates this
thoneyvazul@916
   481
    /// automatically allocated map, of course.
thoneyvazul@916
   482
    /// \return <tt> (*this) </tt>
thoneyvazul@916
   483
    MaxCardinalitySearch &processedMap(ProcessedMap &m) 
thoneyvazul@916
   484
    {
thoneyvazul@916
   485
      if(local_processed) {
thoneyvazul@916
   486
	delete _processed;
thoneyvazul@916
   487
	local_processed=false;
thoneyvazul@916
   488
      }
thoneyvazul@916
   489
      _processed = &m;
thoneyvazul@916
   490
      return *this;
thoneyvazul@916
   491
    }
thoneyvazul@916
   492
thoneyvazul@916
   493
    /// \brief Returns a const reference to the cardinality map.
thoneyvazul@916
   494
    ///
thoneyvazul@916
   495
    /// Returns a const reference to the cardinality map used by
thoneyvazul@916
   496
    /// the algorithm.
thoneyvazul@916
   497
    const ProcessedMap &processedMap() const {
thoneyvazul@916
   498
      return *_processed;
thoneyvazul@916
   499
    }
thoneyvazul@916
   500
thoneyvazul@916
   501
    /// \brief Sets the heap and the cross reference used by algorithm.
thoneyvazul@916
   502
    ///
thoneyvazul@916
   503
    /// Sets the heap and the cross reference used by algorithm.
thoneyvazul@916
   504
    /// If you don't use this function before calling \ref run(),
thoneyvazul@916
   505
    /// it will allocate one. The destuctor deallocates this
thoneyvazul@916
   506
    /// automatically allocated map, of course.
thoneyvazul@916
   507
    /// \return <tt> (*this) </tt>
thoneyvazul@916
   508
    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
thoneyvazul@916
   509
      if(local_heap_cross_ref) {
thoneyvazul@916
   510
	delete _heap_cross_ref;
thoneyvazul@916
   511
	local_heap_cross_ref = false;
thoneyvazul@916
   512
      }
thoneyvazul@916
   513
      _heap_cross_ref = &cr;
thoneyvazul@916
   514
      if(local_heap) {
thoneyvazul@916
   515
	delete _heap;
thoneyvazul@916
   516
	local_heap = false;
thoneyvazul@916
   517
      }
thoneyvazul@916
   518
      _heap = &hp;
thoneyvazul@916
   519
      return *this;
thoneyvazul@916
   520
    }
thoneyvazul@916
   521
thoneyvazul@916
   522
    /// \brief Returns a const reference to the heap.
thoneyvazul@916
   523
    ///
thoneyvazul@916
   524
    /// Returns a const reference to the heap used by
thoneyvazul@916
   525
    /// the algorithm.
thoneyvazul@916
   526
    const Heap &heap() const {
thoneyvazul@916
   527
      return *_heap;
thoneyvazul@916
   528
    }
thoneyvazul@916
   529
thoneyvazul@916
   530
    /// \brief Returns a const reference to the cross reference.
thoneyvazul@916
   531
    ///
thoneyvazul@916
   532
    /// Returns a const reference to the cross reference
thoneyvazul@916
   533
    /// of the heap.
thoneyvazul@916
   534
    const HeapCrossRef &heapCrossRef() const {
thoneyvazul@916
   535
      return *_heap_cross_ref;
thoneyvazul@916
   536
    }
thoneyvazul@916
   537
thoneyvazul@916
   538
  private:
thoneyvazul@916
   539
thoneyvazul@916
   540
    typedef typename Digraph::Node Node;
thoneyvazul@916
   541
    typedef typename Digraph::NodeIt NodeIt;
thoneyvazul@916
   542
    typedef typename Digraph::Arc Arc;
thoneyvazul@916
   543
    typedef typename Digraph::InArcIt InArcIt;
thoneyvazul@916
   544
thoneyvazul@916
   545
    void create_maps() {
thoneyvazul@916
   546
      if(!_capacity) {
thoneyvazul@916
   547
	local_capacity = true;
thoneyvazul@916
   548
	_capacity = Traits::createCapacityMap(*_graph);
thoneyvazul@916
   549
      }
thoneyvazul@916
   550
      if(!_cardinality) {
thoneyvazul@916
   551
	local_cardinality = true;
thoneyvazul@916
   552
	_cardinality = Traits::createCardinalityMap(*_graph);
thoneyvazul@916
   553
      }
thoneyvazul@916
   554
      if(!_processed) {
thoneyvazul@916
   555
	local_processed = true;
thoneyvazul@916
   556
	_processed = Traits::createProcessedMap(*_graph);
thoneyvazul@916
   557
      }
thoneyvazul@916
   558
      if (!_heap_cross_ref) {
thoneyvazul@916
   559
	local_heap_cross_ref = true;
thoneyvazul@916
   560
	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);
thoneyvazul@916
   561
      }
thoneyvazul@916
   562
      if (!_heap) {
thoneyvazul@916
   563
	local_heap = true;
thoneyvazul@916
   564
	_heap = Traits::createHeap(*_heap_cross_ref);
thoneyvazul@916
   565
      }
thoneyvazul@916
   566
    }
thoneyvazul@916
   567
    
thoneyvazul@916
   568
    void finalizeNodeData(Node node, Value capacity) {
thoneyvazul@916
   569
      _processed->set(node, true);
thoneyvazul@916
   570
      _cardinality->set(node, capacity);
thoneyvazul@916
   571
    }
thoneyvazul@916
   572
thoneyvazul@916
   573
  public:
thoneyvazul@916
   574
    /// \name Execution control
thoneyvazul@916
   575
    /// The simplest way to execute the algorithm is to use
thoneyvazul@916
   576
    /// one of the member functions called \ref run().
thoneyvazul@916
   577
    /// \n
thoneyvazul@916
   578
    /// If you need more control on the execution,
thoneyvazul@916
   579
    /// first you must call \ref init(), then you can add several source nodes
thoneyvazul@916
   580
    /// with \ref addSource().
thoneyvazul@916
   581
    /// Finally \ref start() will perform the computation.
thoneyvazul@916
   582
thoneyvazul@916
   583
    ///@{
thoneyvazul@916
   584
thoneyvazul@916
   585
    /// \brief Initializes the internal data structures.
thoneyvazul@916
   586
    ///
thoneyvazul@916
   587
    /// Initializes the internal data structures, and clears the heap.
thoneyvazul@916
   588
    void init() {
thoneyvazul@916
   589
      create_maps();
thoneyvazul@916
   590
      _heap->clear();
thoneyvazul@916
   591
      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
thoneyvazul@916
   592
	_processed->set(it, false);
thoneyvazul@916
   593
	_heap_cross_ref->set(it, Heap::PRE_HEAP);
thoneyvazul@916
   594
      }
thoneyvazul@916
   595
    }
thoneyvazul@916
   596
    
thoneyvazul@916
   597
    /// \brief Adds a new source node.
thoneyvazul@916
   598
    /// 
thoneyvazul@916
   599
    /// Adds a new source node to the priority heap.
thoneyvazul@916
   600
    ///
thoneyvazul@916
   601
    /// It checks if the node has not yet been added to the heap.
thoneyvazul@916
   602
    void addSource(Node source, Value capacity = 0) {
thoneyvazul@916
   603
      if(_heap->state(source) == Heap::PRE_HEAP) {
thoneyvazul@916
   604
	_heap->push(source, capacity);
thoneyvazul@916
   605
      } 
thoneyvazul@916
   606
    }
thoneyvazul@916
   607
    
thoneyvazul@916
   608
    /// \brief Processes the next node in the priority heap
thoneyvazul@916
   609
    ///
thoneyvazul@916
   610
    /// Processes the next node in the priority heap.
thoneyvazul@916
   611
    ///
thoneyvazul@916
   612
    /// \return The processed node.
thoneyvazul@916
   613
    ///
thoneyvazul@916
   614
    /// \warning The priority heap must not be empty!
thoneyvazul@916
   615
    Node processNextNode() {
thoneyvazul@916
   616
      Node node = _heap->top(); 
thoneyvazul@916
   617
      finalizeNodeData(node, _heap->prio());
thoneyvazul@916
   618
      _heap->pop();
thoneyvazul@916
   619
      
thoneyvazul@916
   620
      for (InArcIt it(*_graph, node); it != INVALID; ++it) {
thoneyvazul@916
   621
	Node source = _graph->source(it);
thoneyvazul@916
   622
	switch (_heap->state(source)) {
thoneyvazul@916
   623
	case Heap::PRE_HEAP:
thoneyvazul@916
   624
	  _heap->push(source, (*_capacity)[it]);
thoneyvazul@916
   625
	  break;
thoneyvazul@916
   626
	case Heap::IN_HEAP:
thoneyvazul@916
   627
	  _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
thoneyvazul@916
   628
	  break;
thoneyvazul@916
   629
	case Heap::POST_HEAP:
thoneyvazul@916
   630
	  break;
thoneyvazul@916
   631
	}
thoneyvazul@916
   632
      }
thoneyvazul@916
   633
      return node;
thoneyvazul@916
   634
    }
thoneyvazul@916
   635
thoneyvazul@916
   636
    /// \brief Next node to be processed.
thoneyvazul@916
   637
    ///
thoneyvazul@916
   638
    /// Next node to be processed.
thoneyvazul@916
   639
    ///
thoneyvazul@916
   640
    /// \return The next node to be processed or INVALID if the 
thoneyvazul@916
   641
    /// priority heap is empty.
thoneyvazul@916
   642
    Node nextNode() { 
thoneyvazul@916
   643
      return !_heap->empty() ? _heap->top() : INVALID;
thoneyvazul@916
   644
    }
thoneyvazul@916
   645
 
thoneyvazul@916
   646
    /// \brief Returns \c false if there are nodes
thoneyvazul@916
   647
    /// to be processed in the priority heap
thoneyvazul@916
   648
    ///
thoneyvazul@916
   649
    /// Returns \c false if there are nodes
thoneyvazul@916
   650
    /// to be processed in the priority heap
thoneyvazul@916
   651
    bool emptyQueue() { return _heap->empty(); }
thoneyvazul@916
   652
    /// \brief Returns the number of the nodes to be processed 
thoneyvazul@916
   653
    /// in the priority heap
thoneyvazul@916
   654
    ///
thoneyvazul@916
   655
    /// Returns the number of the nodes to be processed in the priority heap
thoneyvazul@916
   656
    int emptySize() { return _heap->size(); }
thoneyvazul@916
   657
    
thoneyvazul@916
   658
    /// \brief Executes the algorithm.
thoneyvazul@916
   659
    ///
thoneyvazul@916
   660
    /// Executes the algorithm.
thoneyvazul@916
   661
    ///
thoneyvazul@916
   662
    ///\pre init() must be called and at least one node should be added
thoneyvazul@916
   663
    /// with addSource() before using this function.
thoneyvazul@916
   664
    ///
thoneyvazul@916
   665
    /// This method runs the Maximum Cardinality Search algorithm from the 
thoneyvazul@916
   666
    /// source node(s).
thoneyvazul@916
   667
    void start() {
thoneyvazul@916
   668
      while ( !_heap->empty() ) processNextNode();
thoneyvazul@916
   669
    }
thoneyvazul@916
   670
    
thoneyvazul@916
   671
    /// \brief Executes the algorithm until \c dest is reached.
thoneyvazul@916
   672
    ///
thoneyvazul@916
   673
    /// Executes the algorithm until \c dest is reached.
thoneyvazul@916
   674
    ///
thoneyvazul@916
   675
    /// \pre init() must be called and at least one node should be added
thoneyvazul@916
   676
    /// with addSource() before using this function.
thoneyvazul@916
   677
    ///
thoneyvazul@916
   678
    /// This method runs the %MaxCardinalitySearch algorithm from the source 
thoneyvazul@916
   679
    /// nodes.
thoneyvazul@916
   680
    void start(Node dest) {
thoneyvazul@916
   681
      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
thoneyvazul@916
   682
      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
thoneyvazul@916
   683
    }
thoneyvazul@916
   684
    
thoneyvazul@916
   685
    /// \brief Executes the algorithm until a condition is met.
thoneyvazul@916
   686
    ///
thoneyvazul@916
   687
    /// Executes the algorithm until a condition is met.
thoneyvazul@916
   688
    ///
thoneyvazul@916
   689
    /// \pre init() must be called and at least one node should be added
thoneyvazul@916
   690
    /// with addSource() before using this function.
thoneyvazul@916
   691
    ///
thoneyvazul@916
   692
    /// \param nm must be a bool (or convertible) node map. The algorithm
thoneyvazul@916
   693
    /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
thoneyvazul@916
   694
    template <typename NodeBoolMap>
thoneyvazul@916
   695
    void start(const NodeBoolMap &nm) {
thoneyvazul@916
   696
      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
thoneyvazul@916
   697
      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
thoneyvazul@916
   698
    }
thoneyvazul@916
   699
    
thoneyvazul@916
   700
    /// \brief Runs the maximum cardinality search algorithm from node \c s.
thoneyvazul@916
   701
    ///
thoneyvazul@916
   702
    /// This method runs the %MaxCardinalitySearch algorithm from a root 
thoneyvazul@916
   703
    /// node \c s.
thoneyvazul@916
   704
    ///
thoneyvazul@916
   705
    ///\note d.run(s) is just a shortcut of the following code.
thoneyvazul@916
   706
    ///\code
thoneyvazul@916
   707
    ///  d.init();
thoneyvazul@916
   708
    ///  d.addSource(s);
thoneyvazul@916
   709
    ///  d.start();
thoneyvazul@916
   710
    ///\endcode
thoneyvazul@916
   711
    void run(Node s) {
thoneyvazul@916
   712
      init();
thoneyvazul@916
   713
      addSource(s);
thoneyvazul@916
   714
      start();
thoneyvazul@916
   715
    }
thoneyvazul@916
   716
thoneyvazul@916
   717
    /// \brief Runs the maximum cardinality search algorithm for the 
thoneyvazul@916
   718
    /// whole digraph.
thoneyvazul@916
   719
    ///
thoneyvazul@916
   720
    /// This method runs the %MaxCardinalitySearch algorithm from all 
thoneyvazul@916
   721
    /// unprocessed node of the digraph.
thoneyvazul@916
   722
    ///
thoneyvazul@916
   723
    ///\note d.run(s) is just a shortcut of the following code.
thoneyvazul@916
   724
    ///\code
thoneyvazul@916
   725
    ///  d.init();
thoneyvazul@916
   726
    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
thoneyvazul@916
   727
    ///    if (!d.reached(it)) {
thoneyvazul@916
   728
    ///      d.addSource(s);
thoneyvazul@916
   729
    ///      d.start();
thoneyvazul@916
   730
    ///    }
thoneyvazul@916
   731
    ///  }
thoneyvazul@916
   732
    ///\endcode
thoneyvazul@916
   733
    void run() {
thoneyvazul@916
   734
      init();
thoneyvazul@916
   735
      for (NodeIt it(*_graph); it != INVALID; ++it) {
thoneyvazul@916
   736
        if (!reached(it)) {
thoneyvazul@916
   737
          addSource(it);
thoneyvazul@916
   738
          start();
thoneyvazul@916
   739
        }
thoneyvazul@916
   740
      }
thoneyvazul@916
   741
    }
thoneyvazul@916
   742
    
thoneyvazul@916
   743
    ///@}
thoneyvazul@916
   744
thoneyvazul@916
   745
    /// \name Query Functions
thoneyvazul@916
   746
    /// The results of the maximum cardinality search algorithm can be 
thoneyvazul@916
   747
    /// obtained using these functions.
thoneyvazul@916
   748
    /// \n
thoneyvazul@916
   749
    /// Before the use of these functions, either run() or start() must be 
thoneyvazul@916
   750
    /// called.
thoneyvazul@916
   751
    
thoneyvazul@916
   752
    ///@{
thoneyvazul@916
   753
thoneyvazul@916
   754
    /// \brief The cardinality of a node.
thoneyvazul@916
   755
    ///
thoneyvazul@916
   756
    /// Returns the cardinality of a node.
thoneyvazul@916
   757
    /// \pre \ref run() must be called before using this function.
thoneyvazul@916
   758
    /// \warning If node \c v in unreachable from the root the return value
thoneyvazul@916
   759
    /// of this funcion is undefined.
thoneyvazul@916
   760
    Value cardinality(Node node) const { return (*_cardinality)[node]; }
thoneyvazul@916
   761
thoneyvazul@916
   762
    /// \brief The current cardinality of a node.
thoneyvazul@916
   763
    ///
thoneyvazul@916
   764
    /// Returns the current cardinality of a node.
thoneyvazul@916
   765
    /// \pre the given node should be reached but not processed
thoneyvazul@916
   766
    Value currentCardinality(Node node) const { return (*_heap)[node]; }
thoneyvazul@916
   767
thoneyvazul@916
   768
    /// \brief Returns a reference to the NodeMap of cardinalities.
thoneyvazul@916
   769
    ///
thoneyvazul@916
   770
    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
thoneyvazul@916
   771
    /// must be called before using this function.
thoneyvazul@916
   772
    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
thoneyvazul@916
   773
 
thoneyvazul@916
   774
    /// \brief Checks if a node is reachable from the root.
thoneyvazul@916
   775
    ///
thoneyvazul@916
   776
    /// Returns \c true if \c v is reachable from the root.
thoneyvazul@916
   777
    /// \warning The source nodes are initated as unreached.
thoneyvazul@916
   778
    /// \pre \ref run() must be called before using this function.
thoneyvazul@916
   779
    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
thoneyvazul@916
   780
thoneyvazul@916
   781
    /// \brief Checks if a node is processed.
thoneyvazul@916
   782
    ///
thoneyvazul@916
   783
    /// Returns \c true if \c v is processed, i.e. the shortest
thoneyvazul@916
   784
    /// path to \c v has already found.
thoneyvazul@916
   785
    /// \pre \ref run() must be called before using this function.
thoneyvazul@916
   786
    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
thoneyvazul@916
   787
    
thoneyvazul@916
   788
    ///@}
thoneyvazul@916
   789
  };
thoneyvazul@916
   790
thoneyvazul@916
   791
}
thoneyvazul@916
   792
thoneyvazul@916
   793
#endif