RhodeCode

  /// for the documentation of a MaxCardinalitySearch traits class.

#ifdef DOXYGEN

  template <typename GR, typename CAP, typename TR>

#else

  template <typename GR, typename CAP = 

	    ConstMap<typename GR::Arc, Const<int,1> >,

	    typename TR = 

            MaxCardinalitySearchDefaultTraits<GR, CAP> >

#endif

  class MaxCardinalitySearch {

  public:

    typedef TR Traits;

    ///The type of the underlying digraph.

    typedef typename Traits::Digraph Digraph;

    ///The type of the capacity of the arcs.

    typedef typename Traits::CapacityMap::Value Value;

    ///The type of the map that stores the arc capacities.

    typedef typename Traits::CapacityMap CapacityMap;

    ///The type of the map indicating if a node is processed.

    typedef typename Traits::ProcessedMap ProcessedMap;

    ///The type of the map that stores the cardinalities of the nodes.

    typedef typename Traits::CardinalityMap CardinalityMap;

    ///The cross reference type used for the current heap.

    typedef typename Traits::HeapCrossRef HeapCrossRef;

    ///The heap type used by the algorithm. It maximizes the priorities.

    typedef typename Traits::Heap Heap;

  private:

    // Pointer to the underlying digraph.

    const Digraph *_graph;

    // Pointer to the capacity map

    const CapacityMap *_capacity;

    // Indicates if \ref _capacity is locally allocated (\c true) or not.

    bool local_capacity;

    // Pointer to the map of cardinality.

    CardinalityMap *_cardinality;

    // Indicates if \ref _cardinality is locally allocated (\c true) or not.

    bool local_cardinality;

    // Pointer to the map of processed status of the nodes.

    ProcessedMap *_processed;

    // Indicates if \ref _processed is locally allocated (\c true) or not.

    bool local_processed;

    // Pointer to the heap cross references.

    HeapCrossRef *_heap_cross_ref;

    // Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.

    bool local_heap_cross_ref;

    // Pointer to the heap.

    Heap *_heap;

    // Indicates if \ref _heap is locally allocated (\c true) or not.

    bool local_heap;

  public :

    typedef MaxCardinalitySearch Create;

    ///\name Named template parameters

    ///@{

    template <class T>

    struct DefCapacityMapTraits : public Traits {

      typedef T CapacityMap;

      static CapacityMap *createCapacityMap(const Digraph &) {

       	LEMON_ASSERT(false,"Uninitialized parameter.");

	return 0;

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting 

    /// CapacityMap type

    ///

    /// \ref named-templ-param "Named parameter" for setting CapacityMap type

    /// for the algorithm.

    template <class T>

    struct SetCapacityMap 

      : public MaxCardinalitySearch<Digraph, CapacityMap, 

                                    DefCapacityMapTraits<T> > { 

      typedef MaxCardinalitySearch<Digraph, CapacityMap, 

                                   DefCapacityMapTraits<T> > Create;

    };

    template <class T>

    struct DefCardinalityMapTraits : public Traits {

      typedef T CardinalityMap;

      static CardinalityMap *createCardinalityMap(const Digraph &) 

      {

	LEMON_ASSERT(false,"Uninitialized parameter.");

	return 0;

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting 

    /// CardinalityMap type

    ///

    /// \ref named-templ-param "Named parameter" for setting CardinalityMap 

    /// type for the algorithm.

    template <class T>

    struct SetCardinalityMap 

      : public MaxCardinalitySearch<Digraph, CapacityMap, 

                                    DefCardinalityMapTraits<T> > { 

      typedef MaxCardinalitySearch<Digraph, CapacityMap, 

                                   DefCardinalityMapTraits<T> > Create;

    };

    template <class T>

    struct DefProcessedMapTraits : public Traits {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &) {

       	LEMON_ASSERT(false,"Uninitialized parameter.");

	return 0;

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting 

    /// ProcessedMap type

    ///

    /// \ref named-templ-param "Named parameter" for setting ProcessedMap type

    /// for the algorithm.

    template <class T>

    struct SetProcessedMap 

      : public MaxCardinalitySearch<Digraph, CapacityMap, 

                                    DefProcessedMapTraits<T> > { 

      typedef MaxCardinalitySearch<Digraph, CapacityMap, 

                                   DefProcessedMapTraits<T> > Create;

    };

    template <class H, class CR>

    struct DefHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

      static HeapCrossRef *createHeapCrossRef(const Digraph &) {

     	LEMON_ASSERT(false,"Uninitialized parameter.");

	return 0;

      }

      static Heap *createHeap(HeapCrossRef &) {

       	LEMON_ASSERT(false,"Uninitialized parameter.");

	return 0;

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting heap 

    /// and cross reference type

    ///

    /// \ref named-templ-param "Named parameter" for setting heap and cross 

    /// reference type for the algorithm.

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetHeap

      : public MaxCardinalitySearch<Digraph, CapacityMap, 

                                    DefHeapTraits<H, CR> > { 

      typedef MaxCardinalitySearch< Digraph, CapacityMap, 

                                    DefHeapTraits<H, CR> > Create;

    };

    template <class H, class CR>

    struct DefStandardHeapTraits : public Traits {

      typedef CR HeapCrossRef;

      typedef H Heap;

      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {

	return new HeapCrossRef(digraph);

      }

      static Heap *createHeap(HeapCrossRef &crossref) {

	return new Heap(crossref);

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting heap and 

    /// cross reference type with automatic allocation

    ///

    /// \ref named-templ-param "Named parameter" for setting heap and cross 

    /// reference type. It can allocate the heap and the cross reference 

    /// object if the cross reference's constructor waits for the digraph as 

    /// parameter and the heap's constructor waits for the cross reference.

    template <class H, class CR = typename Digraph::template NodeMap<int> >

    struct SetStandardHeap

      : public MaxCardinalitySearch<Digraph, CapacityMap, 

                                    DefStandardHeapTraits<H, CR> > { 

      typedef MaxCardinalitySearch<Digraph, CapacityMap, 

                                   DefStandardHeapTraits<H, CR> > 

      Create;

    };

    ///@}

  protected:

    MaxCardinalitySearch() {}

  public:      

    /// \brief Constructor.

    ///

    ///\param digraph the digraph the algorithm will run on.

    ///\param capacity the capacity map used by the algorithm.

    MaxCardinalitySearch(const Digraph& digraph,

      _graph(&digraph),

      _capacity(&capacity), local_capacity(false),

      _cardinality(0), local_cardinality(false),

      _processed(0), local_processed(false),

      _heap_cross_ref(0), local_heap_cross_ref(false),

      _heap(0), local_heap(false)

    { }

    /// \brief Destructor.

    ~MaxCardinalitySearch() {

      if(local_capacity) delete _capacity;

      if(local_cardinality) delete _cardinality;

      if(local_processed) delete _processed;

      if(local_heap_cross_ref) delete _heap_cross_ref;

      if(local_heap) delete _heap;

    }

    /// \brief Sets the capacity map.

    ///

    /// Sets the capacity map.

    /// \return <tt> (*this) </tt>

    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {

      if (local_capacity) {

	delete _capacity;

	local_capacity=false;

      }

      _capacity=&m;

      return *this;

    }

    /// \brief Returns a const reference to the capacity map.

    ///

    /// Returns a const reference to the capacity map used by

    /// the algorithm.

    const CapacityMap &capacityMap() const {

      return *_capacity;

    }

    /// \brief Sets the map storing the cardinalities calculated by the 

    /// algorithm.

    ///

    /// Sets the map storing the cardinalities calculated by the algorithm.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destuctor deallocates this

    /// automatically allocated map, of course.

    /// \return <tt> (*this) </tt>

    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {

      if(local_cardinality) {

	delete _cardinality;

	local_cardinality=false;

      }

      _cardinality = &m;

      return *this;

    }

    /// \brief Sets the map storing the processed nodes.

    ///

    /// Sets the map storing the processed nodes.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destuctor deallocates this

    /// automatically allocated map, of course.

    /// \return <tt> (*this) </tt>

    MaxCardinalitySearch &processedMap(ProcessedMap &m) 

    {

      if(local_processed) {

	delete _processed;

	local_processed=false;

      }

      _processed = &m;

      return *this;

    }

    /// \brief Returns a const reference to the cardinality map.

    ///

    /// Returns a const reference to the cardinality map used by

    /// the algorithm.

    const ProcessedMap &processedMap() const {

      return *_processed;

    }

    /// \brief Sets the heap and the cross reference used by algorithm.

    ///

    /// Sets the heap and the cross reference used by algorithm.

    /// If you don't use this function before calling \ref run(),

    /// it will allocate one. The destuctor deallocates this

    /// automatically allocated map, of course.

    /// \return <tt> (*this) </tt>

    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {

      if(local_heap_cross_ref) {

	delete _heap_cross_ref;

	local_heap_cross_ref = false;

      }

      _heap_cross_ref = &cr;

      if(local_heap) {

	delete _heap;

	local_heap = false;

      }

      _heap = &hp;

      return *this;

    }

    /// \brief Returns a const reference to the heap.

    ///

    /// Returns a const reference to the heap used by

    /// the algorithm.

    const Heap &heap() const {

      return *_heap;

    }

    /// \brief Returns a const reference to the cross reference.

    ///

    /// Returns a const reference to the cross reference

    /// of the heap.

    const HeapCrossRef &heapCrossRef() const {

      return *_heap_cross_ref;

    }

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::InArcIt InArcIt;

    void create_maps() {

      if(!_capacity) {

	local_capacity = true;

	_capacity = Traits::createCapacityMap(*_graph);

      }

      if(!_cardinality) {

	local_cardinality = true;

	_cardinality = Traits::createCardinalityMap(*_graph);

      }

      if(!_processed) {

	local_processed = true;

	_processed = Traits::createProcessedMap(*_graph);

      }

      if (!_heap_cross_ref) {

	local_heap_cross_ref = true;

	_heap_cross_ref = Traits::createHeapCrossRef(*_graph);

      }

      if (!_heap) {

	local_heap = true;

	_heap = Traits::createHeap(*_heap_cross_ref);

      }

    }

    void finalizeNodeData(Node node, Value capacity) {

      _processed->set(node, true);

      _cardinality->set(node, capacity);

    }

  public:

    /// \name Execution control

    /// The simplest way to execute the algorithm is to use

    /// one of the member functions called \ref run().

    /// \n

    /// If you need more control on the execution,

    /// first you must call \ref init(), then you can add several source nodes

    /// with \ref addSource().

    /// Finally \ref start() will perform the computation.

    ///@{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures, and clears the heap.

    void init() {

      create_maps();

      _heap->clear();

      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {

	_processed->set(it, false);

	_heap_cross_ref->set(it, Heap::PRE_HEAP);

      }

    }

    /// \brief Adds a new source node.

    /// 

    /// Adds a new source node to the priority heap.

    ///

    /// It checks if the node has not yet been added to the heap.

    void addSource(Node source, Value capacity = 0) {

      if(_heap->state(source) == Heap::PRE_HEAP) {

	_heap->push(source, capacity);

      } 

    }

    /// \brief Processes the next node in the priority heap

    ///

    /// Processes the next node in the priority heap.

    ///

    /// \return The processed node.

    ///

    /// \warning The priority heap must not be empty!

    Node processNextNode() {

      Node node = _heap->top(); 

      finalizeNodeData(node, _heap->prio());

      _heap->pop();

      for (InArcIt it(*_graph, node); it != INVALID; ++it) {