COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
08/09/13 11:28:17 (6 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1271:fb1c7da561ce, 1381:e0ccc1f0268f
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_cardinality_search.h

    r1129 r1270  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    2222
    2323/// \ingroup search
    24 /// \file 
     24/// \file
    2525/// \brief Maximum cardinality search in undirected digraphs.
    2626
     
    4242  template <typename GR, typename CAP>
    4343  struct MaxCardinalitySearchDefaultTraits {
    44     /// The digraph type the algorithm runs on. 
     44    /// The digraph type the algorithm runs on.
    4545    typedef GR Digraph;
    4646
     
    5151
    5252      static CapacityMap *createCapacityMap(const Digraph& g) {
    53         return new CapacityMap(g);
     53        return new CapacityMap(g);
    5454      }
    5555    };
     
    6161
    6262      static CapacityMap *createCapacityMap(const Digraph&) {
    63         return new CapacityMap;
     63        return new CapacityMap;
    6464      }
    6565    };
     
    9191    /// \brief Instantiates a HeapCrossRef.
    9292    ///
    93     /// This function instantiates a \ref HeapCrossRef. 
    94     /// \param digraph is the digraph, to which we would like to define the 
     93    /// This function instantiates a \ref HeapCrossRef.
     94    /// \param digraph is the digraph, to which we would like to define the
    9595    /// HeapCrossRef.
    9696    static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
    9797      return new HeapCrossRef(digraph);
    9898    }
    99    
     99
    100100    template <typename CapacityMap>
    101101    struct HeapSelector {
    102102      template <typename Value, typename Ref>
    103       struct Selector { 
     103      struct Selector {
    104104        typedef BinHeap<Value, Ref, std::greater<Value> > Heap;
    105105      };
     
    129129    /// \brief Instantiates a Heap.
    130130    ///
    131     /// This function instantiates a \ref Heap. 
     131    /// This function instantiates a \ref Heap.
    132132    /// \param crossref The cross reference of the heap.
    133133    static Heap *createHeap(HeapCrossRef& crossref) {
     
    144144    /// \brief Instantiates a ProcessedMap.
    145145    ///
    146     /// This function instantiates a \ref ProcessedMap. 
     146    /// This function instantiates a \ref ProcessedMap.
    147147    /// \param digraph is the digraph, to which
    148148    /// we would like to define the \ref ProcessedMap
     
    157157
    158158    /// \brief The type of the map that stores the cardinalities of the nodes.
    159     /// 
     159    ///
    160160    /// The type of the map that stores the cardinalities of the nodes.
    161161    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
     
    164164    /// \brief Instantiates a CardinalityMap.
    165165    ///
    166     /// This function instantiates a \ref CardinalityMap. 
    167     /// \param digraph is the digraph, to which we would like to define the \ref 
     166    /// This function instantiates a \ref CardinalityMap.
     167    /// \param digraph is the digraph, to which we would like to define the \ref
    168168    /// CardinalityMap
    169169    static CardinalityMap *createCardinalityMap(const Digraph &digraph) {
     
    173173
    174174  };
    175  
     175
    176176  /// \ingroup search
    177177  ///
    178178  /// \brief Maximum Cardinality Search algorithm class.
    179179  ///
    180   /// This class provides an efficient implementation of Maximum Cardinality 
    181   /// Search algorithm. The maximum cardinality search first chooses any 
     180  /// This class provides an efficient implementation of Maximum Cardinality
     181  /// Search algorithm. The maximum cardinality search first chooses any
    182182  /// node of the digraph. Then every time it chooses one unprocessed node
    183183  /// with maximum cardinality, i.e the sum of capacities on out arcs to the nodes
     
    187187
    188188  /// The arc capacities are passed to the algorithm using a
    189   /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
     189  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
    190190  /// kind of capacity.
    191191  ///
    192   /// The type of the capacity is determined by the \ref 
     192  /// The type of the capacity is determined by the \ref
    193193  /// concepts::ReadMap::Value "Value" of the capacity map.
    194194  ///
     
    197197  ///
    198198  /// \param GR The digraph type the algorithm runs on. The value of
    199   /// Digraph is not used directly by the search algorithm, it 
     199  /// Digraph is not used directly by the search algorithm, it
    200200  /// is only passed to \ref MaxCardinalitySearchDefaultTraits.
    201   /// \param CAP This read-only ArcMap determines the capacities of 
     201  /// \param CAP This read-only ArcMap determines the capacities of
    202202  /// the arcs. It is read once for each arc, so the map may involve in
    203203  /// relatively time consuming process to compute the arc capacity if
    204204  /// it is necessary. The default map type is \ref
    205205  /// ConstMap "ConstMap<concepts::Digraph::Arc, Const<int,1> >". The value
    206   /// of CapacityMap is not used directly by search algorithm, it is only 
    207   /// passed to \ref MaxCardinalitySearchDefaultTraits. 
    208   /// \param TR Traits class to set various data types used by the 
    209   /// algorithm.  The default traits class is 
    210   /// \ref MaxCardinalitySearchDefaultTraits 
    211   /// "MaxCardinalitySearchDefaultTraits<GR, CAP>". 
    212   /// See \ref MaxCardinalitySearchDefaultTraits 
     206  /// of CapacityMap is not used directly by search algorithm, it is only
     207  /// passed to \ref MaxCardinalitySearchDefaultTraits.
     208  /// \param TR Traits class to set various data types used by the
     209  /// algorithm.  The default traits class is
     210  /// \ref MaxCardinalitySearchDefaultTraits
     211  /// "MaxCardinalitySearchDefaultTraits<GR, CAP>".
     212  /// See \ref MaxCardinalitySearchDefaultTraits
    213213  /// for the documentation of a MaxCardinalitySearch traits class.
    214214
     
    216216  template <typename GR, typename CAP, typename TR>
    217217#else
    218   template <typename GR, typename CAP = 
    219             ConstMap<typename GR::Arc, Const<int,1> >,
    220             typename TR =
     218  template <typename GR, typename CAP =
     219            ConstMap<typename GR::Arc, Const<int,1> >,
     220            typename TR =
    221221            MaxCardinalitySearchDefaultTraits<GR, CAP> >
    222222#endif
     
    227227    ///The type of the underlying digraph.
    228228    typedef typename Traits::Digraph Digraph;
    229    
     229
    230230    ///The type of the capacity of the arcs.
    231231    typedef typename Traits::CapacityMap::Value Value;
     
    267267
    268268    typedef MaxCardinalitySearch Create;
    269  
     269
    270270    ///\name Named template parameters
    271271
     
    276276      typedef T CapacityMap;
    277277      static CapacityMap *createCapacityMap(const Digraph &) {
    278         LEMON_ASSERT(false,"Uninitialized parameter.");
    279         return 0;
    280       }
    281     };
    282     /// \brief \ref named-templ-param "Named parameter" for setting 
     278               LEMON_ASSERT(false,"Uninitialized parameter.");
     279        return 0;
     280      }
     281    };
     282    /// \brief \ref named-templ-param "Named parameter" for setting
    283283    /// CapacityMap type
    284284    ///
     
    286286    /// for the algorithm.
    287287    template <class T>
    288     struct SetCapacityMap 
    289       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    290                                     DefCapacityMapTraits<T> > { 
    291       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     288    struct SetCapacityMap
     289      : public MaxCardinalitySearch<Digraph, CapacityMap,
     290                                    DefCapacityMapTraits<T> > {
     291      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    292292                                   DefCapacityMapTraits<T> > Create;
    293293    };
     
    296296    struct DefCardinalityMapTraits : public Traits {
    297297      typedef T CardinalityMap;
    298       static CardinalityMap *createCardinalityMap(const Digraph &) 
     298      static CardinalityMap *createCardinalityMap(const Digraph &)
    299299      {
    300         LEMON_ASSERT(false,"Uninitialized parameter.");
    301         return 0;
    302       }
    303     };
    304     /// \brief \ref named-templ-param "Named parameter" for setting 
     300        LEMON_ASSERT(false,"Uninitialized parameter.");
     301        return 0;
     302      }
     303    };
     304    /// \brief \ref named-templ-param "Named parameter" for setting
    305305    /// CardinalityMap type
    306306    ///
    307     /// \ref named-templ-param "Named parameter" for setting CardinalityMap 
     307    /// \ref named-templ-param "Named parameter" for setting CardinalityMap
    308308    /// type for the algorithm.
    309309    template <class T>
    310     struct SetCardinalityMap 
    311       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    312                                     DefCardinalityMapTraits<T> > { 
    313       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     310    struct SetCardinalityMap
     311      : public MaxCardinalitySearch<Digraph, CapacityMap,
     312                                    DefCardinalityMapTraits<T> > {
     313      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    314314                                   DefCardinalityMapTraits<T> > Create;
    315315    };
    316    
     316
    317317    template <class T>
    318318    struct DefProcessedMapTraits : public Traits {
    319319      typedef T ProcessedMap;
    320320      static ProcessedMap *createProcessedMap(const Digraph &) {
    321         LEMON_ASSERT(false,"Uninitialized parameter.");
    322         return 0;
    323       }
    324     };
    325     /// \brief \ref named-templ-param "Named parameter" for setting 
     321               LEMON_ASSERT(false,"Uninitialized parameter.");
     322        return 0;
     323      }
     324    };
     325    /// \brief \ref named-templ-param "Named parameter" for setting
    326326    /// ProcessedMap type
    327327    ///
     
    329329    /// for the algorithm.
    330330    template <class T>
    331     struct SetProcessedMap 
    332       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    333                                     DefProcessedMapTraits<T> > { 
    334       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
     331    struct SetProcessedMap
     332      : public MaxCardinalitySearch<Digraph, CapacityMap,
     333                                    DefProcessedMapTraits<T> > {
     334      typedef MaxCardinalitySearch<Digraph, CapacityMap,
    335335                                   DefProcessedMapTraits<T> > Create;
    336336    };
    337    
     337
    338338    template <class H, class CR>
    339339    struct DefHeapTraits : public Traits {
     
    341341      typedef H Heap;
    342342      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
    343         LEMON_ASSERT(false,"Uninitialized parameter.");
    344         return 0;
     343             LEMON_ASSERT(false,"Uninitialized parameter.");
     344        return 0;
    345345      }
    346346      static Heap *createHeap(HeapCrossRef &) {
    347         LEMON_ASSERT(false,"Uninitialized parameter.");
    348         return 0;
    349       }
    350     };
    351     /// \brief \ref named-templ-param "Named parameter" for setting heap 
     347               LEMON_ASSERT(false,"Uninitialized parameter.");
     348        return 0;
     349      }
     350    };
     351    /// \brief \ref named-templ-param "Named parameter" for setting heap
    352352    /// and cross reference type
    353353    ///
    354     /// \ref named-templ-param "Named parameter" for setting heap and cross 
     354    /// \ref named-templ-param "Named parameter" for setting heap and cross
    355355    /// reference type for the algorithm.
    356356    template <class H, class CR = typename Digraph::template NodeMap<int> >
    357357    struct SetHeap
    358       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    359                                     DefHeapTraits<H, CR> > { 
    360       typedef MaxCardinalitySearch< Digraph, CapacityMap, 
     358      : public MaxCardinalitySearch<Digraph, CapacityMap,
     359                                    DefHeapTraits<H, CR> > {
     360      typedef MaxCardinalitySearch< Digraph, CapacityMap,
    361361                                    DefHeapTraits<H, CR> > Create;
    362362    };
     
    367367      typedef H Heap;
    368368      static HeapCrossRef *createHeapCrossRef(const Digraph &digraph) {
    369         return new HeapCrossRef(digraph);
     369        return new HeapCrossRef(digraph);
    370370      }
    371371      static Heap *createHeap(HeapCrossRef &crossref) {
    372         return new Heap(crossref);
    373       }
    374     };
    375 
    376     /// \brief \ref named-templ-param "Named parameter" for setting heap and 
     372        return new Heap(crossref);
     373      }
     374    };
     375
     376    /// \brief \ref named-templ-param "Named parameter" for setting heap and
    377377    /// cross reference type with automatic allocation
    378378    ///
    379     /// \ref named-templ-param "Named parameter" for setting heap and cross 
    380     /// reference type. It can allocate the heap and the cross reference 
    381     /// object if the cross reference's constructor waits for the digraph as 
     379    /// \ref named-templ-param "Named parameter" for setting heap and cross
     380    /// reference type. It can allocate the heap and the cross reference
     381    /// object if the cross reference's constructor waits for the digraph as
    382382    /// parameter and the heap's constructor waits for the cross reference.
    383383    template <class H, class CR = typename Digraph::template NodeMap<int> >
    384384    struct SetStandardHeap
    385       : public MaxCardinalitySearch<Digraph, CapacityMap, 
    386                                     DefStandardHeapTraits<H, CR> > { 
    387       typedef MaxCardinalitySearch<Digraph, CapacityMap, 
    388                                    DefStandardHeapTraits<H, CR> > 
     385      : public MaxCardinalitySearch<Digraph, CapacityMap,
     386                                    DefStandardHeapTraits<H, CR> > {
     387      typedef MaxCardinalitySearch<Digraph, CapacityMap,
     388                                   DefStandardHeapTraits<H, CR> >
    389389      Create;
    390390    };
    391    
     391
    392392    ///@}
    393393
     
    397397    MaxCardinalitySearch() {}
    398398
    399   public:     
    400    
     399  public:
     400
    401401    /// \brief Constructor.
    402402    ///
     
    404404    ///\param capacity the capacity map used by the algorithm.
    405405    MaxCardinalitySearch(const Digraph& digraph,
    406                         const CapacityMap& capacity) :
     406                        const CapacityMap& capacity) :
    407407      _graph(&digraph),
    408408      _capacity(&capacity), local_capacity(false),
     
    442442    MaxCardinalitySearch &capacityMap(const CapacityMap &m) {
    443443      if (local_capacity) {
    444         delete _capacity;
    445         local_capacity=false;
     444        delete _capacity;
     445        local_capacity=false;
    446446      }
    447447      _capacity=&m;
     
    457457    }
    458458
    459     /// \brief Sets the map storing the cardinalities calculated by the 
     459    /// \brief Sets the map storing the cardinalities calculated by the
    460460    /// algorithm.
    461461    ///
     
    467467    MaxCardinalitySearch &cardinalityMap(CardinalityMap &m) {
    468468      if(local_cardinality) {
    469         delete _cardinality;
    470         local_cardinality=false;
     469        delete _cardinality;
     470        local_cardinality=false;
    471471      }
    472472      _cardinality = &m;
     
    481481    /// automatically allocated map, of course.
    482482    /// \return <tt> (*this) </tt>
    483     MaxCardinalitySearch &processedMap(ProcessedMap &m) 
     483    MaxCardinalitySearch &processedMap(ProcessedMap &m)
    484484    {
    485485      if(local_processed) {
    486         delete _processed;
    487         local_processed=false;
     486        delete _processed;
     487        local_processed=false;
    488488      }
    489489      _processed = &m;
     
    508508    MaxCardinalitySearch &heap(Heap& hp, HeapCrossRef &cr) {
    509509      if(local_heap_cross_ref) {
    510         delete _heap_cross_ref;
    511         local_heap_cross_ref = false;
     510        delete _heap_cross_ref;
     511        local_heap_cross_ref = false;
    512512      }
    513513      _heap_cross_ref = &cr;
    514514      if(local_heap) {
    515         delete _heap;
    516         local_heap = false;
     515        delete _heap;
     516        local_heap = false;
    517517      }
    518518      _heap = &hp;
     
    545545    void create_maps() {
    546546      if(!_capacity) {
    547         local_capacity = true;
    548         _capacity = Traits::createCapacityMap(*_graph);
     547        local_capacity = true;
     548        _capacity = Traits::createCapacityMap(*_graph);
    549549      }
    550550      if(!_cardinality) {
    551         local_cardinality = true;
    552         _cardinality = Traits::createCardinalityMap(*_graph);
     551        local_cardinality = true;
     552        _cardinality = Traits::createCardinalityMap(*_graph);
    553553      }
    554554      if(!_processed) {
    555         local_processed = true;
    556         _processed = Traits::createProcessedMap(*_graph);
     555        local_processed = true;
     556        _processed = Traits::createProcessedMap(*_graph);
    557557      }
    558558      if (!_heap_cross_ref) {
    559         local_heap_cross_ref = true;
    560         _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
     559        local_heap_cross_ref = true;
     560        _heap_cross_ref = Traits::createHeapCrossRef(*_graph);
    561561      }
    562562      if (!_heap) {
    563         local_heap = true;
    564         _heap = Traits::createHeap(*_heap_cross_ref);
    565       }
    566     }
    567    
     563        local_heap = true;
     564        _heap = Traits::createHeap(*_heap_cross_ref);
     565      }
     566    }
     567
    568568    void finalizeNodeData(Node node, Value capacity) {
    569569      _processed->set(node, true);
     
    590590      _heap->clear();
    591591      for (NodeIt it(*_graph) ; it != INVALID ; ++it) {
    592         _processed->set(it, false);
    593         _heap_cross_ref->set(it, Heap::PRE_HEAP);
    594       }
    595     }
    596    
     592        _processed->set(it, false);
     593        _heap_cross_ref->set(it, Heap::PRE_HEAP);
     594      }
     595    }
     596
    597597    /// \brief Adds a new source node.
    598     /// 
     598    ///
    599599    /// Adds a new source node to the priority heap.
    600600    ///
     
    602602    void addSource(Node source, Value capacity = 0) {
    603603      if(_heap->state(source) == Heap::PRE_HEAP) {
    604         _heap->push(source, capacity);
    605       } 
    606     }
    607    
     604        _heap->push(source, capacity);
     605      }
     606    }
     607
    608608    /// \brief Processes the next node in the priority heap
    609609    ///
     
    614614    /// \warning The priority heap must not be empty!
    615615    Node processNextNode() {
    616       Node node = _heap->top(); 
     616      Node node = _heap->top();
    617617      finalizeNodeData(node, _heap->prio());
    618618      _heap->pop();
    619      
     619
    620620      for (InArcIt it(*_graph, node); it != INVALID; ++it) {
    621         Node source = _graph->source(it);
    622         switch (_heap->state(source)) {
    623         case Heap::PRE_HEAP:
    624           _heap->push(source, (*_capacity)[it]);
    625           break;
    626         case Heap::IN_HEAP:
    627           _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
    628           break;
    629         case Heap::POST_HEAP:
    630           break;
    631         }
     621        Node source = _graph->source(it);
     622        switch (_heap->state(source)) {
     623        case Heap::PRE_HEAP:
     624          _heap->push(source, (*_capacity)[it]);
     625          break;
     626        case Heap::IN_HEAP:
     627          _heap->decrease(source, (*_heap)[source] + (*_capacity)[it]);
     628          break;
     629        case Heap::POST_HEAP:
     630          break;
     631        }
    632632      }
    633633      return node;
     
    638638    /// Next node to be processed.
    639639    ///
    640     /// \return The next node to be processed or INVALID if the 
     640    /// \return The next node to be processed or INVALID if the
    641641    /// priority heap is empty.
    642     Node nextNode() { 
     642    Node nextNode() {
    643643      return !_heap->empty() ? _heap->top() : INVALID;
    644644    }
    645  
     645
    646646    /// \brief Returns \c false if there are nodes
    647647    /// to be processed in the priority heap
     
    650650    /// to be processed in the priority heap
    651651    bool emptyQueue() { return _heap->empty(); }
    652     /// \brief Returns the number of the nodes to be processed 
     652    /// \brief Returns the number of the nodes to be processed
    653653    /// in the priority heap
    654654    ///
    655655    /// Returns the number of the nodes to be processed in the priority heap
    656656    int emptySize() { return _heap->size(); }
    657    
     657
    658658    /// \brief Executes the algorithm.
    659659    ///
     
    663663    /// with addSource() before using this function.
    664664    ///
    665     /// This method runs the Maximum Cardinality Search algorithm from the 
     665    /// This method runs the Maximum Cardinality Search algorithm from the
    666666    /// source node(s).
    667667    void start() {
    668668      while ( !_heap->empty() ) processNextNode();
    669669    }
    670    
     670
    671671    /// \brief Executes the algorithm until \c dest is reached.
    672672    ///
     
    676676    /// with addSource() before using this function.
    677677    ///
    678     /// This method runs the %MaxCardinalitySearch algorithm from the source 
     678    /// This method runs the %MaxCardinalitySearch algorithm from the source
    679679    /// nodes.
    680680    void start(Node dest) {
     
    682682      if ( !_heap->empty() ) finalizeNodeData(_heap->top(), _heap->prio());
    683683    }
    684    
     684
    685685    /// \brief Executes the algorithm until a condition is met.
    686686    ///
     
    697697      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
    698698    }
    699    
     699
    700700    /// \brief Runs the maximum cardinality search algorithm from node \c s.
    701701    ///
    702     /// This method runs the %MaxCardinalitySearch algorithm from a root 
     702    /// This method runs the %MaxCardinalitySearch algorithm from a root
    703703    /// node \c s.
    704704    ///
     
    715715    }
    716716
    717     /// \brief Runs the maximum cardinality search algorithm for the 
     717    /// \brief Runs the maximum cardinality search algorithm for the
    718718    /// whole digraph.
    719719    ///
    720     /// This method runs the %MaxCardinalitySearch algorithm from all 
     720    /// This method runs the %MaxCardinalitySearch algorithm from all
    721721    /// unprocessed node of the digraph.
    722722    ///
     
    740740      }
    741741    }
    742    
     742
    743743    ///@}
    744744
    745745    /// \name Query Functions
    746     /// The results of the maximum cardinality search algorithm can be 
     746    /// The results of the maximum cardinality search algorithm can be
    747747    /// obtained using these functions.
    748748    /// \n
    749     /// Before the use of these functions, either run() or start() must be 
     749    /// Before the use of these functions, either run() or start() must be
    750750    /// called.
    751    
     751
    752752    ///@{
    753753
     
    768768    /// \brief Returns a reference to the NodeMap of cardinalities.
    769769    ///
    770     /// Returns a reference to the NodeMap of cardinalities. \pre \ref run() 
     770    /// Returns a reference to the NodeMap of cardinalities. \pre \ref run()
    771771    /// must be called before using this function.
    772772    const CardinalityMap &cardinalityMap() const { return *_cardinality;}
    773  
     773
    774774    /// \brief Checks if a node is reachable from the root.
    775775    ///
     
    785785    /// \pre \ref run() must be called before using this function.
    786786    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
    787    
     787
    788788    ///@}
    789789  };
Note: See TracChangeset for help on using the changeset viewer.