Port max. card. search alg. from svn -r3512 (#397) and (#56)
1.1 --- a/lemon/Makefile.am Wed Sep 22 09:38:23 2010 +0200
1.2 +++ b/lemon/Makefile.am Mon Nov 15 22:23:35 2010 +0100
1.3 @@ -107,6 +107,7 @@
1.4 lemon/matching.h \
1.5 lemon/math.h \
1.6 lemon/min_cost_arborescence.h \
1.7 + lemon/max_cardinality_search.h \
1.8 lemon/nauty_reader.h \
1.9 lemon/network_simplex.h \
1.10 lemon/pairing_heap.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/max_cardinality_search.h Mon Nov 15 22:23:35 2010 +0100
2.3 @@ -0,0 +1,786 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2010
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_MAX_CARDINALITY_SEARCH_H
2.23 +#define LEMON_MAX_CARDINALITY_SEARCH_H
2.24 +
2.25 +
2.26 +/// \ingroup search
2.27 +/// \file
2.28 +/// \brief Maximum cardinality search in undirected digraphs.
2.29 +
2.30 +#include <lemon/bin_heap.h>
2.31 +#include <lemon/bucket_heap.h>
2.32 +
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 + /// \brief Default traits class of MaxCardinalitySearch class.
2.41 + ///
2.42 + /// Default traits class of MaxCardinalitySearch class.
2.43 + /// \param Digraph Digraph type.
2.44 + /// \param CapacityMap Type of capacity map.
2.45 + template <typename GR, typename CAP>
2.46 + struct MaxCardinalitySearchDefaultTraits {
2.47 + /// The digraph type the algorithm runs on.
2.48 + typedef GR Digraph;
2.49 +
2.50 + template <typename CM>
2.51 + struct CapMapSelector {
2.52 +
2.53 + typedef CM CapacityMap;
2.54 +
2.55 + static CapacityMap *createCapacityMap(const Digraph& g) {
2.56 + return new CapacityMap(g);
2.57 + }
2.58 + };
2.59 +
2.60 + template <typename CM>
2.61 + struct CapMapSelector<ConstMap<CM, Const<int, 1> > > {
2.62 +
2.63 + typedef ConstMap<CM, Const<int, 1> > CapacityMap;
2.64 +
2.65 + static CapacityMap *createCapacityMap(const Digraph&) {
2.66 + return new CapacityMap;
2.67 + }
2.68 + };
2.69 +
2.70 + /// \brief The type of the map that stores the arc capacities.
2.71 + ///
2.72 + /// The type of the map that stores the arc capacities.
2.73 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
2.74 + typedef typename CapMapSelector<CAP>::CapacityMap CapacityMap;
2.75 +
2.76 + /// \brief The type of the capacity of the arcs.
2.77 + typedef typename CapacityMap::Value Value;
2.78 +
2.79 + /// \brief Instantiates a CapacityMap.
2.80 + ///
2.81 + /// This function instantiates a \ref CapacityMap.
2.82 + /// \param digraph is the digraph, to which we would like to define
2.83 + /// the CapacityMap.
2.84 + static CapacityMap *createCapacityMap(const Digraph& digraph) {
2.85 + return CapMapSelector<CapacityMap>::createCapacityMap(digraph);
2.86 + }
2.87 +
2.88 + /// \brief The cross reference type used by heap.
2.89 + ///
2.90 + /// The cross reference type used by heap.
2.91 + /// Usually it is \c Digraph::NodeMap<int>.
2.92 + typedef typename Digraph::template NodeMap<int> HeapCrossRef;
2.93 +
2.94 + /// \brief Instantiates a HeapCrossRef.
2.95 + ///
2.96 + /// This function instantiates a \ref HeapCrossRef.
2.97 + /// \param digraph is the digraph, to which we would like to define the
2.98 + /// HeapCrossRef.
2.99 + static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
2.100 + return new HeapCrossRef(digraph);
2.101 + }
2.102 +
2.103 + template <typename CapacityMap>
2.104 + struct HeapSelector {
2.105 + template <typename Value, typename Ref>
2.106 + struct Selector {
2.107 + typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
2.108 + };
2.109 + };
2.110 +
2.111 + template <typename CapacityKey>
2.112 + struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
2.113 + template <typename Value, typename Ref>
2.114 + struct Selector {
2.115 + typedef BucketHeap<Ref, false > Heap;
2.116 + };
2.117 + };
2.118 +
2.119 + /// \brief The heap type used by MaxCardinalitySearch algorithm.
2.120 + ///
2.121 + /// The heap type used by MaxCardinalitySearch algorithm. It should
2.122 + /// maximalize the priorities. The default heap type is
2.123 + /// the \ref BinHeap, but it is specialized when the
2.124 + /// CapacityMap is ConstMap<Digraph::Node, Const<int, 1> >
2.125 + /// to BucketHeap.
2.126 + ///
2.127 + /// \sa MaxCardinalitySearch
2.128 + typedef typename HeapSelector<CapacityMap>
2.129 + ::template Selector<Value, HeapCrossRef>
2.130 + ::Heap Heap;
2.131 +
2.132 + /// \brief Instantiates a Heap.
2.133 + ///
2.134 + /// This function instantiates a \ref Heap.
2.135 + /// \param crossref The cross reference of the heap.
2.136 + static Heap *createHeap(HeapCrossRef& crossref) {
2.137 + return new Heap(crossref);
2.138 + }
2.139 +
2.140 + /// \brief The type of the map that stores whether a node is processed.
2.141 + ///
2.142 + /// The type of the map that stores whether a node is processed.
2.143 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.144 + /// By default it is a NullMap.
2.145 + typedef NullMap<typename Digraph::Node, bool> ProcessedMap;
2.146 +
2.147 + /// \brief Instantiates a ProcessedMap.
2.148 + ///
2.149 + /// This function instantiates a \ref ProcessedMap.
2.150 + /// \param digraph is the digraph, to which
2.151 + /// we would like to define the \ref ProcessedMap
2.152 +#ifdef DOXYGEN
2.153 + static ProcessedMap *createProcessedMap(const Digraph &digraph)
2.154 +#else
2.155 + static ProcessedMap *createProcessedMap(const Digraph &)
2.156 +#endif
2.157 + {
2.158 + return new ProcessedMap();
2.159 + }
2.160 +
2.161 + /// \brief The type of the map that stores the cardinalities of the nodes.
2.162 + ///
2.163 + /// The type of the map that stores the cardinalities of the nodes.
2.164 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.165 + typedef typename Digraph::template NodeMap<Value> CardinalityMap;
2.166 +
2.167 + /// \brief Instantiates a CardinalityMap.
2.168 + ///
2.169 + /// This function instantiates a \ref CardinalityMap.
2.170 + /// \param digraph is the digraph, to which we would like to define the \ref
2.171 + /// CardinalityMap
2.172 + static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
2.173 + return new CardinalityMap(digraph);
2.174 + }
2.175 +
2.176 +
2.177 + };
2.178 +
2.179 + /// \ingroup search
2.180 + ///
2.181 + /// \brief Maximum Cardinality Search algorithm class.
2.182 + ///
2.183 + /// This class provides an efficient implementation of Maximum Cardinality
2.184 + /// Search algorithm. The maximum cardinality search first chooses any
2.185 + /// node of the digraph. Then every time it chooses one unprocessed node
2.186 + /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
2.187 + /// which were previusly processed.
2.188 + /// If there is a cut in the digraph the algorithm should choose
2.189 + /// again any unprocessed node of the digraph.
2.190 +
2.191 + /// The arc capacities are passed to the algorithm using a
2.192 + /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
2.193 + /// kind of capacity.
2.194 + ///
2.195 + /// The type of the capacity is determined by the \ref
2.196 + /// concepts::ReadMap::Value "Value" of the capacity map.
2.197 + ///
2.198 + /// It is also possible to change the underlying priority heap.
2.199 + ///
2.200 + ///
2.201 + /// \param GR The digraph type the algorithm runs on. The value of
2.202 + /// Digraph is not used directly by the search algorithm, it
2.203 + /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
2.204 + /// \param CAP This read-only ArcMap determines the capacities of
2.205 + /// the arcs. It is read once for each arc, so the map may involve in
2.206 + /// relatively time consuming process to compute the arc capacity if
2.207 + /// it is necessary. The default map type is \ref
2.208 + /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
2.209 + /// of CapacityMap is not used directly by search algorithm, it is only
2.210 + /// passed to \ref MaxCardinalitySearchDefaultTraits.
2.211 + /// \param TR Traits class to set various data types used by the
2.212 + /// algorithm. The default traits class is
2.213 + /// \ref MaxCardinalitySearchDefaultTraits
2.214 + /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".
2.215 + /// See \ref MaxCardinalitySearchDefaultTraits
2.216 + /// for the documentation of a MaxCardinalitySearch traits class.
2.217 +
2.218 +#ifdef DOXYGEN
2.219 + template <typename GR, typename CAP, typename TR>
2.220 +#else
2.221 + template <typename GR, typename CAP =
2.222 + ConstMap<typename GR::Arc, Const<int,1> >,
2.223 + typename TR =
2.224 + MaxCardinalitySearchDefaultTraits<GR, CAP> >
2.225 +#endif
2.226 + class MaxCardinalitySearch {
2.227 + public:
2.228 +
2.229 + typedef TR Traits;
2.230 + ///The type of the underlying digraph.
2.231 + typedef typename Traits::Digraph Digraph;
2.232 +
2.233 + ///The type of the capacity of the arcs.
2.234 + typedef typename Traits::CapacityMap::Value Value;
2.235 + ///The type of the map that stores the arc capacities.
2.236 + typedef typename Traits::CapacityMap CapacityMap;
2.237 + ///The type of the map indicating if a node is processed.
2.238 + typedef typename Traits::ProcessedMap ProcessedMap;
2.239 + ///The type of the map that stores the cardinalities of the nodes.
2.240 + typedef typename Traits::CardinalityMap CardinalityMap;
2.241 + ///The cross reference type used for the current heap.
2.242 + typedef typename Traits::HeapCrossRef HeapCrossRef;
2.243 + ///The heap type used by the algorithm. It maximizes the priorities.
2.244 + typedef typename Traits::Heap Heap;
2.245 + private:
2.246 + // Pointer to the underlying digraph.
2.247 + const Digraph *_graph;
2.248 + // Pointer to the capacity map
2.249 + const CapacityMap *_capacity;
2.250 + // Indicates if \ref _capacity is locally allocated (\c true) or not.
2.251 + bool local_capacity;
2.252 + // Pointer to the map of cardinality.
2.253 + CardinalityMap *_cardinality;
2.254 + // Indicates if \ref _cardinality is locally allocated (\c true) or not.
2.255 + bool local_cardinality;
2.256 + // Pointer to the map of processed status of the nodes.
2.257 + ProcessedMap *_processed;
2.258 + // Indicates if \ref _processed is locally allocated (\c true) or not.
2.259 + bool local_processed;
2.260 + // Pointer to the heap cross references.
2.261 + HeapCrossRef *_heap_cross_ref;
2.262 + // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
2.263 + bool local_heap_cross_ref;
2.264 + // Pointer to the heap.
2.265 + Heap *_heap;
2.266 + // Indicates if \ref _heap is locally allocated (\c true) or not.
2.267 + bool local_heap;
2.268 +
2.269 + public :
2.270 +
2.271 + typedef MaxCardinalitySearch Create;
2.272 +
2.273 + ///\name Named template parameters
2.274 +
2.275 + ///@{
2.276 +
2.277 + template <class T>
2.278 + struct DefCapacityMapTraits : public Traits {
2.279 + typedef T CapacityMap;
2.280 + static CapacityMap *createCapacityMap(const Digraph &) {
2.281 + LEMON_ASSERT(false,"Uninitialized parameter.");
2.282 + return 0;
2.283 + }
2.284 + };
2.285 + /// \brief \ref named-templ-param "Named parameter" for setting
2.286 + /// CapacityMap type
2.287 + ///
2.288 + /// \ref named-templ-param "Named parameter" for setting CapacityMap type
2.289 + /// for the algorithm.
2.290 + template <class T>
2.291 + struct SetCapacityMap
2.292 + : public MaxCardinalitySearch<Digraph, CapacityMap,
2.293 + DefCapacityMapTraits<T> > {
2.294 + typedef MaxCardinalitySearch<Digraph, CapacityMap,
2.295 + DefCapacityMapTraits<T> > Create;
2.296 + };
2.297 +
2.298 + template <class T>
2.299 + struct DefCardinalityMapTraits : public Traits {
2.300 + typedef T CardinalityMap;
2.301 + static CardinalityMap *createCardinalityMap(const Digraph &)
2.302 + {
2.303 + LEMON_ASSERT(false,"Uninitialized parameter.");
2.304 + return 0;
2.305 + }
2.306 + };
2.307 + /// \brief \ref named-templ-param "Named parameter" for setting
2.308 + /// CardinalityMap type
2.309 + ///
2.310 + /// \ref named-templ-param "Named parameter" for setting CardinalityMap
2.311 + /// type for the algorithm.
2.312 + template <class T>
2.313 + struct SetCardinalityMap
2.314 + : public MaxCardinalitySearch<Digraph, CapacityMap,
2.315 + DefCardinalityMapTraits<T> > {
2.316 + typedef MaxCardinalitySearch<Digraph, CapacityMap,
2.317 + DefCardinalityMapTraits<T> > Create;
2.318 + };
2.319 +
2.320 + template <class T>
2.321 + struct DefProcessedMapTraits : public Traits {
2.322 + typedef T ProcessedMap;
2.323 + static ProcessedMap *createProcessedMap(const Digraph &) {
2.324 + LEMON_ASSERT(false,"Uninitialized parameter.");
2.325 + return 0;
2.326 + }
2.327 + };
2.328 + /// \brief \ref named-templ-param "Named parameter" for setting
2.329 + /// ProcessedMap type
2.330 + ///
2.331 + /// \ref named-templ-param "Named parameter" for setting ProcessedMap type
2.332 + /// for the algorithm.
2.333 + template <class T>
2.334 + struct SetProcessedMap
2.335 + : public MaxCardinalitySearch<Digraph, CapacityMap,
2.336 + DefProcessedMapTraits<T> > {
2.337 + typedef MaxCardinalitySearch<Digraph, CapacityMap,
2.338 + DefProcessedMapTraits<T> > Create;
2.339 + };
2.340 +
2.341 + template <class H, class CR>
2.342 + struct DefHeapTraits : public Traits {
2.343 + typedef CR HeapCrossRef;
2.344 + typedef H Heap;
2.345 + static HeapCrossRef *createHeapCrossRef(const Digraph &) {
2.346 + LEMON_ASSERT(false,"Uninitialized parameter.");
2.347 + return 0;
2.348 + }
2.349 + static Heap *createHeap(HeapCrossRef &) {
2.350 + LEMON_ASSERT(false,"Uninitialized parameter.");
2.351 + return 0;
2.352 + }
2.353 + };
2.354 + /// \brief \ref named-templ-param "Named parameter" for setting heap
2.355 + /// and cross reference type
2.356 + ///
2.357 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.358 + /// reference type for the algorithm.
2.359 + template <class H, class CR = typename Digraph::template NodeMap<int> >
2.360 + struct SetHeap
2.361 + : public MaxCardinalitySearch<Digraph, CapacityMap,
2.362 + DefHeapTraits<H, CR> > {
2.363 + typedef MaxCardinalitySearch< Digraph, CapacityMap,
2.364 + DefHeapTraits<H, CR> > Create;
2.365 + };
2.366 +
2.367 + template <class H, class CR>
2.368 + struct DefStandardHeapTraits : public Traits {
2.369 + typedef CR HeapCrossRef;
2.370 + typedef H Heap;
2.371 + static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
2.372 + return new HeapCrossRef(digraph);
2.373 + }
2.374 + static Heap *createHeap(HeapCrossRef &crossref) {
2.375 + return new Heap(crossref);
2.376 + }
2.377 + };
2.378 +
2.379 + /// \brief \ref named-templ-param "Named parameter" for setting heap and
2.380 + /// cross reference type with automatic allocation
2.381 + ///
2.382 + /// \ref named-templ-param "Named parameter" for setting heap and cross
2.383 + /// reference type. It can allocate the heap and the cross reference
2.384 + /// object if the cross reference's constructor waits for the digraph as
2.385 + /// parameter and the heap's constructor waits for the cross reference.
2.386 + template <class H, class CR = typename Digraph::template NodeMap<int> >
2.387 + struct SetStandardHeap
2.388 + : public MaxCardinalitySearch<Digraph, CapacityMap,
2.389 + DefStandardHeapTraits<H, CR> > {
2.390 + typedef MaxCardinalitySearch<Digraph, CapacityMap,
2.391 + DefStandardHeapTraits<H, CR> >
2.392 + Create;
2.393 + };
2.394 +
2.395 + ///@}
2.396 +
2.397 +
2.398 + protected:
2.399 +
2.400 + MaxCardinalitySearch() {}
2.401 +
2.402 + public:
2.403 +
2.404 + /// \brief Constructor.
2.405 + ///
2.406 + ///\param digraph the digraph the algorithm will run on.
2.407 + ///\param capacity the capacity map used by the algorithm.
2.408 + ///When no capacity map given, a constant 1 capacity map will
2.409 + ///be allocated.
2.410 +#ifdef DOXYGEN
2.411 + MaxCardinalitySearch(const Digraph& digraph,
2.412 + const CapacityMap& capacity=0 ) :
2.413 +#else
2.414 + MaxCardinalitySearch(const Digraph& digraph,
2.415 + const CapacityMap& capacity=*static_cast<const CapacityMap*>(0) ) :
2.416 +#endif
2.417 + _graph(&digraph),
2.418 + _capacity(&capacity), local_capacity(false),
2.419 + _cardinality(0), local_cardinality(false),
2.420 + _processed(0), local_processed(false),
2.421 + _heap_cross_ref(0), local_heap_cross_ref(false),
2.422 + _heap(0), local_heap(false)
2.423 + { }
2.424 +
2.425 + /// \brief Destructor.
2.426 + ~MaxCardinalitySearch() {
2.427 + if(local_capacity) delete _capacity;
2.428 + if(local_cardinality) delete _cardinality;
2.429 + if(local_processed) delete _processed;
2.430 + if(local_heap_cross_ref) delete _heap_cross_ref;
2.431 + if(local_heap) delete _heap;
2.432 + }
2.433 +
2.434 + /// \brief Sets the capacity map.
2.435 + ///
2.436 + /// Sets the capacity map.
2.437 + /// \return <tt> (*this) </tt>
2.438 + MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
2.439 + if (local_capacity) {
2.440 + delete _capacity;
2.441 + local_capacity=false;
2.442 + }
2.443 + _capacity=&m;
2.444 + return *this;
2.445 + }
2.446 +
2.447 + /// \brief Returns a const reference to the capacity map.
2.448 + ///
2.449 + /// Returns a const reference to the capacity map used by
2.450 + /// the algorithm.
2.451 + const CapacityMap &capacityMap() const {
2.452 + return *_capacity;
2.453 + }
2.454 +
2.455 + /// \brief Sets the map storing the cardinalities calculated by the
2.456 + /// algorithm.
2.457 + ///
2.458 + /// Sets the map storing the cardinalities calculated by the algorithm.
2.459 + /// If you don't use this function before calling \ref run(),
2.460 + /// it will allocate one. The destuctor deallocates this
2.461 + /// automatically allocated map, of course.
2.462 + /// \return <tt> (*this) </tt>
2.463 + MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
2.464 + if(local_cardinality) {
2.465 + delete _cardinality;
2.466 + local_cardinality=false;
2.467 + }
2.468 + _cardinality = &m;
2.469 + return *this;
2.470 + }
2.471 +
2.472 + /// \brief Sets the map storing the processed nodes.
2.473 + ///
2.474 + /// Sets the map storing the processed nodes.
2.475 + /// If you don't use this function before calling \ref run(),
2.476 + /// it will allocate one. The destuctor deallocates this
2.477 + /// automatically allocated map, of course.
2.478 + /// \return <tt> (*this) </tt>
2.479 + MaxCardinalitySearch &processedMap(ProcessedMap &m)
2.480 + {
2.481 + if(local_processed) {
2.482 + delete _processed;
2.483 + local_processed=false;
2.484 + }
2.485 + _processed = &m;
2.486 + return *this;
2.487 + }
2.488 +
2.489 + /// \brief Returns a const reference to the cardinality map.
2.490 + ///
2.491 + /// Returns a const reference to the cardinality map used by
2.492 + /// the algorithm.
2.493 + const ProcessedMap &processedMap() const {
2.494 + return *_processed;
2.495 + }
2.496 +
2.497 + /// \brief Sets the heap and the cross reference used by algorithm.
2.498 + ///
2.499 + /// Sets the heap and the cross reference used by algorithm.
2.500 + /// If you don't use this function before calling \ref run(),
2.501 + /// it will allocate one. The destuctor deallocates this
2.502 + /// automatically allocated map, of course.
2.503 + /// \return <tt> (*this) </tt>
2.504 + MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
2.505 + if(local_heap_cross_ref) {
2.506 + delete _heap_cross_ref;
2.507 + local_heap_cross_ref = false;
2.508 + }
2.509 + _heap_cross_ref = &cr;
2.510 + if(local_heap) {
2.511 + delete _heap;
2.512 + local_heap = false;
2.513 + }
2.514 + _heap = &hp;
2.515 + return *this;
2.516 + }
2.517 +
2.518 + /// \brief Returns a const reference to the heap.
2.519 + ///
2.520 + /// Returns a const reference to the heap used by
2.521 + /// the algorithm.
2.522 + const Heap &heap() const {
2.523 + return *_heap;
2.524 + }
2.525 +
2.526 + /// \brief Returns a const reference to the cross reference.
2.527 + ///
2.528 + /// Returns a const reference to the cross reference
2.529 + /// of the heap.
2.530 + const HeapCrossRef &heapCrossRef() const {
2.531 + return *_heap_cross_ref;
2.532 + }
2.533 +
2.534 + private:
2.535 +
2.536 + typedef typename Digraph::Node Node;
2.537 + typedef typename Digraph::NodeIt NodeIt;
2.538 + typedef typename Digraph::Arc Arc;
2.539 + typedef typename Digraph::InArcIt InArcIt;
2.540 +
2.541 + void create_maps() {
2.542 + if(!_capacity) {
2.543 + local_capacity = true;
2.544 + _capacity = Traits::createCapacityMap(*_graph);
2.545 + }
2.546 + if(!_cardinality) {
2.547 + local_cardinality = true;
2.548 + _cardinality = Traits::createCardinalityMap(*_graph);
2.549 + }
2.550 + if(!_processed) {
2.551 + local_processed = true;
2.552 + _processed = Traits::createProcessedMap(*_graph);
2.553 + }
2.554 + if (!_heap_cross_ref) {
2.555 + local_heap_cross_ref = true;
2.556 + _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
2.557 + }
2.558 + if (!_heap) {
2.559 + local_heap = true;
2.560 + _heap = Traits::createHeap(*_heap_cross_ref);
2.561 + }
2.562 + }
2.563 +
2.564 + void finalizeNodeData(Node node, Value capacity) {
2.565 + _processed->set(node, true);
2.566 + _cardinality->set(node, capacity);
2.567 + }
2.568 +
2.569 + public:
2.570 + /// \name Execution control
2.571 + /// The simplest way to execute the algorithm is to use
2.572 + /// one of the member functions called \ref run().
2.573 + /// \n
2.574 + /// If you need more control on the execution,
2.575 + /// first you must call \ref init(), then you can add several source nodes
2.576 + /// with \ref addSource().
2.577 + /// Finally \ref start() will perform the computation.
2.578 +
2.579 + ///@{
2.580 +
2.581 + /// \brief Initializes the internal data structures.
2.582 + ///
2.583 + /// Initializes the internal data structures, and clears the heap.
2.584 + void init() {
2.585 + create_maps();
2.586 + _heap->clear();
2.587 + for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
2.588 + _processed->set(it, false);
2.589 + _heap_cross_ref->set(it, Heap::PRE_HEAP);
2.590 + }
2.591 + }
2.592 +
2.593 + /// \brief Adds a new source node.
2.594 + ///
2.595 + /// Adds a new source node to the priority heap.
2.596 + ///
2.597 + /// It checks if the node has not yet been added to the heap.
2.598 + void addSource(Node source, Value capacity = 0) {
2.599 + if(_heap->state(source) == Heap::PRE_HEAP) {
2.600 + _heap->push(source, capacity);
2.601 + }
2.602 + }
2.603 +
2.604 + /// \brief Processes the next node in the priority heap
2.605 + ///
2.606 + /// Processes the next node in the priority heap.
2.607 + ///
2.608 + /// \return The processed node.
2.609 + ///
2.610 + /// \warning The priority heap must not be empty!
2.611 + Node processNextNode() {
2.612 + Node node = _heap->top();
2.613 + finalizeNodeData(node, _heap->prio());
2.614 + _heap->pop();
2.615 +
2.616 + for (InArcIt it(*_graph, node); it != INVALID; ++it) {
2.617 + Node source = _graph->source(it);
2.618 + switch (_heap->state(source)) {
2.619 + case Heap::PRE_HEAP:
2.620 + _heap->push(source, (*_capacity)[it]);
2.621 + break;
2.622 + case Heap::IN_HEAP:
2.623 + _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
2.624 + break;
2.625 + case Heap::POST_HEAP:
2.626 + break;
2.627 + }
2.628 + }
2.629 + return node;
2.630 + }
2.631 +
2.632 + /// \brief Next node to be processed.
2.633 + ///
2.634 + /// Next node to be processed.
2.635 + ///
2.636 + /// \return The next node to be processed or INVALID if the
2.637 + /// priority heap is empty.
2.638 + Node nextNode() {
2.639 + return !_heap->empty() ? _heap->top() : INVALID;
2.640 + }
2.641 +
2.642 + /// \brief Returns \c false if there are nodes
2.643 + /// to be processed in the priority heap
2.644 + ///
2.645 + /// Returns \c false if there are nodes
2.646 + /// to be processed in the priority heap
2.647 + bool emptyQueue() { return _heap->empty(); }
2.648 + /// \brief Returns the number of the nodes to be processed
2.649 + /// in the priority heap
2.650 + ///
2.651 + /// Returns the number of the nodes to be processed in the priority heap
2.652 + int emptySize() { return _heap->size(); }
2.653 +
2.654 + /// \brief Executes the algorithm.
2.655 + ///
2.656 + /// Executes the algorithm.
2.657 + ///
2.658 + ///\pre init() must be called and at least one node should be added
2.659 + /// with addSource() before using this function.
2.660 + ///
2.661 + /// This method runs the Maximum Cardinality Search algorithm from the
2.662 + /// source node(s).
2.663 + void start() {
2.664 + while ( !_heap->empty() ) processNextNode();
2.665 + }
2.666 +
2.667 + /// \brief Executes the algorithm until \c dest is reached.
2.668 + ///
2.669 + /// Executes the algorithm until \c dest is reached.
2.670 + ///
2.671 + /// \pre init() must be called and at least one node should be added
2.672 + /// with addSource() before using this function.
2.673 + ///
2.674 + /// This method runs the %MaxCardinalitySearch algorithm from the source
2.675 + /// nodes.
2.676 + void start(Node dest) {
2.677 + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
2.678 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
2.679 + }
2.680 +
2.681 + /// \brief Executes the algorithm until a condition is met.
2.682 + ///
2.683 + /// Executes the algorithm until a condition is met.
2.684 + ///
2.685 + /// \pre init() must be called and at least one node should be added
2.686 + /// with addSource() before using this function.
2.687 + ///
2.688 + /// \param nm must be a bool (or convertible) node map. The algorithm
2.689 + /// will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
2.690 + template <typename NodeBoolMap>
2.691 + void start(const NodeBoolMap &nm) {
2.692 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
2.693 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
2.694 + }
2.695 +
2.696 + /// \brief Runs the maximum cardinality search algorithm from node \c s.
2.697 + ///
2.698 + /// This method runs the %MaxCardinalitySearch algorithm from a root
2.699 + /// node \c s.
2.700 + ///
2.701 + ///\note d.run(s) is just a shortcut of the following code.
2.702 + ///\code
2.703 + /// d.init();
2.704 + /// d.addSource(s);
2.705 + /// d.start();
2.706 + ///\endcode
2.707 + void run(Node s) {
2.708 + init();
2.709 + addSource(s);
2.710 + start();
2.711 + }
2.712 +
2.713 + /// \brief Runs the maximum cardinality search algorithm for the
2.714 + /// whole digraph.
2.715 + ///
2.716 + /// This method runs the %MaxCardinalitySearch algorithm from all
2.717 + /// unprocessed node of the digraph.
2.718 + ///
2.719 + ///\note d.run(s) is just a shortcut of the following code.
2.720 + ///\code
2.721 + /// d.init();
2.722 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
2.723 + /// if (!d.reached(it)) {
2.724 + /// d.addSource(s);
2.725 + /// d.start();
2.726 + /// }
2.727 + /// }
2.728 + ///\endcode
2.729 + void run() {
2.730 + init();
2.731 + for (NodeIt it(*_graph); it != INVALID; ++it) {
2.732 + if (!reached(it)) {
2.733 + addSource(it);
2.734 + start();
2.735 + }
2.736 + }
2.737 + }
2.738 +
2.739 + ///@}
2.740 +
2.741 + /// \name Query Functions
2.742 + /// The results of the maximum cardinality search algorithm can be
2.743 + /// obtained using these functions.
2.744 + /// \n
2.745 + /// Before the use of these functions, either run() or start() must be
2.746 + /// called.
2.747 +
2.748 + ///@{
2.749 +
2.750 + /// \brief The cardinality of a node.
2.751 + ///
2.752 + /// Returns the cardinality of a node.
2.753 + /// \pre \ref run() must be called before using this function.
2.754 + /// \warning If node \c v in unreachable from the root the return value
2.755 + /// of this funcion is undefined.
2.756 + Value cardinality(Node node) const { return (*_cardinality)[node]; }
2.757 +
2.758 + /// \brief The current cardinality of a node.
2.759 + ///
2.760 + /// Returns the current cardinality of a node.
2.761 + /// \pre the given node should be reached but not processed
2.762 + Value currentCardinality(Node node) const { return (*_heap)[node]; }
2.763 +
2.764 + /// \brief Returns a reference to the NodeMap of cardinalities.
2.765 + ///
2.766 + /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
2.767 + /// must be called before using this function.
2.768 + const CardinalityMap &cardinalityMap() const { return *_cardinality;}
2.769 +
2.770 + /// \brief Checks if a node is reachable from the root.
2.771 + ///
2.772 + /// Returns \c true if \c v is reachable from the root.
2.773 + /// \warning The source nodes are initated as unreached.
2.774 + /// \pre \ref run() must be called before using this function.
2.775 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
2.776 +
2.777 + /// \brief Checks if a node is processed.
2.778 + ///
2.779 + /// Returns \c true if \c v is processed, i.e. the shortest
2.780 + /// path to \c v has already found.
2.781 + /// \pre \ref run() must be called before using this function.
2.782 + bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
2.783 +
2.784 + ///@}
2.785 + };
2.786 +
2.787 +}
2.788 +
2.789 +#endif
3.1 --- a/test/CMakeLists.txt Wed Sep 22 09:38:23 2010 +0200
3.2 +++ b/test/CMakeLists.txt Mon Nov 15 22:23:35 2010 +0100
3.3 @@ -31,6 +31,7 @@
3.4 kruskal_test
3.5 maps_test
3.6 matching_test
3.7 + max_cardinality_search_test
3.8 max_clique_test
3.9 min_cost_arborescence_test
3.10 min_cost_flow_test
4.1 --- a/test/Makefile.am Wed Sep 22 09:38:23 2010 +0200
4.2 +++ b/test/Makefile.am Mon Nov 15 22:23:35 2010 +0100
4.3 @@ -33,6 +33,7 @@
4.4 test/kruskal_test \
4.5 test/maps_test \
4.6 test/matching_test \
4.7 + test/max_cardinality_search_test \
4.8 test/max_clique_test \
4.9 test/min_cost_arborescence_test \
4.10 test/min_cost_flow_test \
4.11 @@ -85,6 +86,7 @@
4.12 test_maps_test_SOURCES = test/maps_test.cc
4.13 test_mip_test_SOURCES = test/mip_test.cc
4.14 test_matching_test_SOURCES = test/matching_test.cc
4.15 +test_max_cardinality_search_test_SOURCES = test/max_cardinality_search_test.cc
4.16 test_max_clique_test_SOURCES = test/max_clique_test.cc
4.17 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
4.18 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/max_cardinality_search_test.cc Mon Nov 15 22:23:35 2010 +0100
5.3 @@ -0,0 +1,162 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2010
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#include <iostream>
5.23 +
5.24 +#include "test_tools.h"
5.25 +#include <lemon/smart_graph.h>
5.26 +#include <lemon/max_cardinality_search.h>
5.27 +#include <lemon/concepts/digraph.h>
5.28 +#include <lemon/concepts/maps.h>
5.29 +#include <lemon/concepts/heap.h>
5.30 +#include <lemon/lgf_reader.h>
5.31 +
5.32 +using namespace lemon;
5.33 +using namespace std;
5.34 +
5.35 +char test_lgf[] =
5.36 + "@nodes\n"
5.37 + "label\n"
5.38 + "0\n"
5.39 + "1\n"
5.40 + "2\n"
5.41 + "3\n"
5.42 + "@arcs\n"
5.43 + " label capacity\n"
5.44 + "0 1 0 2\n"
5.45 + "1 0 1 2\n"
5.46 + "2 1 2 1\n"
5.47 + "2 3 3 3\n"
5.48 + "3 2 4 3\n"
5.49 + "3 1 5 5\n"
5.50 + "@attributes\n"
5.51 + "s 0\n"
5.52 + "x 1\n"
5.53 + "y 2\n"
5.54 + "z 3\n";
5.55 +
5.56 +void checkMaxCardSearchCompile() {
5.57 +
5.58 + typedef concepts::Digraph Digraph;
5.59 + typedef int Value;
5.60 + typedef Digraph::Node Node;
5.61 + typedef Digraph::Arc Arc;
5.62 + typedef concepts::ReadMap<Arc,Value> CapMap;
5.63 + typedef concepts::ReadWriteMap<Node,Value> CardMap;
5.64 + typedef concepts::ReadWriteMap<Node,bool> ProcMap;
5.65 + typedef Digraph::NodeMap<int> HeapCrossRef;
5.66 +
5.67 + Digraph g;
5.68 + Node n,s;
5.69 + CapMap cap;
5.70 + CardMap card;
5.71 + ProcMap proc;
5.72 + HeapCrossRef crossref(g);
5.73 +
5.74 + typedef MaxCardinalitySearch<Digraph,CapMap>
5.75 + ::SetCapacityMap<CapMap>
5.76 + ::SetCardinalityMap<CardMap>
5.77 + ::SetProcessedMap<ProcMap>
5.78 + ::SetStandardHeap<BinHeap<Value,HeapCrossRef> >
5.79 + ::Create MaxCardType;
5.80 +
5.81 + MaxCardType maxcard(g,cap);
5.82 + const MaxCardType& const_maxcard = maxcard;
5.83 +
5.84 + const MaxCardType::Heap& heap_const = const_maxcard.heap();
5.85 + MaxCardType::Heap& heap = const_cast<MaxCardType::Heap&>(heap_const);
5.86 + maxcard.heap(heap,crossref);
5.87 +
5.88 + maxcard.capacityMap(cap).cardinalityMap(card).processedMap(proc);
5.89 +
5.90 + maxcard.init();
5.91 + maxcard.addSource(s);
5.92 + n = maxcard.nextNode();
5.93 + maxcard.processNextNode();
5.94 + maxcard.start();
5.95 + maxcard.run(s);
5.96 + maxcard.run();
5.97 + }
5.98 +
5.99 + void checkWithIntMap( std::istringstream& input)
5.100 + {
5.101 + typedef SmartDigraph Digraph;
5.102 + typedef Digraph::Node Node;
5.103 + typedef Digraph::ArcMap<int> CapMap;
5.104 +
5.105 + Digraph g;
5.106 + Node s,x,y,z,a;
5.107 + CapMap cap(g);
5.108 +
5.109 + DigraphReader<Digraph>(g,input).
5.110 + arcMap("capacity", cap).
5.111 + node("s",s).
5.112 + node("x",x).
5.113 + node("y",y).
5.114 + node("z",z).
5.115 + run();
5.116 +
5.117 + MaxCardinalitySearch<Digraph,CapMap> maxcard(g,cap);
5.118 +
5.119 + maxcard.init();
5.120 + maxcard.addSource(s);
5.121 + maxcard.start(x);
5.122 +
5.123 + check(maxcard.processed(s) and !maxcard.processed(x) and
5.124 + !maxcard.processed(y), "Wrong processed()!");
5.125 +
5.126 + a=maxcard.nextNode();
5.127 + check(maxcard.processNextNode()==a,
5.128 + "Wrong nextNode() or processNextNode() return value!");
5.129 +
5.130 + check(maxcard.processed(a), "Wrong processNextNode()!");
5.131 +
5.132 + maxcard.start();
5.133 + check(maxcard.cardinality(x)==2 and maxcard.cardinality(y)>=4,
5.134 + "Wrong cardinalities!");
5.135 + }
5.136 +
5.137 + void checkWithConst1Map(std::istringstream &input) {
5.138 + typedef SmartDigraph Digraph;
5.139 + typedef Digraph::Node Node;
5.140 +
5.141 + Digraph g;
5.142 + Node s,x,y,z;
5.143 +
5.144 + DigraphReader<Digraph>(g,input).
5.145 + node("s",s).
5.146 + node("x",x).
5.147 + node("y",y).
5.148 + node("z",z).
5.149 + run();
5.150 +
5.151 + MaxCardinalitySearch<Digraph> maxcard(g);
5.152 + maxcard.run(s);
5.153 + check(maxcard.cardinality(x)==1 &&
5.154 + maxcard.cardinality(y)+maxcard.cardinality(z)==3,
5.155 + "Wrong cardinalities!");
5.156 +}
5.157 +
5.158 +int main() {
5.159 +
5.160 + std::istringstream input1(test_lgf);
5.161 + checkWithIntMap(input1);
5.162 +
5.163 + std::istringstream input2(test_lgf);
5.164 + checkWithConst1Map(input2);
5.165 +}