COIN-OR::LEMON - Graph Library

Changeset 2537:4a2091b1796a in lemon-0.x for lemon


Ignore:
Timestamp:
12/10/07 17:33:37 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3414
Message:

Using operation traits in dijkstra

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r2476 r2537  
    2424///\brief Dijkstra algorithm.
    2525///
    26 ///\todo dijkstraZero() solution should be revised.
    2726
    2827#include <lemon/list_graph.h>
     
    3635namespace lemon {
    3736
    38   template<class T> T dijkstraZero() {return 0;}
     37  /// \brief Default OperationTraits for the Dijkstra algorithm class.
     38  /// 
     39  /// It defines all computational operations and constants which are
     40  /// used in the Dijkstra algorithm.
     41  template <typename Value>
     42  struct DijkstraDefaultOperationTraits {
     43    /// \brief Gives back the zero value of the type.
     44    static Value zero() {
     45      return static_cast<Value>(0);
     46    }
     47    /// \brief Gives back the sum of the given two elements.
     48    static Value plus(const Value& left, const Value& right) {
     49      return left + right;
     50    }
     51    /// \brief Gives back true only if the first value less than the second.
     52    static bool less(const Value& left, const Value& right) {
     53      return left < right;
     54    }
     55  };
     56
     57  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
     58  /// 
     59  /// It defines all computational operations and constants which are
     60  /// used in the Dijkstra algorithm for widest path computation.
     61  template <typename Value>
     62  struct DijkstraWidestPathOperationTraits {
     63    /// \brief Gives back the maximum value of the type.
     64    static Value zero() {
     65      return std::numeric_limits<Value>::max();
     66    }
     67    /// \brief Gives back the maximum of the given two elements.
     68    static Value plus(const Value& left, const Value& right) {
     69      return std::min(left, right);
     70    }
     71    /// \brief Gives back true only if the first value less than the second.
     72    static bool less(const Value& left, const Value& right) {
     73      return left < right;
     74    }
     75  };
    3976 
    4077  ///Default traits class of Dijkstra class.
     
    5592    //The type of the length of the edges.
    5693    typedef typename LM::Value Value;
     94    /// Operation traits for Dijkstra algorithm.
     95
     96    /// It defines the used operation by the algorithm.
     97    /// \see DijkstraDefaultOperationTraits
     98    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    5799    /// The cross reference type used by heap.
     100
    58101
    59102    /// The cross reference type used by heap.
     
    62105    ///Instantiates a HeapCrossRef.
    63106
    64     ///This function instantiates a \ref HeapCrossRef.
     107    ///This function instantiates a \c HeapCrossRef.
    65108    /// \param G is the graph, to which we would like to define the
    66109    /// HeapCrossRef.
     
    93136    ///Instantiates a PredMap.
    94137 
    95     ///This function instantiates a \ref PredMap.
     138    ///This function instantiates a \c PredMap.
    96139    ///\param G is the graph, to which we would like to define the PredMap.
    97140    ///\todo The graph alone may be insufficient for the initialization
     
    112155    ///Instantiates a ProcessedMap.
    113156 
    114     ///This function instantiates a \ref ProcessedMap.
     157    ///This function instantiates a \c ProcessedMap.
    115158    ///\param g is the graph, to which
    116     ///we would like to define the \ref ProcessedMap
     159    ///we would like to define the \c ProcessedMap
    117160#ifdef DOXYGEN
    118161    static ProcessedMap *createProcessedMap(const GR &g)
     
    171214
    172215#ifdef DOXYGEN
    173   template <typename GR,
    174             typename LM,
    175             typename TR>
     216  template <typename GR, typename LM, typename TR>
    176217#else
    177218  template <typename GR=ListGraph,
     
    221262    ///The heap type used by the dijkstra algorithm.
    222263    typedef typename TR::Heap Heap;
     264    ///The operation traits.
     265    typedef typename TR::OperationTraits OperationTraits;
    223266  private:
    224267    /// Pointer to the underlying graph.
     
    404447      Create;
    405448    };
     449
     450    template <class T>
     451    struct DefOperationTraitsTraits : public Traits {
     452      typedef T OperationTraits;
     453    };
     454   
     455    /// \brief \ref named-templ-param "Named parameter" for setting
     456    /// OperationTraits type
     457    ///
     458    /// \ref named-templ-param "Named parameter" for setting OperationTraits
     459    /// type
     460    template <class T>
     461    struct DefOperationTraits
     462      : public Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > {
     463      typedef Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> >
     464      Create;
     465    };
    406466   
    407467    ///@}
     
    550610    ///it is pushed to the heap only if either it was not in the heap
    551611    ///or the shortest path found till then is shorter than \c dst.
    552     void addSource(Node s,Value dst=dijkstraZero<Value>())
     612    void addSource(Node s,Value dst=OperationTraits::zero())
    553613    {
    554614      if(_heap->state(s) != Heap::IN_HEAP) {
    555615        _heap->push(s,dst);
    556       } else if((*_heap)[s]<dst) {
     616      } else if(OperationTraits::less((*_heap)[s], dst)) {
    557617        _heap->set(s,dst);
    558618        _pred->set(s,INVALID);
     
    578638        switch(_heap->state(w)) {
    579639        case Heap::PRE_HEAP:
    580           _heap->push(w,oldvalue+(*length)[e]);
     640          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
    581641          _pred->set(w,e);
    582642          break;
    583643        case Heap::IN_HEAP:
    584           if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
    585             _heap->decrease(w, oldvalue+(*length)[e]);
    586             _pred->set(w,e);
     644          {
     645            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
     646            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
     647              _heap->decrease(w, newvalue);
     648              _pred->set(w,e);
     649            }
    587650          }
    588651          break;
     
    715778      addSource(s);
    716779      start(t);
    717       return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
     780      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
    718781    }
    719782   
     
    827890    //The type of the length of the edges.
    828891    typedef typename LM::Value Value;
     892    /// Operation traits for Dijkstra algorithm.
     893
     894    /// It defines the used operation by the algorithm.
     895    /// \see DijkstraDefaultOperationTraits
     896    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    829897    ///The heap type used by Dijkstra algorithm.
    830898
Note: See TracChangeset for help on using the changeset viewer.