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

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

Using operation traits in dijkstra

File:
1 edited

Unmodified
Added
Removed
• ## lemon/dijkstra.h

 r2476 ///\brief Dijkstra algorithm. /// ///\todo dijkstraZero() solution should be revised. #include namespace lemon { template T dijkstraZero() {return 0;} /// \brief Default OperationTraits for the Dijkstra algorithm class. /// /// It defines all computational operations and constants which are /// used in the Dijkstra algorithm. template struct DijkstraDefaultOperationTraits { /// \brief Gives back the zero value of the type. static Value zero() { return static_cast(0); } /// \brief Gives back the sum of the given two elements. static Value plus(const Value& left, const Value& right) { return left + right; } /// \brief Gives back true only if the first value less than the second. static bool less(const Value& left, const Value& right) { return left < right; } }; /// \brief Widest path OperationTraits for the Dijkstra algorithm class. /// /// It defines all computational operations and constants which are /// used in the Dijkstra algorithm for widest path computation. template struct DijkstraWidestPathOperationTraits { /// \brief Gives back the maximum value of the type. static Value zero() { return std::numeric_limits::max(); } /// \brief Gives back the maximum of the given two elements. static Value plus(const Value& left, const Value& right) { return std::min(left, right); } /// \brief Gives back true only if the first value less than the second. static bool less(const Value& left, const Value& right) { return left < right; } }; ///Default traits class of Dijkstra class. //The type of the length of the edges. typedef typename LM::Value Value; /// Operation traits for Dijkstra algorithm. /// It defines the used operation by the algorithm. /// \see DijkstraDefaultOperationTraits typedef DijkstraDefaultOperationTraits OperationTraits; /// The cross reference type used by heap. /// The cross reference type used by heap. ///Instantiates a HeapCrossRef. ///This function instantiates a \ref HeapCrossRef. ///This function instantiates a \c HeapCrossRef. /// \param G is the graph, to which we would like to define the /// HeapCrossRef. ///Instantiates a PredMap. ///This function instantiates a \ref PredMap. ///This function instantiates a \c PredMap. ///\param G is the graph, to which we would like to define the PredMap. ///\todo The graph alone may be insufficient for the initialization ///Instantiates a ProcessedMap. ///This function instantiates a \ref ProcessedMap. ///This function instantiates a \c ProcessedMap. ///\param g is the graph, to which ///we would like to define the \ref ProcessedMap ///we would like to define the \c ProcessedMap #ifdef DOXYGEN static ProcessedMap *createProcessedMap(const GR &g) #ifdef DOXYGEN template template #else template struct DefOperationTraitsTraits : public Traits { typedef T OperationTraits; }; /// \brief \ref named-templ-param "Named parameter" for setting /// OperationTraits type /// /// \ref named-templ-param "Named parameter" for setting OperationTraits /// type template struct DefOperationTraits : public Dijkstra > { typedef Dijkstra > Create; }; ///@} ///it is pushed to the heap only if either it was not in the heap ///or the shortest path found till then is shorter than \c dst. void addSource(Node s,Value dst=dijkstraZero()) void addSource(Node s,Value dst=OperationTraits::zero()) { if(_heap->state(s) != Heap::IN_HEAP) { _heap->push(s,dst); } else if((*_heap)[s]set(s,dst); _pred->set(s,INVALID); switch(_heap->state(w)) { case Heap::PRE_HEAP: _heap->push(w,oldvalue+(*length)[e]); _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); _pred->set(w,e); break; case Heap::IN_HEAP: if ( oldvalue+(*length)[e] < (*_heap)[w] ) { _heap->decrease(w, oldvalue+(*length)[e]); _pred->set(w,e); { Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { _heap->decrease(w, newvalue); _pred->set(w,e); } } break; addSource(s); start(t); return (*_pred)[t]==INVALID?dijkstraZero():(*_dist)[t]; return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; } //The type of the length of the edges. typedef typename LM::Value Value; /// Operation traits for Dijkstra algorithm. /// It defines the used operation by the algorithm. /// \see DijkstraDefaultOperationTraits typedef DijkstraDefaultOperationTraits OperationTraits; ///The heap type used by Dijkstra algorithm.
Note: See TracChangeset for help on using the changeset viewer.