thoneyvazul@916: /* -*- C++ -*- thoneyvazul@916: * thoneyvazul@916: * This file is a part of LEMON, a generic C++ optimization library thoneyvazul@916: * thoneyvazul@916: * Copyright (C) 2003-2010 thoneyvazul@916: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport thoneyvazul@916: * (Egervary Research Group on Combinatorial Optimization, EGRES). thoneyvazul@916: * thoneyvazul@916: * Permission to use, modify and distribute this software is granted thoneyvazul@916: * provided that this copyright notice appears in all copies. For thoneyvazul@916: * precise terms see the accompanying LICENSE file. thoneyvazul@916: * thoneyvazul@916: * This software is provided "AS IS" with no warranty of any kind, thoneyvazul@916: * express or implied, and with no claim as to its suitability for any thoneyvazul@916: * purpose. thoneyvazul@916: * thoneyvazul@916: */ thoneyvazul@916: thoneyvazul@916: #ifndef LEMON_MAX_CARDINALITY_SEARCH_H thoneyvazul@916: #define LEMON_MAX_CARDINALITY_SEARCH_H thoneyvazul@916: thoneyvazul@916: thoneyvazul@916: /// \ingroup search thoneyvazul@916: /// \file thoneyvazul@916: /// \brief Maximum cardinality search in undirected digraphs. thoneyvazul@916: thoneyvazul@916: #include thoneyvazul@916: #include thoneyvazul@916: thoneyvazul@916: #include thoneyvazul@916: #include thoneyvazul@916: thoneyvazul@916: #include thoneyvazul@916: thoneyvazul@916: namespace lemon { thoneyvazul@916: thoneyvazul@916: /// \brief Default traits class of MaxCardinalitySearch class. thoneyvazul@916: /// thoneyvazul@916: /// Default traits class of MaxCardinalitySearch class. thoneyvazul@916: /// \param Digraph Digraph type. thoneyvazul@916: /// \param CapacityMap Type of capacity map. thoneyvazul@916: template thoneyvazul@916: struct MaxCardinalitySearchDefaultTraits { thoneyvazul@916: /// The digraph type the algorithm runs on. thoneyvazul@916: typedef GR Digraph; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct CapMapSelector { thoneyvazul@916: thoneyvazul@916: typedef CM CapacityMap; thoneyvazul@916: thoneyvazul@916: static CapacityMap *createCapacityMap(const Digraph& g) { thoneyvazul@916: return new CapacityMap(g); thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct CapMapSelector > > { thoneyvazul@916: thoneyvazul@916: typedef ConstMap > CapacityMap; thoneyvazul@916: thoneyvazul@916: static CapacityMap *createCapacityMap(const Digraph&) { thoneyvazul@916: return new CapacityMap; thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: /// \brief The type of the map that stores the arc capacities. thoneyvazul@916: /// thoneyvazul@916: /// The type of the map that stores the arc capacities. thoneyvazul@916: /// It must meet the \ref concepts::ReadMap "ReadMap" concept. thoneyvazul@916: typedef typename CapMapSelector::CapacityMap CapacityMap; thoneyvazul@916: thoneyvazul@916: /// \brief The type of the capacity of the arcs. thoneyvazul@916: typedef typename CapacityMap::Value Value; thoneyvazul@916: thoneyvazul@916: /// \brief Instantiates a CapacityMap. thoneyvazul@916: /// thoneyvazul@916: /// This function instantiates a \ref CapacityMap. thoneyvazul@916: /// \param digraph is the digraph, to which we would like to define thoneyvazul@916: /// the CapacityMap. thoneyvazul@916: static CapacityMap *createCapacityMap(const Digraph& digraph) { thoneyvazul@916: return CapMapSelector::createCapacityMap(digraph); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief The cross reference type used by heap. thoneyvazul@916: /// thoneyvazul@916: /// The cross reference type used by heap. thoneyvazul@916: /// Usually it is \c Digraph::NodeMap. thoneyvazul@916: typedef typename Digraph::template NodeMap HeapCrossRef; thoneyvazul@916: thoneyvazul@916: /// \brief Instantiates a HeapCrossRef. thoneyvazul@916: /// thoneyvazul@916: /// This function instantiates a \ref HeapCrossRef. thoneyvazul@916: /// \param digraph is the digraph, to which we would like to define the thoneyvazul@916: /// HeapCrossRef. thoneyvazul@916: static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) { thoneyvazul@916: return new HeapCrossRef(digraph); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct HeapSelector { thoneyvazul@916: template thoneyvazul@916: struct Selector { thoneyvazul@916: typedef BinHeap > Heap; thoneyvazul@916: }; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct HeapSelector > > { thoneyvazul@916: template thoneyvazul@916: struct Selector { thoneyvazul@916: typedef BucketHeap Heap; thoneyvazul@916: }; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: /// \brief The heap type used by MaxCardinalitySearch algorithm. thoneyvazul@916: /// thoneyvazul@916: /// The heap type used by MaxCardinalitySearch algorithm. It should thoneyvazul@916: /// maximalize the priorities. The default heap type is thoneyvazul@916: /// the \ref BinHeap, but it is specialized when the thoneyvazul@916: /// CapacityMap is ConstMap > thoneyvazul@916: /// to BucketHeap. thoneyvazul@916: /// thoneyvazul@916: /// \sa MaxCardinalitySearch thoneyvazul@916: typedef typename HeapSelector thoneyvazul@916: ::template Selector thoneyvazul@916: ::Heap Heap; thoneyvazul@916: thoneyvazul@916: /// \brief Instantiates a Heap. thoneyvazul@916: /// thoneyvazul@916: /// This function instantiates a \ref Heap. thoneyvazul@916: /// \param crossref The cross reference of the heap. thoneyvazul@916: static Heap *createHeap(HeapCrossRef& crossref) { thoneyvazul@916: return new Heap(crossref); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief The type of the map that stores whether a node is processed. thoneyvazul@916: /// thoneyvazul@916: /// The type of the map that stores whether a node is processed. thoneyvazul@916: /// It must meet the \ref concepts::WriteMap "WriteMap" concept. thoneyvazul@916: /// By default it is a NullMap. thoneyvazul@916: typedef NullMap ProcessedMap; thoneyvazul@916: thoneyvazul@916: /// \brief Instantiates a ProcessedMap. thoneyvazul@916: /// thoneyvazul@916: /// This function instantiates a \ref ProcessedMap. thoneyvazul@916: /// \param digraph is the digraph, to which thoneyvazul@916: /// we would like to define the \ref ProcessedMap thoneyvazul@916: #ifdef DOXYGEN thoneyvazul@916: static ProcessedMap *createProcessedMap(const Digraph &digraph) thoneyvazul@916: #else thoneyvazul@916: static ProcessedMap *createProcessedMap(const Digraph &) thoneyvazul@916: #endif thoneyvazul@916: { thoneyvazul@916: return new ProcessedMap(); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief The type of the map that stores the cardinalities of the nodes. thoneyvazul@916: /// thoneyvazul@916: /// The type of the map that stores the cardinalities of the nodes. thoneyvazul@916: /// It must meet the \ref concepts::WriteMap "WriteMap" concept. thoneyvazul@916: typedef typename Digraph::template NodeMap CardinalityMap; thoneyvazul@916: thoneyvazul@916: /// \brief Instantiates a CardinalityMap. thoneyvazul@916: /// thoneyvazul@916: /// This function instantiates a \ref CardinalityMap. thoneyvazul@916: /// \param digraph is the digraph, to which we would like to define the \ref thoneyvazul@916: /// CardinalityMap thoneyvazul@916: static CardinalityMap *createCardinalityMap(const Digraph &digraph) { thoneyvazul@916: return new CardinalityMap(digraph); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: /// \ingroup search thoneyvazul@916: /// thoneyvazul@916: /// \brief Maximum Cardinality Search algorithm class. thoneyvazul@916: /// thoneyvazul@916: /// This class provides an efficient implementation of Maximum Cardinality thoneyvazul@916: /// Search algorithm. The maximum cardinality search first chooses any thoneyvazul@916: /// node of the digraph. Then every time it chooses one unprocessed node thoneyvazul@916: /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes thoneyvazul@916: /// which were previusly processed. thoneyvazul@916: /// If there is a cut in the digraph the algorithm should choose thoneyvazul@916: /// again any unprocessed node of the digraph. thoneyvazul@916: thoneyvazul@916: /// The arc capacities are passed to the algorithm using a thoneyvazul@916: /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any thoneyvazul@916: /// kind of capacity. thoneyvazul@916: /// thoneyvazul@916: /// The type of the capacity is determined by the \ref thoneyvazul@916: /// concepts::ReadMap::Value "Value" of the capacity map. thoneyvazul@916: /// thoneyvazul@916: /// It is also possible to change the underlying priority heap. thoneyvazul@916: /// thoneyvazul@916: /// thoneyvazul@916: /// \param GR The digraph type the algorithm runs on. The value of thoneyvazul@916: /// Digraph is not used directly by the search algorithm, it thoneyvazul@916: /// is only passed to \ref MaxCardinalitySearchDefaultTraits. thoneyvazul@916: /// \param CAP This read-only ArcMap determines the capacities of thoneyvazul@916: /// the arcs. It is read once for each arc, so the map may involve in thoneyvazul@916: /// relatively time consuming process to compute the arc capacity if thoneyvazul@916: /// it is necessary. The default map type is \ref thoneyvazul@916: /// ConstMap "ConstMap >". The value thoneyvazul@916: /// of CapacityMap is not used directly by search algorithm, it is only thoneyvazul@916: /// passed to \ref MaxCardinalitySearchDefaultTraits. thoneyvazul@916: /// \param TR Traits class to set various data types used by the thoneyvazul@916: /// algorithm. The default traits class is thoneyvazul@916: /// \ref MaxCardinalitySearchDefaultTraits thoneyvazul@916: /// "MaxCardinalitySearchDefaultTraits". thoneyvazul@916: /// See \ref MaxCardinalitySearchDefaultTraits thoneyvazul@916: /// for the documentation of a MaxCardinalitySearch traits class. thoneyvazul@916: thoneyvazul@916: #ifdef DOXYGEN thoneyvazul@916: template thoneyvazul@916: #else thoneyvazul@916: template >, thoneyvazul@916: typename TR = thoneyvazul@916: MaxCardinalitySearchDefaultTraits > thoneyvazul@916: #endif thoneyvazul@916: class MaxCardinalitySearch { thoneyvazul@916: public: thoneyvazul@916: thoneyvazul@916: typedef TR Traits; thoneyvazul@916: ///The type of the underlying digraph. thoneyvazul@916: typedef typename Traits::Digraph Digraph; thoneyvazul@916: thoneyvazul@916: ///The type of the capacity of the arcs. thoneyvazul@916: typedef typename Traits::CapacityMap::Value Value; thoneyvazul@916: ///The type of the map that stores the arc capacities. thoneyvazul@916: typedef typename Traits::CapacityMap CapacityMap; thoneyvazul@916: ///The type of the map indicating if a node is processed. thoneyvazul@916: typedef typename Traits::ProcessedMap ProcessedMap; thoneyvazul@916: ///The type of the map that stores the cardinalities of the nodes. thoneyvazul@916: typedef typename Traits::CardinalityMap CardinalityMap; thoneyvazul@916: ///The cross reference type used for the current heap. thoneyvazul@916: typedef typename Traits::HeapCrossRef HeapCrossRef; thoneyvazul@916: ///The heap type used by the algorithm. It maximizes the priorities. thoneyvazul@916: typedef typename Traits::Heap Heap; thoneyvazul@916: private: thoneyvazul@916: // Pointer to the underlying digraph. thoneyvazul@916: const Digraph *_graph; thoneyvazul@916: // Pointer to the capacity map thoneyvazul@916: const CapacityMap *_capacity; thoneyvazul@916: // Indicates if \ref _capacity is locally allocated (\c true) or not. thoneyvazul@916: bool local_capacity; thoneyvazul@916: // Pointer to the map of cardinality. thoneyvazul@916: CardinalityMap *_cardinality; thoneyvazul@916: // Indicates if \ref _cardinality is locally allocated (\c true) or not. thoneyvazul@916: bool local_cardinality; thoneyvazul@916: // Pointer to the map of processed status of the nodes. thoneyvazul@916: ProcessedMap *_processed; thoneyvazul@916: // Indicates if \ref _processed is locally allocated (\c true) or not. thoneyvazul@916: bool local_processed; thoneyvazul@916: // Pointer to the heap cross references. thoneyvazul@916: HeapCrossRef *_heap_cross_ref; thoneyvazul@916: // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. thoneyvazul@916: bool local_heap_cross_ref; thoneyvazul@916: // Pointer to the heap. thoneyvazul@916: Heap *_heap; thoneyvazul@916: // Indicates if \ref _heap is locally allocated (\c true) or not. thoneyvazul@916: bool local_heap; thoneyvazul@916: thoneyvazul@916: public : thoneyvazul@916: thoneyvazul@916: typedef MaxCardinalitySearch Create; thoneyvazul@916: thoneyvazul@916: ///\name Named template parameters thoneyvazul@916: thoneyvazul@916: ///@{ thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct DefCapacityMapTraits : public Traits { thoneyvazul@916: typedef T CapacityMap; thoneyvazul@916: static CapacityMap *createCapacityMap(const Digraph &) { thoneyvazul@916: LEMON_ASSERT(false,"Uninitialized parameter."); thoneyvazul@916: return 0; thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: /// \brief \ref named-templ-param "Named parameter" for setting thoneyvazul@916: /// CapacityMap type thoneyvazul@916: /// thoneyvazul@916: /// \ref named-templ-param "Named parameter" for setting CapacityMap type thoneyvazul@916: /// for the algorithm. thoneyvazul@916: template thoneyvazul@916: struct SetCapacityMap thoneyvazul@916: : public MaxCardinalitySearch > { thoneyvazul@916: typedef MaxCardinalitySearch > Create; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct DefCardinalityMapTraits : public Traits { thoneyvazul@916: typedef T CardinalityMap; thoneyvazul@916: static CardinalityMap *createCardinalityMap(const Digraph &) thoneyvazul@916: { thoneyvazul@916: LEMON_ASSERT(false,"Uninitialized parameter."); thoneyvazul@916: return 0; thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: /// \brief \ref named-templ-param "Named parameter" for setting thoneyvazul@916: /// CardinalityMap type thoneyvazul@916: /// thoneyvazul@916: /// \ref named-templ-param "Named parameter" for setting CardinalityMap thoneyvazul@916: /// type for the algorithm. thoneyvazul@916: template thoneyvazul@916: struct SetCardinalityMap thoneyvazul@916: : public MaxCardinalitySearch > { thoneyvazul@916: typedef MaxCardinalitySearch > Create; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct DefProcessedMapTraits : public Traits { thoneyvazul@916: typedef T ProcessedMap; thoneyvazul@916: static ProcessedMap *createProcessedMap(const Digraph &) { thoneyvazul@916: LEMON_ASSERT(false,"Uninitialized parameter."); thoneyvazul@916: return 0; thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: /// \brief \ref named-templ-param "Named parameter" for setting thoneyvazul@916: /// ProcessedMap type thoneyvazul@916: /// thoneyvazul@916: /// \ref named-templ-param "Named parameter" for setting ProcessedMap type thoneyvazul@916: /// for the algorithm. thoneyvazul@916: template thoneyvazul@916: struct SetProcessedMap thoneyvazul@916: : public MaxCardinalitySearch > { thoneyvazul@916: typedef MaxCardinalitySearch > Create; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct DefHeapTraits : public Traits { thoneyvazul@916: typedef CR HeapCrossRef; thoneyvazul@916: typedef H Heap; thoneyvazul@916: static HeapCrossRef *createHeapCrossRef(const Digraph &) { thoneyvazul@916: LEMON_ASSERT(false,"Uninitialized parameter."); thoneyvazul@916: return 0; thoneyvazul@916: } thoneyvazul@916: static Heap *createHeap(HeapCrossRef &) { thoneyvazul@916: LEMON_ASSERT(false,"Uninitialized parameter."); thoneyvazul@916: return 0; thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: /// \brief \ref named-templ-param "Named parameter" for setting heap thoneyvazul@916: /// and cross reference type thoneyvazul@916: /// thoneyvazul@916: /// \ref named-templ-param "Named parameter" for setting heap and cross thoneyvazul@916: /// reference type for the algorithm. thoneyvazul@916: template > thoneyvazul@916: struct SetHeap thoneyvazul@916: : public MaxCardinalitySearch > { thoneyvazul@916: typedef MaxCardinalitySearch< Digraph, CapacityMap, thoneyvazul@916: DefHeapTraits > Create; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: template thoneyvazul@916: struct DefStandardHeapTraits : public Traits { thoneyvazul@916: typedef CR HeapCrossRef; thoneyvazul@916: typedef H Heap; thoneyvazul@916: static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) { thoneyvazul@916: return new HeapCrossRef(digraph); thoneyvazul@916: } thoneyvazul@916: static Heap *createHeap(HeapCrossRef &crossref) { thoneyvazul@916: return new Heap(crossref); thoneyvazul@916: } thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: /// \brief \ref named-templ-param "Named parameter" for setting heap and thoneyvazul@916: /// cross reference type with automatic allocation thoneyvazul@916: /// thoneyvazul@916: /// \ref named-templ-param "Named parameter" for setting heap and cross thoneyvazul@916: /// reference type. It can allocate the heap and the cross reference thoneyvazul@916: /// object if the cross reference's constructor waits for the digraph as thoneyvazul@916: /// parameter and the heap's constructor waits for the cross reference. thoneyvazul@916: template > thoneyvazul@916: struct SetStandardHeap thoneyvazul@916: : public MaxCardinalitySearch > { thoneyvazul@916: typedef MaxCardinalitySearch > thoneyvazul@916: Create; thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: ///@} thoneyvazul@916: thoneyvazul@916: thoneyvazul@916: protected: thoneyvazul@916: thoneyvazul@916: MaxCardinalitySearch() {} thoneyvazul@916: thoneyvazul@916: public: thoneyvazul@916: thoneyvazul@916: /// \brief Constructor. thoneyvazul@916: /// thoneyvazul@916: ///\param digraph the digraph the algorithm will run on. thoneyvazul@916: ///\param capacity the capacity map used by the algorithm. thoneyvazul@916: ///When no capacity map given, a constant 1 capacity map will thoneyvazul@916: ///be allocated. thoneyvazul@916: #ifdef DOXYGEN thoneyvazul@916: MaxCardinalitySearch(const Digraph& digraph, thoneyvazul@916: const CapacityMap& capacity=0 ) : thoneyvazul@916: #else thoneyvazul@916: MaxCardinalitySearch(const Digraph& digraph, thoneyvazul@916: const CapacityMap& capacity=*static_cast(0) ) : thoneyvazul@916: #endif thoneyvazul@916: _graph(&digraph), thoneyvazul@916: _capacity(&capacity), local_capacity(false), thoneyvazul@916: _cardinality(0), local_cardinality(false), thoneyvazul@916: _processed(0), local_processed(false), thoneyvazul@916: _heap_cross_ref(0), local_heap_cross_ref(false), thoneyvazul@916: _heap(0), local_heap(false) thoneyvazul@916: { } thoneyvazul@916: thoneyvazul@916: /// \brief Destructor. thoneyvazul@916: ~MaxCardinalitySearch() { thoneyvazul@916: if(local_capacity) delete _capacity; thoneyvazul@916: if(local_cardinality) delete _cardinality; thoneyvazul@916: if(local_processed) delete _processed; thoneyvazul@916: if(local_heap_cross_ref) delete _heap_cross_ref; thoneyvazul@916: if(local_heap) delete _heap; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Sets the capacity map. thoneyvazul@916: /// thoneyvazul@916: /// Sets the capacity map. thoneyvazul@916: /// \return (*this) thoneyvazul@916: MaxCardinalitySearch &capacityMap(const CapacityMap &m) { thoneyvazul@916: if (local_capacity) { thoneyvazul@916: delete _capacity; thoneyvazul@916: local_capacity=false; thoneyvazul@916: } thoneyvazul@916: _capacity=&m; thoneyvazul@916: return *this; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Returns a const reference to the capacity map. thoneyvazul@916: /// thoneyvazul@916: /// Returns a const reference to the capacity map used by thoneyvazul@916: /// the algorithm. thoneyvazul@916: const CapacityMap &capacityMap() const { thoneyvazul@916: return *_capacity; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Sets the map storing the cardinalities calculated by the thoneyvazul@916: /// algorithm. thoneyvazul@916: /// thoneyvazul@916: /// Sets the map storing the cardinalities calculated by the algorithm. thoneyvazul@916: /// If you don't use this function before calling \ref run(), thoneyvazul@916: /// it will allocate one. The destuctor deallocates this thoneyvazul@916: /// automatically allocated map, of course. thoneyvazul@916: /// \return (*this) thoneyvazul@916: MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) { thoneyvazul@916: if(local_cardinality) { thoneyvazul@916: delete _cardinality; thoneyvazul@916: local_cardinality=false; thoneyvazul@916: } thoneyvazul@916: _cardinality = &m; thoneyvazul@916: return *this; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Sets the map storing the processed nodes. thoneyvazul@916: /// thoneyvazul@916: /// Sets the map storing the processed nodes. thoneyvazul@916: /// If you don't use this function before calling \ref run(), thoneyvazul@916: /// it will allocate one. The destuctor deallocates this thoneyvazul@916: /// automatically allocated map, of course. thoneyvazul@916: /// \return (*this) thoneyvazul@916: MaxCardinalitySearch &processedMap(ProcessedMap &m) thoneyvazul@916: { thoneyvazul@916: if(local_processed) { thoneyvazul@916: delete _processed; thoneyvazul@916: local_processed=false; thoneyvazul@916: } thoneyvazul@916: _processed = &m; thoneyvazul@916: return *this; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Returns a const reference to the cardinality map. thoneyvazul@916: /// thoneyvazul@916: /// Returns a const reference to the cardinality map used by thoneyvazul@916: /// the algorithm. thoneyvazul@916: const ProcessedMap &processedMap() const { thoneyvazul@916: return *_processed; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Sets the heap and the cross reference used by algorithm. thoneyvazul@916: /// thoneyvazul@916: /// Sets the heap and the cross reference used by algorithm. thoneyvazul@916: /// If you don't use this function before calling \ref run(), thoneyvazul@916: /// it will allocate one. The destuctor deallocates this thoneyvazul@916: /// automatically allocated map, of course. thoneyvazul@916: /// \return (*this) thoneyvazul@916: MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) { thoneyvazul@916: if(local_heap_cross_ref) { thoneyvazul@916: delete _heap_cross_ref; thoneyvazul@916: local_heap_cross_ref = false; thoneyvazul@916: } thoneyvazul@916: _heap_cross_ref = &cr; thoneyvazul@916: if(local_heap) { thoneyvazul@916: delete _heap; thoneyvazul@916: local_heap = false; thoneyvazul@916: } thoneyvazul@916: _heap = &hp; thoneyvazul@916: return *this; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Returns a const reference to the heap. thoneyvazul@916: /// thoneyvazul@916: /// Returns a const reference to the heap used by thoneyvazul@916: /// the algorithm. thoneyvazul@916: const Heap &heap() const { thoneyvazul@916: return *_heap; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Returns a const reference to the cross reference. thoneyvazul@916: /// thoneyvazul@916: /// Returns a const reference to the cross reference thoneyvazul@916: /// of the heap. thoneyvazul@916: const HeapCrossRef &heapCrossRef() const { thoneyvazul@916: return *_heap_cross_ref; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: private: thoneyvazul@916: thoneyvazul@916: typedef typename Digraph::Node Node; thoneyvazul@916: typedef typename Digraph::NodeIt NodeIt; thoneyvazul@916: typedef typename Digraph::Arc Arc; thoneyvazul@916: typedef typename Digraph::InArcIt InArcIt; thoneyvazul@916: thoneyvazul@916: void create_maps() { thoneyvazul@916: if(!_capacity) { thoneyvazul@916: local_capacity = true; thoneyvazul@916: _capacity = Traits::createCapacityMap(*_graph); thoneyvazul@916: } thoneyvazul@916: if(!_cardinality) { thoneyvazul@916: local_cardinality = true; thoneyvazul@916: _cardinality = Traits::createCardinalityMap(*_graph); thoneyvazul@916: } thoneyvazul@916: if(!_processed) { thoneyvazul@916: local_processed = true; thoneyvazul@916: _processed = Traits::createProcessedMap(*_graph); thoneyvazul@916: } thoneyvazul@916: if (!_heap_cross_ref) { thoneyvazul@916: local_heap_cross_ref = true; thoneyvazul@916: _heap_cross_ref = Traits::createHeapCrossRef(*_graph); thoneyvazul@916: } thoneyvazul@916: if (!_heap) { thoneyvazul@916: local_heap = true; thoneyvazul@916: _heap = Traits::createHeap(*_heap_cross_ref); thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: void finalizeNodeData(Node node, Value capacity) { thoneyvazul@916: _processed->set(node, true); thoneyvazul@916: _cardinality->set(node, capacity); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: public: thoneyvazul@916: /// \name Execution control thoneyvazul@916: /// The simplest way to execute the algorithm is to use thoneyvazul@916: /// one of the member functions called \ref run(). thoneyvazul@916: /// \n thoneyvazul@916: /// If you need more control on the execution, thoneyvazul@916: /// first you must call \ref init(), then you can add several source nodes thoneyvazul@916: /// with \ref addSource(). thoneyvazul@916: /// Finally \ref start() will perform the computation. thoneyvazul@916: thoneyvazul@916: ///@{ thoneyvazul@916: thoneyvazul@916: /// \brief Initializes the internal data structures. thoneyvazul@916: /// thoneyvazul@916: /// Initializes the internal data structures, and clears the heap. thoneyvazul@916: void init() { thoneyvazul@916: create_maps(); thoneyvazul@916: _heap->clear(); thoneyvazul@916: for (NodeIt it(*_graph) ; it != INVALID ; ++it) { thoneyvazul@916: _processed->set(it, false); thoneyvazul@916: _heap_cross_ref->set(it, Heap::PRE_HEAP); thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Adds a new source node. thoneyvazul@916: /// thoneyvazul@916: /// Adds a new source node to the priority heap. thoneyvazul@916: /// thoneyvazul@916: /// It checks if the node has not yet been added to the heap. thoneyvazul@916: void addSource(Node source, Value capacity = 0) { thoneyvazul@916: if(_heap->state(source) == Heap::PRE_HEAP) { thoneyvazul@916: _heap->push(source, capacity); thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Processes the next node in the priority heap thoneyvazul@916: /// thoneyvazul@916: /// Processes the next node in the priority heap. thoneyvazul@916: /// thoneyvazul@916: /// \return The processed node. thoneyvazul@916: /// thoneyvazul@916: /// \warning The priority heap must not be empty! thoneyvazul@916: Node processNextNode() { thoneyvazul@916: Node node = _heap->top(); thoneyvazul@916: finalizeNodeData(node, _heap->prio()); thoneyvazul@916: _heap->pop(); thoneyvazul@916: thoneyvazul@916: for (InArcIt it(*_graph, node); it != INVALID; ++it) { thoneyvazul@916: Node source = _graph->source(it); thoneyvazul@916: switch (_heap->state(source)) { thoneyvazul@916: case Heap::PRE_HEAP: thoneyvazul@916: _heap->push(source, (*_capacity)[it]); thoneyvazul@916: break; thoneyvazul@916: case Heap::IN_HEAP: thoneyvazul@916: _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]); thoneyvazul@916: break; thoneyvazul@916: case Heap::POST_HEAP: thoneyvazul@916: break; thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: return node; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Next node to be processed. thoneyvazul@916: /// thoneyvazul@916: /// Next node to be processed. thoneyvazul@916: /// thoneyvazul@916: /// \return The next node to be processed or INVALID if the thoneyvazul@916: /// priority heap is empty. thoneyvazul@916: Node nextNode() { thoneyvazul@916: return !_heap->empty() ? _heap->top() : INVALID; thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Returns \c false if there are nodes thoneyvazul@916: /// to be processed in the priority heap thoneyvazul@916: /// thoneyvazul@916: /// Returns \c false if there are nodes thoneyvazul@916: /// to be processed in the priority heap thoneyvazul@916: bool emptyQueue() { return _heap->empty(); } thoneyvazul@916: /// \brief Returns the number of the nodes to be processed thoneyvazul@916: /// in the priority heap thoneyvazul@916: /// thoneyvazul@916: /// Returns the number of the nodes to be processed in the priority heap thoneyvazul@916: int emptySize() { return _heap->size(); } thoneyvazul@916: thoneyvazul@916: /// \brief Executes the algorithm. thoneyvazul@916: /// thoneyvazul@916: /// Executes the algorithm. thoneyvazul@916: /// thoneyvazul@916: ///\pre init() must be called and at least one node should be added thoneyvazul@916: /// with addSource() before using this function. thoneyvazul@916: /// thoneyvazul@916: /// This method runs the Maximum Cardinality Search algorithm from the thoneyvazul@916: /// source node(s). thoneyvazul@916: void start() { thoneyvazul@916: while ( !_heap->empty() ) processNextNode(); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Executes the algorithm until \c dest is reached. thoneyvazul@916: /// thoneyvazul@916: /// Executes the algorithm until \c dest is reached. thoneyvazul@916: /// thoneyvazul@916: /// \pre init() must be called and at least one node should be added thoneyvazul@916: /// with addSource() before using this function. thoneyvazul@916: /// thoneyvazul@916: /// This method runs the %MaxCardinalitySearch algorithm from the source thoneyvazul@916: /// nodes. thoneyvazul@916: void start(Node dest) { thoneyvazul@916: while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); thoneyvazul@916: if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio()); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Executes the algorithm until a condition is met. thoneyvazul@916: /// thoneyvazul@916: /// Executes the algorithm until a condition is met. thoneyvazul@916: /// thoneyvazul@916: /// \pre init() must be called and at least one node should be added thoneyvazul@916: /// with addSource() before using this function. thoneyvazul@916: /// thoneyvazul@916: /// \param nm must be a bool (or convertible) node map. The algorithm thoneyvazul@916: /// will stop when it reaches a node \c v with nm[v]==true. thoneyvazul@916: template thoneyvazul@916: void start(const NodeBoolMap &nm) { thoneyvazul@916: while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); thoneyvazul@916: if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Runs the maximum cardinality search algorithm from node \c s. thoneyvazul@916: /// thoneyvazul@916: /// This method runs the %MaxCardinalitySearch algorithm from a root thoneyvazul@916: /// node \c s. thoneyvazul@916: /// thoneyvazul@916: ///\note d.run(s) is just a shortcut of the following code. thoneyvazul@916: ///\code thoneyvazul@916: /// d.init(); thoneyvazul@916: /// d.addSource(s); thoneyvazul@916: /// d.start(); thoneyvazul@916: ///\endcode thoneyvazul@916: void run(Node s) { thoneyvazul@916: init(); thoneyvazul@916: addSource(s); thoneyvazul@916: start(); thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: /// \brief Runs the maximum cardinality search algorithm for the thoneyvazul@916: /// whole digraph. thoneyvazul@916: /// thoneyvazul@916: /// This method runs the %MaxCardinalitySearch algorithm from all thoneyvazul@916: /// unprocessed node of the digraph. thoneyvazul@916: /// thoneyvazul@916: ///\note d.run(s) is just a shortcut of the following code. thoneyvazul@916: ///\code thoneyvazul@916: /// d.init(); thoneyvazul@916: /// for (NodeIt it(digraph); it != INVALID; ++it) { thoneyvazul@916: /// if (!d.reached(it)) { thoneyvazul@916: /// d.addSource(s); thoneyvazul@916: /// d.start(); thoneyvazul@916: /// } thoneyvazul@916: /// } thoneyvazul@916: ///\endcode thoneyvazul@916: void run() { thoneyvazul@916: init(); thoneyvazul@916: for (NodeIt it(*_graph); it != INVALID; ++it) { thoneyvazul@916: if (!reached(it)) { thoneyvazul@916: addSource(it); thoneyvazul@916: start(); thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: ///@} thoneyvazul@916: thoneyvazul@916: /// \name Query Functions thoneyvazul@916: /// The results of the maximum cardinality search algorithm can be thoneyvazul@916: /// obtained using these functions. thoneyvazul@916: /// \n thoneyvazul@916: /// Before the use of these functions, either run() or start() must be thoneyvazul@916: /// called. thoneyvazul@916: thoneyvazul@916: ///@{ thoneyvazul@916: thoneyvazul@916: /// \brief The cardinality of a node. thoneyvazul@916: /// thoneyvazul@916: /// Returns the cardinality of a node. thoneyvazul@916: /// \pre \ref run() must be called before using this function. thoneyvazul@916: /// \warning If node \c v in unreachable from the root the return value thoneyvazul@916: /// of this funcion is undefined. thoneyvazul@916: Value cardinality(Node node) const { return (*_cardinality)[node]; } thoneyvazul@916: thoneyvazul@916: /// \brief The current cardinality of a node. thoneyvazul@916: /// thoneyvazul@916: /// Returns the current cardinality of a node. thoneyvazul@916: /// \pre the given node should be reached but not processed thoneyvazul@916: Value currentCardinality(Node node) const { return (*_heap)[node]; } thoneyvazul@916: thoneyvazul@916: /// \brief Returns a reference to the NodeMap of cardinalities. thoneyvazul@916: /// thoneyvazul@916: /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() thoneyvazul@916: /// must be called before using this function. thoneyvazul@916: const CardinalityMap &cardinalityMap() const { return *_cardinality;} thoneyvazul@916: thoneyvazul@916: /// \brief Checks if a node is reachable from the root. thoneyvazul@916: /// thoneyvazul@916: /// Returns \c true if \c v is reachable from the root. thoneyvazul@916: /// \warning The source nodes are initated as unreached. thoneyvazul@916: /// \pre \ref run() must be called before using this function. thoneyvazul@916: bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } thoneyvazul@916: thoneyvazul@916: /// \brief Checks if a node is processed. thoneyvazul@916: /// thoneyvazul@916: /// Returns \c true if \c v is processed, i.e. the shortest thoneyvazul@916: /// path to \c v has already found. thoneyvazul@916: /// \pre \ref run() must be called before using this function. thoneyvazul@916: bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } thoneyvazul@916: thoneyvazul@916: ///@} thoneyvazul@916: }; thoneyvazul@916: thoneyvazul@916: } thoneyvazul@916: thoneyvazul@916: #endif