1.1 --- a/src/work/alpar/dijkstra.h Mon Nov 01 07:04:52 2004 +0000
1.2 +++ b/src/work/alpar/dijkstra.h Mon Nov 01 17:57:19 2004 +0000
1.3 @@ -21,6 +21,7 @@
1.4 ///\file
1.5 ///\brief Dijkstra algorithm.
1.6
1.7 +#include <lemon/list_graph.h>
1.8 #include <lemon/bin_heap.h>
1.9 #include <lemon/invalid.h>
1.10
1.11 @@ -29,6 +30,71 @@
1.12 /// \addtogroup flowalgs
1.13 /// @{
1.14
1.15 + template<class GR, class LM>
1.16 + struct DijkstraDefaultTraits
1.17 + {
1.18 + ///\e
1.19 + typedef GR Graph;
1.20 + ///\e
1.21 + typedef typename Graph::Node Node;
1.22 + ///\e
1.23 + typedef typename Graph::Edge Edge;
1.24 + ///The type of the map that stores the edge lengths.
1.25 +
1.26 + ///It must meet the \ref ReadMap concept.
1.27 + ///
1.28 + typedef LM LengthMap;
1.29 + ///The type of the length of the edges.
1.30 + typedef typename LM::ValueType ValueType;
1.31 + ///The heap type used by the dijkstra algorithm.
1.32 + typedef BinHeap<typename Graph::Node,
1.33 + typename LM::ValueType,
1.34 + typename GR::template NodeMap<int>,
1.35 + std::less<ValueType> > Heap;
1.36 +
1.37 + ///\brief The type of the map that stores the last
1.38 + ///edges of the shortest paths.
1.39 + ///
1.40 + ///It must meet the \ref WriteMap concept.
1.41 + ///
1.42 + typedef typename Graph::template NodeMap<Edge> PredMap;
1.43 + ///
1.44 +
1.45 + ///\todo Please document...
1.46 + ///
1.47 + static PredMap *createPredMap(const Graph &G)
1.48 + {
1.49 + return new PredMap(G);
1.50 + }
1.51 + ///\brief The type of the map that stores the last but one
1.52 + ///nodes of the shortest paths.
1.53 + ///
1.54 + ///It must meet the \ref WriteMap concept.
1.55 + ///
1.56 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.57 + ///
1.58 +
1.59 + ///\todo Please document...
1.60 + ///
1.61 + static PredNodeMap *createPredNodeMap(const Graph &G)
1.62 + {
1.63 + return new PredNodeMap(G);
1.64 + }
1.65 + ///The type of the map that stores the dists of the nodes.
1.66 +
1.67 + ///It must meet the \ref WriteMap concept.
1.68 + ///
1.69 + typedef typename Graph::template NodeMap<ValueType> DistMap;
1.70 + ///
1.71 +
1.72 + ///\todo Please document...
1.73 + ///
1.74 + static DistMap *createDistMap(const Graph &G)
1.75 + {
1.76 + return new DistMap(G);
1.77 + }
1.78 + };
1.79 +
1.80 ///%Dijkstra algorithm class.
1.81
1.82 ///This class provides an efficient implementation of %Dijkstra algorithm.
1.83 @@ -41,7 +107,8 @@
1.84 ///
1.85 ///It is also possible to change the underlying priority heap.
1.86 ///
1.87 - ///\param GR The graph type the algorithm runs on.
1.88 + ///\param GR The graph type the algorithm runs on. The default value is
1.89 + ///\ref ListGraph
1.90 ///\param LM This read-only
1.91 ///EdgeMap
1.92 ///determines the
1.93 @@ -61,14 +128,15 @@
1.94 #ifdef DOXYGEN
1.95 template <typename GR,
1.96 typename LM,
1.97 - typename Heap>
1.98 + typename TR>
1.99 #else
1.100 - template <typename GR,
1.101 + template <typename GR=ListGraph,
1.102 typename LM=typename GR::template EdgeMap<int>,
1.103 - template <class,class,class,class> class Heap = BinHeap >
1.104 + typename TR=DijkstraDefaultTraits<GR,LM> >
1.105 #endif
1.106 class Dijkstra{
1.107 public:
1.108 + typedef TR Traits;
1.109 ///The type of the underlying graph.
1.110 typedef GR Graph;
1.111 ///\e
1.112 @@ -86,12 +154,15 @@
1.113 typedef LM LengthMap;
1.114 ///\brief The type of the map that stores the last
1.115 ///edges of the shortest paths.
1.116 - typedef typename Graph::template NodeMap<Edge> PredMap;
1.117 + typedef typename TR::PredMap PredMap;
1.118 ///\brief The type of the map that stores the last but one
1.119 ///nodes of the shortest paths.
1.120 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
1.121 + typedef typename TR::PredNodeMap PredNodeMap;
1.122 ///The type of the map that stores the dists of the nodes.
1.123 - typedef typename Graph::template NodeMap<ValueType> DistMap;
1.124 + typedef typename TR::DistMap DistMap;
1.125 +
1.126 + ///The heap type used by the dijkstra algorithm.
1.127 + typedef typename TR::Heap Heap;
1.128
1.129 private:
1.130 /// Pointer to the underlying graph.
1.131 @@ -122,19 +193,74 @@
1.132 {
1.133 if(!predecessor) {
1.134 local_predecessor = true;
1.135 - predecessor = new PredMap(*G);
1.136 + predecessor = Traits::createPredMap(*G);
1.137 }
1.138 if(!pred_node) {
1.139 local_pred_node = true;
1.140 - pred_node = new PredNodeMap(*G);
1.141 + pred_node = Traits::createPredNodeMap(*G);
1.142 }
1.143 if(!distance) {
1.144 local_distance = true;
1.145 - distance = new DistMap(*G);
1.146 + distance = Traits::createDistMap(*G);
1.147 }
1.148 }
1.149
1.150 public :
1.151 +
1.152 + template <class T>
1.153 + struct SetPredMapTraits : public Traits {
1.154 + typedef T PredMap;
1.155 + ///\todo An exception should be thrown.
1.156 + ///
1.157 + static PredMap *createPredMap(const Graph &G)
1.158 + {
1.159 + std::cerr << __FILE__ ":" << __LINE__ <<
1.160 + ": error: Special maps should be manually created" << std::endl;
1.161 + exit(1);
1.162 + }
1.163 + };
1.164 + ///\ref named-templ-param "Named parameter" for setting PredMap's type
1.165 + template <class T>
1.166 + class SetPredMap : public Dijkstra< Graph,
1.167 + LengthMap,
1.168 + SetPredMapTraits<T> > { };
1.169 +
1.170 + template <class T>
1.171 + struct SetPredNodeMapTraits : public Traits {
1.172 + typedef T PredNodeMap;
1.173 + ///\todo An exception should be thrown.
1.174 + ///
1.175 + static PredNodeMap *createPredNodeMap(const Graph &G)
1.176 + {
1.177 + std::cerr << __FILE__ ":" << __LINE__ <<
1.178 + ": error: Special maps should be manually created" << std::endl;
1.179 + exit(1);
1.180 + }
1.181 + };
1.182 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
1.183 + template <class T>
1.184 + class SetPredNodeMap : public Dijkstra< Graph,
1.185 + LengthMap,
1.186 + SetPredNodeMapTraits<T> > { };
1.187 +
1.188 + template <class T>
1.189 + struct SetDistMapTraits : public Traits {
1.190 + typedef T DistMap;
1.191 + ///\todo An exception should be thrown.
1.192 + ///
1.193 + static DistMap *createDistMap(const Graph &G)
1.194 + {
1.195 + std::cerr << __FILE__ ":" << __LINE__ <<
1.196 + ": error: Special maps should be manually created" << std::endl;
1.197 + exit(1);
1.198 + }
1.199 + };
1.200 + ///\ref named-templ-param "Named parameter" for setting DistMap's type
1.201 + template <class T>
1.202 + class SetDistMap : public Dijkstra< Graph,
1.203 + LengthMap,
1.204 + SetDistMapTraits<T> > { };
1.205 +
1.206 ///Constructor.
1.207
1.208 ///\param _G the graph the algorithm will run on.
1.209 @@ -237,11 +363,7 @@
1.210
1.211 typename GR::template NodeMap<int> heap_map(*G,-1);
1.212
1.213 - typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
1.214 - std::less<ValueType> >
1.215 - HeapType;
1.216 -
1.217 - HeapType heap(heap_map);
1.218 + Heap heap(heap_map);
1.219
1.220 heap.push(s,0);
1.221
1.222 @@ -256,19 +378,19 @@
1.223 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.224 Node w=G->head(e);
1.225 switch(heap.state(w)) {
1.226 - case HeapType::PRE_HEAP:
1.227 + case Heap::PRE_HEAP:
1.228 heap.push(w,oldvalue+(*length)[e]);
1.229 predecessor->set(w,e);
1.230 pred_node->set(w,v);
1.231 break;
1.232 - case HeapType::IN_HEAP:
1.233 + case Heap::IN_HEAP:
1.234 if ( oldvalue+(*length)[e] < heap[w] ) {
1.235 heap.decrease(w, oldvalue+(*length)[e]);
1.236 predecessor->set(w,e);
1.237 pred_node->set(w,v);
1.238 }
1.239 break;
1.240 - case HeapType::POST_HEAP:
1.241 + case Heap::POST_HEAP:
1.242 break;
1.243 }
1.244 }
1.245 @@ -334,7 +456,142 @@
1.246 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.247
1.248 };
1.249 +
1.250 + ///\e
1.251 +
1.252 + ///\e
1.253 + ///
1.254 + template<class TR>
1.255 + class _Dijkstra
1.256 + {
1.257 + typedef TR Traits;
1.258 +
1.259 + ///The type of the underlying graph.
1.260 + typedef typename TR::Graph Graph;
1.261 + ///\e
1.262 + typedef typename Graph::Node Node;
1.263 + ///\e
1.264 + typedef typename Graph::NodeIt NodeIt;
1.265 + ///\e
1.266 + typedef typename Graph::Edge Edge;
1.267 + ///\e
1.268 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.269 +
1.270 + ///The type of the map that stores the edge lengths.
1.271 + typedef typename TR::LengthMap LengthMap;
1.272 + ///The type of the length of the edges.
1.273 + typedef typename LengthMap::ValueType ValueType;
1.274 + ///\brief The type of the map that stores the last
1.275 + ///edges of the shortest paths.
1.276 + typedef typename TR::PredMap PredMap;
1.277 + ///\brief The type of the map that stores the last but one
1.278 + ///nodes of the shortest paths.
1.279 + typedef typename TR::PredNodeMap PredNodeMap;
1.280 + ///The type of the map that stores the dists of the nodes.
1.281 + typedef typename TR::DistMap DistMap;
1.282 +
1.283 + ///The heap type used by the dijkstra algorithm.
1.284 + typedef typename TR::Heap Heap;
1.285 +
1.286 + /// Pointer to the underlying graph.
1.287 + const Graph *G;
1.288 + /// Pointer to the length map
1.289 + const LengthMap *length;
1.290 + ///Pointer to the map of predecessors edges.
1.291 + PredMap *predecessor;
1.292 + ///Pointer to the map of predecessors nodes.
1.293 + PredNodeMap *pred_node;
1.294 + ///Pointer to the map of distances.
1.295 + DistMap *distance;
1.296 +
1.297 + Node source;
1.298 +
1.299 +public:
1.300 + _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
1.301 + distance(0), source(INVALID) {}
1.302 +
1.303 + _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
1.304 + G(&g), length(&l), predecessor(0), pred_node(0),
1.305 + distance(0), source(s) {}
1.306 +
1.307 + ~_Dijkstra()
1.308 + {
1.309 + Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
1.310 + if(predecessor) Dij.setPredMap(*predecessor);
1.311 + if(pred_node) Dij.setPredNodeMap(*pred_node);
1.312 + if(distance) Dij.setDistMap(*distance);
1.313 + Dij.run(source);
1.314 + }
1.315 +
1.316 + template<class T>
1.317 + struct SetPredMapTraits : public Traits {typedef T PredMap;};
1.318 +
1.319 + ///\e
1.320 + template<class T>
1.321 + _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t)
1.322 + {
1.323 + _Dijkstra<SetPredMapTraits<T> > r;
1.324 + r.G=G;
1.325 + r.length=length;
1.326 + r.predecessor=&t;
1.327 + r.pred_node=pred_node;
1.328 + r.distance=distance;
1.329 + r.source=source;
1.330 + return r;
1.331 + }
1.332 +
1.333 + template<class T>
1.334 + struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
1.335 + ///\e
1.336 + template<class T>
1.337 + _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t)
1.338 + {
1.339 + _Dijkstra<SetPredNodeMapTraits<T> > r;
1.340 + r.G=G;
1.341 + r.length=length;
1.342 + r.predecessor=predecessor;
1.343 + r.pred_node=&t;
1.344 + r.distance=distance;
1.345 + r.source=source;
1.346 + return r;
1.347 + }
1.348 +
1.349 + template<class T>
1.350 + struct SetDistMapTraits : public Traits {typedef T DistMap;};
1.351 + ///\e
1.352 + template<class T>
1.353 + _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t)
1.354 + {
1.355 + _Dijkstra<SetPredMapTraits<T> > r;
1.356 + r.G=G;
1.357 + r.length=length;
1.358 + r.predecessor=predecessor;
1.359 + r.pred_node=pred_node;
1.360 + r.distance=&t;
1.361 + r.source=source;
1.362 + return r;
1.363 + }
1.364 +
1.365 + ///\e
1.366 + _Dijkstra<TR> &setSource(Node s)
1.367 + {
1.368 + source=s;
1.369 + return *this;
1.370 + }
1.371 +
1.372 + };
1.373
1.374 + ///\e
1.375 +
1.376 + ///\e
1.377 + ///
1.378 + template<class GR, class LM>
1.379 + _Dijkstra<DijkstraDefaultTraits<GR,LM> >
1.380 + dijkstra(const GR &g,const LM &l,typename GR::Node s)
1.381 + {
1.382 + return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
1.383 + }
1.384 +
1.385 /// @}
1.386
1.387 } //END OF NAMESPACE LEMON