Changeset 953:d9c115e2eeaf in lemon-0.x for src/work/alpar

Timestamp:

11/01/04 18:57:19 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1333

Message:

• Named parameters and traits for Dijkstra (in src/work/alpar/dijkstra.h to be swithced to src/lemon)
• doc/named-param.dox: Doxygen page for named parameters.

File:

• src/work/alpar/dijkstra.h (modified) (10 diffs)

src/work/alpar/dijkstra.h

@@ -22 +22 @@
 ///\brief Dijkstra algorithm.
 
+#include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
 #include <lemon/invalid.h>
@@ -30 +31 @@
 /// @{
 
+  template<class GR, class LM>
+  struct DijkstraDefaultTraits
+  {
+    ///\e 
+    typedef GR Graph;
+    ///\e
+    typedef typename Graph::Node Node;
+    ///\e
+    typedef typename Graph::Edge Edge;
+    ///The type of the map that stores the edge lengths.
+
+    ///It must meet the \ref ReadMap concept.
+    ///
+    typedef LM LengthMap;
+    ///The type of the length of the edges.
+    typedef typename LM::ValueType ValueType;
+    ///The heap type used by the dijkstra algorithm.
+    typedef BinHeap<typename Graph::Node,
+                    typename LM::ValueType,
+                    typename GR::template NodeMap<int>,
+                    std::less<ValueType> > Heap;
+
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///It must meet the \ref WriteMap concept.
+    ///
+    typedef typename Graph::template NodeMap<Edge> PredMap;
+    ///
+ 
+    ///\todo Please document...
+    ///
+    static PredMap *createPredMap(const Graph &G) 
+    {
+      return new PredMap(G);
+    }
+    ///\brief The type of the map that stores the last but one
+    ///nodes of the shortest paths.
+    ///
+    ///It must meet the \ref WriteMap concept.
+    ///
+    typedef typename Graph::template NodeMap<Node> PredNodeMap;
+    ///
+ 
+    ///\todo Please document...
+    /// 
+    static PredNodeMap *createPredNodeMap(const Graph &G)
+    {
+      return new PredNodeMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///It must meet the \ref WriteMap concept.
+    ///
+    typedef typename Graph::template NodeMap<ValueType> DistMap;
+    ///
+ 
+    ///\todo Please document...
+    ///
+    static DistMap *createDistMap(const Graph &G)
+    {
+      return new DistMap(G);
+    }
+  };
+  
   ///%Dijkstra algorithm class.
 
@@ -42 +108 @@
   ///It is also possible to change the underlying priority heap.
   ///
-  ///\param GR The graph type the algorithm runs on.
+  ///\param GR The graph type the algorithm runs on. The default value is
+  ///\ref ListGraph
   ///\param LM This read-only
   ///EdgeMap
@@ -62 +129 @@
   template <typename GR,
             typename LM,
-            typename Heap>
+            typename TR>
 #else
-  template <typename GR,
+  template <typename GR=ListGraph,
             typename LM=typename GR::template EdgeMap<int>,
-            template <class,class,class,class> class Heap = BinHeap >
+            typename TR=DijkstraDefaultTraits<GR,LM> >
 #endif
   class Dijkstra{
   public:
+    typedef TR Traits;
     ///The type of the underlying graph.
     typedef GR Graph;
@@ -87 +155 @@
     ///\brief The type of the map that stores the last
     ///edges of the shortest paths.
-    typedef typename Graph::template NodeMap<Edge> PredMap;
+    typedef typename TR::PredMap PredMap;
     ///\brief The type of the map that stores the last but one
     ///nodes of the shortest paths.
-    typedef typename Graph::template NodeMap<Node> PredNodeMap;
+    typedef typename TR::PredNodeMap PredNodeMap;
     ///The type of the map that stores the dists of the nodes.
-    typedef typename Graph::template NodeMap<ValueType> DistMap;
+    typedef typename TR::DistMap DistMap;
+
+    ///The heap type used by the dijkstra algorithm.
+    typedef typename TR::Heap Heap;
 
   private:
@@ -123 +194 @@
       if(!predecessor) {
         local_predecessor = true;
-        predecessor = new PredMap(*G);
+        predecessor = Traits::createPredMap(*G);
       }
       if(!pred_node) {
         local_pred_node = true;
-        pred_node = new PredNodeMap(*G);
+        pred_node = Traits::createPredNodeMap(*G);
       }
       if(!distance) {
         local_distance = true;
-        distance = new DistMap(*G);
+        distance = Traits::createDistMap(*G);
       }
     }
     
   public :
+
+    template <class T>
+    struct SetPredMapTraits : public Traits {
+      typedef T PredMap;
+      ///\todo An exception should be thrown.
+      ///
+      static PredMap *createPredMap(const Graph &G) 
+      {
+        std::cerr << __FILE__ ":" << __LINE__ <<
+          ": error: Special maps should be manually created" << std::endl;
+        exit(1);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredMap's type
+    template <class T>
+    class SetPredMap : public Dijkstra< Graph,
+                                        LengthMap,
+                                        SetPredMapTraits<T> > { };
+    
+    template <class T>
+    struct SetPredNodeMapTraits : public Traits {
+      typedef T PredNodeMap;
+      ///\todo An exception should be thrown.
+      ///
+      static PredNodeMap *createPredNodeMap(const Graph &G) 
+      {
+        std::cerr << __FILE__ ":" << __LINE__ <<
+          ": error: Special maps should be manually created" << std::endl;
+        exit(1);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
+    template <class T>
+    class SetPredNodeMap : public Dijkstra< Graph,
+                                            LengthMap,
+                                            SetPredNodeMapTraits<T> > { };
+    
+    template <class T>
+    struct SetDistMapTraits : public Traits {
+      typedef T DistMap;
+      ///\todo An exception should be thrown.
+      ///
+      static DistMap *createDistMap(const Graph &G) 
+      {
+        std::cerr << __FILE__ ":" << __LINE__ <<
+          ": error: Special maps should be manually created" << std::endl;
+        exit(1);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting DistMap's type
+    template <class T>
+    class SetDistMap : public Dijkstra< Graph,
+                                        LengthMap,
+                                        SetDistMapTraits<T> > { };
+    
     ///Constructor.
     
@@ -238 +364 @@
       typename GR::template NodeMap<int> heap_map(*G,-1);
       
-      typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
-      std::less<ValueType> > 
-      HeapType;
-      
-      HeapType heap(heap_map);
+      Heap heap(heap_map);
       
       heap.push(s,0); 
@@ -257 +379 @@
           Node w=G->head(e); 
           switch(heap.state(w)) {
-          case HeapType::PRE_HEAP:
+          case Heap::PRE_HEAP:
             heap.push(w,oldvalue+(*length)[e]); 
             predecessor->set(w,e);
             pred_node->set(w,v);
             break;
-          case HeapType::IN_HEAP:
+          case Heap::IN_HEAP:
             if ( oldvalue+(*length)[e] < heap[w] ) {
               heap.decrease(w, oldvalue+(*length)[e]); 
@@ -269 +391 @@
             }
             break;
-          case HeapType::POST_HEAP:
+          case Heap::POST_HEAP:
             break;
           }
@@ -335 +457 @@
     
   };
+
+  ///\e
+
+  ///\e
+  ///
+  template<class TR>
+  class _Dijkstra 
+  {
+    typedef TR Traits;
+
+    ///The type of the underlying graph.
+    typedef typename TR::Graph Graph;
+    ///\e
+    typedef typename Graph::Node Node;
+    ///\e
+    typedef typename Graph::NodeIt NodeIt;
+    ///\e
+    typedef typename Graph::Edge Edge;
+    ///\e
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    ///The type of the map that stores the edge lengths.
+    typedef typename TR::LengthMap LengthMap;
+    ///The type of the length of the edges.
+    typedef typename LengthMap::ValueType ValueType;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+    ///\brief The type of the map that stores the last but one
+    ///nodes of the shortest paths.
+    typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename TR::DistMap DistMap;
+
+    ///The heap type used by the dijkstra algorithm.
+    typedef typename TR::Heap Heap;
+
+    /// Pointer to the underlying graph.
+    const Graph *G;
+    /// Pointer to the length map
+    const LengthMap *length;
+    ///Pointer to the map of predecessors edges.
+    PredMap *predecessor;
+    ///Pointer to the map of predecessors nodes.
+    PredNodeMap *pred_node;
+    ///Pointer to the map of distances.
+    DistMap *distance;
+    
+    Node source;
+    
+public:
+    _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
+                  distance(0), source(INVALID) {}
+
+    _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
+      G(&g), length(&l), predecessor(0), pred_node(0),
+                  distance(0), source(s) {}
+
+    ~_Dijkstra() 
+    {
+      Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
+      if(predecessor) Dij.setPredMap(*predecessor);
+      if(pred_node) Dij.setPredNodeMap(*pred_node);
+      if(distance) Dij.setDistMap(*distance);
+      Dij.run(source);
+    }
+
+    template<class T>
+    struct SetPredMapTraits : public Traits {typedef T PredMap;};
+    
+    ///\e
+    template<class T>
+    _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t) 
+    {
+      _Dijkstra<SetPredMapTraits<T> > r;
+      r.G=G;
+      r.length=length;
+      r.predecessor=&t;
+      r.pred_node=pred_node;
+      r.distance=distance;
+      r.source=source;
+      return r;
+    }
+    
+    template<class T>
+    struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
+    ///\e
+    template<class T>
+    _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t) 
+    {
+      _Dijkstra<SetPredNodeMapTraits<T> > r;
+      r.G=G;
+      r.length=length;
+      r.predecessor=predecessor;
+      r.pred_node=&t;
+      r.distance=distance;
+      r.source=source;
+      return r;
+    }
+    
+    template<class T>
+    struct SetDistMapTraits : public Traits {typedef T DistMap;};
+    ///\e
+    template<class T>
+    _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t) 
+    {
+      _Dijkstra<SetPredMapTraits<T> > r;
+      r.G=G;
+      r.length=length;
+      r.predecessor=predecessor;
+      r.pred_node=pred_node;
+      r.distance=&t;
+      r.source=source;
+      return r;
+    }
+    
+    ///\e
+    _Dijkstra<TR> &setSource(Node s) 
+    {
+      source=s;
+      return *this;
+    }
+    
+  };
   
+  ///\e
+
+  ///\e
+  ///
+  template<class GR, class LM>
+  _Dijkstra<DijkstraDefaultTraits<GR,LM> >
+  dijkstra(const GR &g,const LM &l,typename GR::Node s)
+  {
+    return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
+  }
+
 /// @}