Changeset 954:5b1ffef43d4c in lemon-0.x for src/work

Timestamp:

11/01/04 20:00:19 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Improved docs.

File:

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

src/work/alpar/dijkstra.h

@@ -31 +31 @@
 /// @{
 
+  ///Default traits class of Dijkstra class.
+
+  ///Default traits class of Dijkstra class.
+  ///\param GR Graph type.
+  ///\param LM Type of length map.
   template<class GR, class LM>
   struct DijkstraDefaultTraits
   {
-    ///\e 
+    ///The graph type the algorithm runs on. 
     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.
 
@@ -45 +46 @@
     ///
     typedef LM LengthMap;
-    ///The type of the length of the edges.
+    //The type of the length of the edges.
     typedef typename LM::ValueType ValueType;
-    ///The heap type used by the dijkstra algorithm.
+    ///The heap type used by Dijkstra algorithm.
     typedef BinHeap<typename Graph::Node,
                     typename LM::ValueType,
@@ -58 +59 @@
     ///It must meet the \ref WriteMap concept.
     ///
-    typedef typename Graph::template NodeMap<Edge> PredMap;
-    ///
+    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
  
     ///\todo Please document...
     ///
-    static PredMap *createPredMap(const Graph &G) 
+    static PredMap *createPredMap(const GR &G) 
     {
       return new PredMap(G);
@@ -72 +73 @@
     ///It must meet the \ref WriteMap concept.
     ///
-    typedef typename Graph::template NodeMap<Node> PredNodeMap;
-    ///
+    typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
+    ///Instantiates a PredNodeMap.
  
     ///\todo Please document...
     /// 
-    static PredNodeMap *createPredNodeMap(const Graph &G)
+    static PredNodeMap *createPredNodeMap(const GR &G)
     {
       return new PredNodeMap(G);
@@ -85 +86 @@
     ///It must meet the \ref WriteMap concept.
     ///
-    typedef typename Graph::template NodeMap<ValueType> DistMap;
-    ///
+    typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
+    ///Instantiates a DistMap.
  
     ///\todo Please document...
     ///
-    static DistMap *createDistMap(const Graph &G)
+    static DistMap *createDistMap(const GR &G)
     {
       return new DistMap(G);
@@ -109 +110 @@
   ///
   ///\param GR The graph type the algorithm runs on. The default value is
-  ///\ref ListGraph
+  ///\ref ListGraph. The value of GR is not used directly by %Dijsktra, it
+  ///is only passed to \ref DijkstraDefaultTraits.
   ///\param LM This read-only
   ///EdgeMap
@@ -116 +118 @@
   ///may involve in relatively time consuming process to compute the edge
   ///length if it is necessary. The default map type is
-  ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
-  ///\param Heap The heap type used by the %Dijkstra
-  ///algorithm. The default
-  ///is using \ref BinHeap "binary heap".
+  ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
+  ///The value of LM is not used directly by %Dijsktra, it
+  ///is only passed to \ref DijkstraDefaultTraits.
+  ///\param TR Traits class to set various data types used by the algorithm.
+  ///The default traits class is
+  ///\ref DijkstraDefaultTraits<GR,LM> "DijkstraDefaultTraits<GR,LM>".
+  ///See \ref DijkstraDefaultTraits for the documentation of
+  ///a Dijkstra traits class.
   ///
   ///\author Jacint Szabo and Alpar Juttner
   ///\todo We need a typedef-names should be standardized. (-:
-  ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
-  ///should not be fixed. (Problematic to solve).
 
 #ifdef DOXYGEN
@@ -139 +143 @@
     typedef TR Traits;
     ///The type of the underlying graph.
-    typedef GR Graph;
+    typedef typename TR::Graph Graph;
     ///\e
     typedef typename Graph::Node Node;
@@ -150 +154 @@
     
     ///The type of the length of the edges.
-    typedef typename LM::ValueType ValueType;
+    typedef typename TR::LengthMap::ValueType ValueType;
     ///The type of the map that stores the edge lengths.
-    typedef LM LengthMap;
+    typedef typename TR::LengthMap LengthMap;
     ///\brief The type of the map that stores the last
     ///edges of the shortest paths.
@@ -161 +165 @@
     ///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;
@@ -169 +172 @@
     const Graph *G;
     /// Pointer to the length map
-    const LM *length;
+    const LengthMap *length;
     ///Pointer to the map of predecessors edges.
     PredMap *predecessor;
@@ -220 +223 @@
       }
     };
-    ///\ref named-templ-param "Named parameter" for setting PredMap's type
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+
+    ///\ingroup flowalgs 
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
     template <class T>
     class SetPredMap : public Dijkstra< Graph,
@@ -238 +244 @@
       }
     };
-    ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
+    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+
+    ///\ingroup flowalgs 
+    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
     template <class T>
     class SetPredNodeMap : public Dijkstra< Graph,
@@ -256 +265 @@
       }
     };
-    ///\ref named-templ-param "Named parameter" for setting DistMap's type
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+
+    ///\ingroup flowalgs 
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
     template <class T>
     class SetDistMap : public Dijkstra< Graph,
@@ -266 +278 @@
     ///\param _G the graph the algorithm will run on.
     ///\param _length the length map used by the algorithm.
-    Dijkstra(const Graph& _G, const LM& _length) :
+    Dijkstra(const Graph& _G, const LengthMap& _length) :
       G(&_G), length(&_length),
       predecessor(NULL), local_predecessor(false),
@@ -285 +297 @@
     ///Sets the length map.
     ///\return <tt> (*this) </tt>
-    Dijkstra &setLengthMap(const LM &m) 
+    Dijkstra &setLengthMap(const LengthMap &m) 
     {
       length = &m;
@@ -350 +362 @@
   ///- The shortest path tree.
   ///- The distance of each node from the root.
-    
+  ///\todo heap_map's type could also be in the traits class.
     void run(Node s) {
       
@@ -362 +374 @@
       }
       
-      typename GR::template NodeMap<int> heap_map(*G,-1);
+      typename Graph::template NodeMap<int> heap_map(*G,-1);
       
       Heap heap(heap_map);
@@ -584 +596 @@
   ///\e
 
-  ///\e
+  ///\todo Please document...
   ///
   template<class GR, class LM>