Changeset 2537:4a2091b1796a in lemon-0.x

Timestamp:

12/10/07 17:33:37 (17 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:

• lemon/dijkstra.h (modified) (13 diffs)

lemon/dijkstra.h

@@ -24 +24 @@
 ///\brief Dijkstra algorithm.
 ///
-///\todo dijkstraZero() solution should be revised.
 
 #include <lemon/list_graph.h>
@@ -36 +35 @@
 namespace lemon {
 
-  template<class T> 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 <typename Value>
+  struct DijkstraDefaultOperationTraits {
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(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 <typename Value>
+  struct DijkstraWidestPathOperationTraits {
+    /// \brief Gives back the maximum value of the type.
+    static Value zero() {
+      return std::numeric_limits<Value>::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.
@@ -55 +92 @@
     //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<Value> OperationTraits;
     /// The cross reference type used by heap.
+
 
     /// The cross reference type used by heap.
@@ -62 +105 @@
     ///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.
@@ -93 +136 @@
     ///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
@@ -112 +155 @@
     ///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)
@@ -171 +214 @@
 
 #ifdef DOXYGEN
-  template <typename GR,
-            typename LM,
-            typename TR>
+  template <typename GR, typename LM, typename TR>
 #else
   template <typename GR=ListGraph,
@@ -221 +262 @@
     ///The heap type used by the dijkstra algorithm.
     typedef typename TR::Heap Heap;
+    ///The operation traits.
+    typedef typename TR::OperationTraits OperationTraits;
   private:
     /// Pointer to the underlying graph.
@@ -404 +447 @@
       Create;
     };
+
+    template <class T>
+    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 <class T>
+    struct DefOperationTraits
+      : public Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> >
+      Create;
+    };
     
     ///@}
@@ -550 +610 @@
     ///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<Value>())
+    void addSource(Node s,Value dst=OperationTraits::zero())
     {
       if(_heap->state(s) != Heap::IN_HEAP) {
         _heap->push(s,dst);
-      } else if((*_heap)[s]<dst) {
+      } else if(OperationTraits::less((*_heap)[s], dst)) {
         _heap->set(s,dst);
         _pred->set(s,INVALID);
@@ -578 +638 @@
         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;
@@ -715 +778 @@
       addSource(s);
       start(t);
-      return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
+      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
     }
     
@@ -827 +890 @@
     //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<Value> OperationTraits;
     ///The heap type used by Dijkstra algorithm.