1.1 --- a/src/work/alpar/dijkstra.h Mon Nov 01 17:57:19 2004 +0000
1.2 +++ b/src/work/alpar/dijkstra.h Mon Nov 01 19:00:19 2004 +0000
1.3 @@ -30,23 +30,24 @@
1.4 /// \addtogroup flowalgs
1.5 /// @{
1.6
1.7 + ///Default traits class of Dijkstra class.
1.8 +
1.9 + ///Default traits class of Dijkstra class.
1.10 + ///\param GR Graph type.
1.11 + ///\param LM Type of length map.
1.12 template<class GR, class LM>
1.13 struct DijkstraDefaultTraits
1.14 {
1.15 - ///\e
1.16 + ///The graph type the algorithm runs on.
1.17 typedef GR Graph;
1.18 - ///\e
1.19 - typedef typename Graph::Node Node;
1.20 - ///\e
1.21 - typedef typename Graph::Edge Edge;
1.22 ///The type of the map that stores the edge lengths.
1.23
1.24 ///It must meet the \ref ReadMap concept.
1.25 ///
1.26 typedef LM LengthMap;
1.27 - ///The type of the length of the edges.
1.28 + //The type of the length of the edges.
1.29 typedef typename LM::ValueType ValueType;
1.30 - ///The heap type used by the dijkstra algorithm.
1.31 + ///The heap type used by Dijkstra algorithm.
1.32 typedef BinHeap<typename Graph::Node,
1.33 typename LM::ValueType,
1.34 typename GR::template NodeMap<int>,
1.35 @@ -57,12 +58,12 @@
1.36 ///
1.37 ///It must meet the \ref WriteMap concept.
1.38 ///
1.39 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.40 - ///
1.41 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.42 + ///Instantiates a PredMap.
1.43
1.44 ///\todo Please document...
1.45 ///
1.46 - static PredMap *createPredMap(const Graph &G)
1.47 + static PredMap *createPredMap(const GR &G)
1.48 {
1.49 return new PredMap(G);
1.50 }
1.51 @@ -71,12 +72,12 @@
1.52 ///
1.53 ///It must meet the \ref WriteMap concept.
1.54 ///
1.55 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.56 - ///
1.57 + typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
1.58 + ///Instantiates a PredNodeMap.
1.59
1.60 ///\todo Please document...
1.61 ///
1.62 - static PredNodeMap *createPredNodeMap(const Graph &G)
1.63 + static PredNodeMap *createPredNodeMap(const GR &G)
1.64 {
1.65 return new PredNodeMap(G);
1.66 }
1.67 @@ -84,12 +85,12 @@
1.68
1.69 ///It must meet the \ref WriteMap concept.
1.70 ///
1.71 - typedef typename Graph::template NodeMap<ValueType> DistMap;
1.72 - ///
1.73 + typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
1.74 + ///Instantiates a DistMap.
1.75
1.76 ///\todo Please document...
1.77 ///
1.78 - static DistMap *createDistMap(const Graph &G)
1.79 + static DistMap *createDistMap(const GR &G)
1.80 {
1.81 return new DistMap(G);
1.82 }
1.83 @@ -108,22 +109,25 @@
1.84 ///It is also possible to change the underlying priority heap.
1.85 ///
1.86 ///\param GR The graph type the algorithm runs on. The default value is
1.87 - ///\ref ListGraph
1.88 + ///\ref ListGraph. The value of GR is not used directly by %Dijsktra, it
1.89 + ///is only passed to \ref DijkstraDefaultTraits.
1.90 ///\param LM This read-only
1.91 ///EdgeMap
1.92 ///determines the
1.93 ///lengths of the edges. It is read once for each edge, so the map
1.94 ///may involve in relatively time consuming process to compute the edge
1.95 ///length if it is necessary. The default map type is
1.96 - ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>"
1.97 - ///\param Heap The heap type used by the %Dijkstra
1.98 - ///algorithm. The default
1.99 - ///is using \ref BinHeap "binary heap".
1.100 + ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
1.101 + ///The value of LM is not used directly by %Dijsktra, it
1.102 + ///is only passed to \ref DijkstraDefaultTraits.
1.103 + ///\param TR Traits class to set various data types used by the algorithm.
1.104 + ///The default traits class is
1.105 + ///\ref DijkstraDefaultTraits<GR,LM> "DijkstraDefaultTraits<GR,LM>".
1.106 + ///See \ref DijkstraDefaultTraits for the documentation of
1.107 + ///a Dijkstra traits class.
1.108 ///
1.109 ///\author Jacint Szabo and Alpar Juttner
1.110 ///\todo We need a typedef-names should be standardized. (-:
1.111 - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
1.112 - ///should not be fixed. (Problematic to solve).
1.113
1.114 #ifdef DOXYGEN
1.115 template <typename GR,
1.116 @@ -138,7 +142,7 @@
1.117 public:
1.118 typedef TR Traits;
1.119 ///The type of the underlying graph.
1.120 - typedef GR Graph;
1.121 + typedef typename TR::Graph Graph;
1.122 ///\e
1.123 typedef typename Graph::Node Node;
1.124 ///\e
1.125 @@ -149,9 +153,9 @@
1.126 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.127
1.128 ///The type of the length of the edges.
1.129 - typedef typename LM::ValueType ValueType;
1.130 + typedef typename TR::LengthMap::ValueType ValueType;
1.131 ///The type of the map that stores the edge lengths.
1.132 - typedef LM LengthMap;
1.133 + typedef typename TR::LengthMap LengthMap;
1.134 ///\brief The type of the map that stores the last
1.135 ///edges of the shortest paths.
1.136 typedef typename TR::PredMap PredMap;
1.137 @@ -160,7 +164,6 @@
1.138 typedef typename TR::PredNodeMap PredNodeMap;
1.139 ///The type of the map that stores the dists of the nodes.
1.140 typedef typename TR::DistMap DistMap;
1.141 -
1.142 ///The heap type used by the dijkstra algorithm.
1.143 typedef typename TR::Heap Heap;
1.144
1.145 @@ -168,7 +171,7 @@
1.146 /// Pointer to the underlying graph.
1.147 const Graph *G;
1.148 /// Pointer to the length map
1.149 - const LM *length;
1.150 + const LengthMap *length;
1.151 ///Pointer to the map of predecessors edges.
1.152 PredMap *predecessor;
1.153 ///Indicates if \ref predecessor is locally allocated (\c true) or not.
1.154 @@ -219,7 +222,10 @@
1.155 exit(1);
1.156 }
1.157 };
1.158 - ///\ref named-templ-param "Named parameter" for setting PredMap's type
1.159 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.160 +
1.161 + ///\ingroup flowalgs
1.162 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.163 template <class T>
1.164 class SetPredMap : public Dijkstra< Graph,
1.165 LengthMap,
1.166 @@ -237,7 +243,10 @@
1.167 exit(1);
1.168 }
1.169 };
1.170 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
1.171 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.172 +
1.173 + ///\ingroup flowalgs
1.174 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.175 template <class T>
1.176 class SetPredNodeMap : public Dijkstra< Graph,
1.177 LengthMap,
1.178 @@ -255,7 +264,10 @@
1.179 exit(1);
1.180 }
1.181 };
1.182 - ///\ref named-templ-param "Named parameter" for setting DistMap's type
1.183 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.184 +
1.185 + ///\ingroup flowalgs
1.186 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.187 template <class T>
1.188 class SetDistMap : public Dijkstra< Graph,
1.189 LengthMap,
1.190 @@ -265,7 +277,7 @@
1.191
1.192 ///\param _G the graph the algorithm will run on.
1.193 ///\param _length the length map used by the algorithm.
1.194 - Dijkstra(const Graph& _G, const LM& _length) :
1.195 + Dijkstra(const Graph& _G, const LengthMap& _length) :
1.196 G(&_G), length(&_length),
1.197 predecessor(NULL), local_predecessor(false),
1.198 pred_node(NULL), local_pred_node(false),
1.199 @@ -284,7 +296,7 @@
1.200
1.201 ///Sets the length map.
1.202 ///\return <tt> (*this) </tt>
1.203 - Dijkstra &setLengthMap(const LM &m)
1.204 + Dijkstra &setLengthMap(const LengthMap &m)
1.205 {
1.206 length = &m;
1.207 return *this;
1.208 @@ -349,7 +361,7 @@
1.209 ///shortest path to each node. The algorithm computes
1.210 ///- The shortest path tree.
1.211 ///- The distance of each node from the root.
1.212 -
1.213 + ///\todo heap_map's type could also be in the traits class.
1.214 void run(Node s) {
1.215
1.216 init_maps();
1.217 @@ -361,7 +373,7 @@
1.218 pred_node->set(u,INVALID);
1.219 }
1.220
1.221 - typename GR::template NodeMap<int> heap_map(*G,-1);
1.222 + typename Graph::template NodeMap<int> heap_map(*G,-1);
1.223
1.224 Heap heap(heap_map);
1.225
1.226 @@ -583,7 +595,7 @@
1.227
1.228 ///\e
1.229
1.230 - ///\e
1.231 + ///\todo Please document...
1.232 ///
1.233 template<class GR, class LM>
1.234 _Dijkstra<DijkstraDefaultTraits<GR,LM> >