# HG changeset patch
# User alpar
# Date 1099331839 0
# Node ID d9c115e2eeaf428d0922d34dae92cc61f7495bdb
# Parent  fa65d57f1930402f0a8653af0dfb93e7bdd99055
- 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.

diff -r fa65d57f1930 -r d9c115e2eeaf doc/Doxyfile
--- a/doc/Doxyfile	Mon Nov 01 07:04:52 2004 +0000
+++ b/doc/Doxyfile	Mon Nov 01 17:57:19 2004 +0000
@@ -425,6 +425,7 @@
 
 INPUT                  = mainpage.dox \
                          graphs.dox \
+                         named-param.dox \
                          maps.dox \
                          coding_style.dox \
                          groups.dox \
diff -r fa65d57f1930 -r d9c115e2eeaf doc/named-param.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/named-param.dox	Mon Nov 01 17:57:19 2004 +0000
@@ -0,0 +1,5 @@
+/*!
+\page named-param Named Parameters
+
+
+*/
diff -r fa65d57f1930 -r d9c115e2eeaf src/work/alpar/dijkstra.h
--- a/src/work/alpar/dijkstra.h	Mon Nov 01 07:04:52 2004 +0000
+++ b/src/work/alpar/dijkstra.h	Mon Nov 01 17:57:19 2004 +0000
@@ -21,6 +21,7 @@
 ///\file
 ///\brief Dijkstra algorithm.
 
+#include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
 #include <lemon/invalid.h>
 
@@ -29,6 +30,71 @@
 /// \addtogroup flowalgs
 /// @{
 
+  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.
 
   ///This class provides an efficient implementation of %Dijkstra algorithm.
@@ -41,7 +107,8 @@
   ///
   ///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
   ///determines the
@@ -61,14 +128,15 @@
 #ifdef DOXYGEN
   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;
     ///\e
@@ -86,12 +154,15 @@
     typedef LM LengthMap;
     ///\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:
     /// Pointer to the underlying graph.
@@ -122,19 +193,74 @@
     {
       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.
     
     ///\param _G the graph the algorithm will run on.
@@ -237,11 +363,7 @@
       
       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); 
       
@@ -256,19 +378,19 @@
 	for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
 	  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]); 
 	      predecessor->set(w,e);
 	      pred_node->set(w,v);
 	    }
 	    break;
-	  case HeapType::POST_HEAP:
+	  case Heap::POST_HEAP:
 	    break;
 	  }
 	}
@@ -334,7 +456,142 @@
     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     
   };
+
+  ///\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);
+  }
+
 /// @}
   
 } //END OF NAMESPACE LEMON