1.1 --- a/doc/Doxyfile Mon Nov 01 07:04:52 2004 +0000
1.2 +++ b/doc/Doxyfile Mon Nov 01 17:57:19 2004 +0000
1.3 @@ -425,6 +425,7 @@
1.4
1.5 INPUT = mainpage.dox \
1.6 graphs.dox \
1.7 + named-param.dox \
1.8 maps.dox \
1.9 coding_style.dox \
1.10 groups.dox \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/doc/named-param.dox Mon Nov 01 17:57:19 2004 +0000
2.3 @@ -0,0 +1,5 @@
2.4 +/*!
2.5 +\page named-param Named Parameters
2.6 +
2.7 +
2.8 +*/
3.1 --- a/src/work/alpar/dijkstra.h Mon Nov 01 07:04:52 2004 +0000
3.2 +++ b/src/work/alpar/dijkstra.h Mon Nov 01 17:57:19 2004 +0000
3.3 @@ -21,6 +21,7 @@
3.4 ///\file
3.5 ///\brief Dijkstra algorithm.
3.6
3.7 +#include <lemon/list_graph.h>
3.8 #include <lemon/bin_heap.h>
3.9 #include <lemon/invalid.h>
3.10
3.11 @@ -29,6 +30,71 @@
3.12 /// \addtogroup flowalgs
3.13 /// @{
3.14
3.15 + template<class GR, class LM>
3.16 + struct DijkstraDefaultTraits
3.17 + {
3.18 + ///\e
3.19 + typedef GR Graph;
3.20 + ///\e
3.21 + typedef typename Graph::Node Node;
3.22 + ///\e
3.23 + typedef typename Graph::Edge Edge;
3.24 + ///The type of the map that stores the edge lengths.
3.25 +
3.26 + ///It must meet the \ref ReadMap concept.
3.27 + ///
3.28 + typedef LM LengthMap;
3.29 + ///The type of the length of the edges.
3.30 + typedef typename LM::ValueType ValueType;
3.31 + ///The heap type used by the dijkstra algorithm.
3.32 + typedef BinHeap<typename Graph::Node,
3.33 + typename LM::ValueType,
3.34 + typename GR::template NodeMap<int>,
3.35 + std::less<ValueType> > Heap;
3.36 +
3.37 + ///\brief The type of the map that stores the last
3.38 + ///edges of the shortest paths.
3.39 + ///
3.40 + ///It must meet the \ref WriteMap concept.
3.41 + ///
3.42 + typedef typename Graph::template NodeMap<Edge> PredMap;
3.43 + ///
3.44 +
3.45 + ///\todo Please document...
3.46 + ///
3.47 + static PredMap *createPredMap(const Graph &G)
3.48 + {
3.49 + return new PredMap(G);
3.50 + }
3.51 + ///\brief The type of the map that stores the last but one
3.52 + ///nodes of the shortest paths.
3.53 + ///
3.54 + ///It must meet the \ref WriteMap concept.
3.55 + ///
3.56 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
3.57 + ///
3.58 +
3.59 + ///\todo Please document...
3.60 + ///
3.61 + static PredNodeMap *createPredNodeMap(const Graph &G)
3.62 + {
3.63 + return new PredNodeMap(G);
3.64 + }
3.65 + ///The type of the map that stores the dists of the nodes.
3.66 +
3.67 + ///It must meet the \ref WriteMap concept.
3.68 + ///
3.69 + typedef typename Graph::template NodeMap<ValueType> DistMap;
3.70 + ///
3.71 +
3.72 + ///\todo Please document...
3.73 + ///
3.74 + static DistMap *createDistMap(const Graph &G)
3.75 + {
3.76 + return new DistMap(G);
3.77 + }
3.78 + };
3.79 +
3.80 ///%Dijkstra algorithm class.
3.81
3.82 ///This class provides an efficient implementation of %Dijkstra algorithm.
3.83 @@ -41,7 +107,8 @@
3.84 ///
3.85 ///It is also possible to change the underlying priority heap.
3.86 ///
3.87 - ///\param GR The graph type the algorithm runs on.
3.88 + ///\param GR The graph type the algorithm runs on. The default value is
3.89 + ///\ref ListGraph
3.90 ///\param LM This read-only
3.91 ///EdgeMap
3.92 ///determines the
3.93 @@ -61,14 +128,15 @@
3.94 #ifdef DOXYGEN
3.95 template <typename GR,
3.96 typename LM,
3.97 - typename Heap>
3.98 + typename TR>
3.99 #else
3.100 - template <typename GR,
3.101 + template <typename GR=ListGraph,
3.102 typename LM=typename GR::template EdgeMap<int>,
3.103 - template <class,class,class,class> class Heap = BinHeap >
3.104 + typename TR=DijkstraDefaultTraits<GR,LM> >
3.105 #endif
3.106 class Dijkstra{
3.107 public:
3.108 + typedef TR Traits;
3.109 ///The type of the underlying graph.
3.110 typedef GR Graph;
3.111 ///\e
3.112 @@ -86,12 +154,15 @@
3.113 typedef LM LengthMap;
3.114 ///\brief The type of the map that stores the last
3.115 ///edges of the shortest paths.
3.116 - typedef typename Graph::template NodeMap<Edge> PredMap;
3.117 + typedef typename TR::PredMap PredMap;
3.118 ///\brief The type of the map that stores the last but one
3.119 ///nodes of the shortest paths.
3.120 - typedef typename Graph::template NodeMap<Node> PredNodeMap;
3.121 + typedef typename TR::PredNodeMap PredNodeMap;
3.122 ///The type of the map that stores the dists of the nodes.
3.123 - typedef typename Graph::template NodeMap<ValueType> DistMap;
3.124 + typedef typename TR::DistMap DistMap;
3.125 +
3.126 + ///The heap type used by the dijkstra algorithm.
3.127 + typedef typename TR::Heap Heap;
3.128
3.129 private:
3.130 /// Pointer to the underlying graph.
3.131 @@ -122,19 +193,74 @@
3.132 {
3.133 if(!predecessor) {
3.134 local_predecessor = true;
3.135 - predecessor = new PredMap(*G);
3.136 + predecessor = Traits::createPredMap(*G);
3.137 }
3.138 if(!pred_node) {
3.139 local_pred_node = true;
3.140 - pred_node = new PredNodeMap(*G);
3.141 + pred_node = Traits::createPredNodeMap(*G);
3.142 }
3.143 if(!distance) {
3.144 local_distance = true;
3.145 - distance = new DistMap(*G);
3.146 + distance = Traits::createDistMap(*G);
3.147 }
3.148 }
3.149
3.150 public :
3.151 +
3.152 + template <class T>
3.153 + struct SetPredMapTraits : public Traits {
3.154 + typedef T PredMap;
3.155 + ///\todo An exception should be thrown.
3.156 + ///
3.157 + static PredMap *createPredMap(const Graph &G)
3.158 + {
3.159 + std::cerr << __FILE__ ":" << __LINE__ <<
3.160 + ": error: Special maps should be manually created" << std::endl;
3.161 + exit(1);
3.162 + }
3.163 + };
3.164 + ///\ref named-templ-param "Named parameter" for setting PredMap's type
3.165 + template <class T>
3.166 + class SetPredMap : public Dijkstra< Graph,
3.167 + LengthMap,
3.168 + SetPredMapTraits<T> > { };
3.169 +
3.170 + template <class T>
3.171 + struct SetPredNodeMapTraits : public Traits {
3.172 + typedef T PredNodeMap;
3.173 + ///\todo An exception should be thrown.
3.174 + ///
3.175 + static PredNodeMap *createPredNodeMap(const Graph &G)
3.176 + {
3.177 + std::cerr << __FILE__ ":" << __LINE__ <<
3.178 + ": error: Special maps should be manually created" << std::endl;
3.179 + exit(1);
3.180 + }
3.181 + };
3.182 + ///\ref named-templ-param "Named parameter" for setting PredNodeMap's type
3.183 + template <class T>
3.184 + class SetPredNodeMap : public Dijkstra< Graph,
3.185 + LengthMap,
3.186 + SetPredNodeMapTraits<T> > { };
3.187 +
3.188 + template <class T>
3.189 + struct SetDistMapTraits : public Traits {
3.190 + typedef T DistMap;
3.191 + ///\todo An exception should be thrown.
3.192 + ///
3.193 + static DistMap *createDistMap(const Graph &G)
3.194 + {
3.195 + std::cerr << __FILE__ ":" << __LINE__ <<
3.196 + ": error: Special maps should be manually created" << std::endl;
3.197 + exit(1);
3.198 + }
3.199 + };
3.200 + ///\ref named-templ-param "Named parameter" for setting DistMap's type
3.201 + template <class T>
3.202 + class SetDistMap : public Dijkstra< Graph,
3.203 + LengthMap,
3.204 + SetDistMapTraits<T> > { };
3.205 +
3.206 ///Constructor.
3.207
3.208 ///\param _G the graph the algorithm will run on.
3.209 @@ -237,11 +363,7 @@
3.210
3.211 typename GR::template NodeMap<int> heap_map(*G,-1);
3.212
3.213 - typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
3.214 - std::less<ValueType> >
3.215 - HeapType;
3.216 -
3.217 - HeapType heap(heap_map);
3.218 + Heap heap(heap_map);
3.219
3.220 heap.push(s,0);
3.221
3.222 @@ -256,19 +378,19 @@
3.223 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
3.224 Node w=G->head(e);
3.225 switch(heap.state(w)) {
3.226 - case HeapType::PRE_HEAP:
3.227 + case Heap::PRE_HEAP:
3.228 heap.push(w,oldvalue+(*length)[e]);
3.229 predecessor->set(w,e);
3.230 pred_node->set(w,v);
3.231 break;
3.232 - case HeapType::IN_HEAP:
3.233 + case Heap::IN_HEAP:
3.234 if ( oldvalue+(*length)[e] < heap[w] ) {
3.235 heap.decrease(w, oldvalue+(*length)[e]);
3.236 predecessor->set(w,e);
3.237 pred_node->set(w,v);
3.238 }
3.239 break;
3.240 - case HeapType::POST_HEAP:
3.241 + case Heap::POST_HEAP:
3.242 break;
3.243 }
3.244 }
3.245 @@ -334,7 +456,142 @@
3.246 bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
3.247
3.248 };
3.249 +
3.250 + ///\e
3.251 +
3.252 + ///\e
3.253 + ///
3.254 + template<class TR>
3.255 + class _Dijkstra
3.256 + {
3.257 + typedef TR Traits;
3.258 +
3.259 + ///The type of the underlying graph.
3.260 + typedef typename TR::Graph Graph;
3.261 + ///\e
3.262 + typedef typename Graph::Node Node;
3.263 + ///\e
3.264 + typedef typename Graph::NodeIt NodeIt;
3.265 + ///\e
3.266 + typedef typename Graph::Edge Edge;
3.267 + ///\e
3.268 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.269 +
3.270 + ///The type of the map that stores the edge lengths.
3.271 + typedef typename TR::LengthMap LengthMap;
3.272 + ///The type of the length of the edges.
3.273 + typedef typename LengthMap::ValueType ValueType;
3.274 + ///\brief The type of the map that stores the last
3.275 + ///edges of the shortest paths.
3.276 + typedef typename TR::PredMap PredMap;
3.277 + ///\brief The type of the map that stores the last but one
3.278 + ///nodes of the shortest paths.
3.279 + typedef typename TR::PredNodeMap PredNodeMap;
3.280 + ///The type of the map that stores the dists of the nodes.
3.281 + typedef typename TR::DistMap DistMap;
3.282 +
3.283 + ///The heap type used by the dijkstra algorithm.
3.284 + typedef typename TR::Heap Heap;
3.285 +
3.286 + /// Pointer to the underlying graph.
3.287 + const Graph *G;
3.288 + /// Pointer to the length map
3.289 + const LengthMap *length;
3.290 + ///Pointer to the map of predecessors edges.
3.291 + PredMap *predecessor;
3.292 + ///Pointer to the map of predecessors nodes.
3.293 + PredNodeMap *pred_node;
3.294 + ///Pointer to the map of distances.
3.295 + DistMap *distance;
3.296 +
3.297 + Node source;
3.298 +
3.299 +public:
3.300 + _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0),
3.301 + distance(0), source(INVALID) {}
3.302 +
3.303 + _Dijkstra(const Graph &g,const LengthMap &l, Node s) :
3.304 + G(&g), length(&l), predecessor(0), pred_node(0),
3.305 + distance(0), source(s) {}
3.306 +
3.307 + ~_Dijkstra()
3.308 + {
3.309 + Dijkstra<Graph,LengthMap,TR> Dij(*G,*length);
3.310 + if(predecessor) Dij.setPredMap(*predecessor);
3.311 + if(pred_node) Dij.setPredNodeMap(*pred_node);
3.312 + if(distance) Dij.setDistMap(*distance);
3.313 + Dij.run(source);
3.314 + }
3.315 +
3.316 + template<class T>
3.317 + struct SetPredMapTraits : public Traits {typedef T PredMap;};
3.318 +
3.319 + ///\e
3.320 + template<class T>
3.321 + _Dijkstra<SetPredMapTraits<T> > setPredMap(const T &t)
3.322 + {
3.323 + _Dijkstra<SetPredMapTraits<T> > r;
3.324 + r.G=G;
3.325 + r.length=length;
3.326 + r.predecessor=&t;
3.327 + r.pred_node=pred_node;
3.328 + r.distance=distance;
3.329 + r.source=source;
3.330 + return r;
3.331 + }
3.332 +
3.333 + template<class T>
3.334 + struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;};
3.335 + ///\e
3.336 + template<class T>
3.337 + _Dijkstra<SetPredNodeMapTraits<T> > setPredNodeMap(const T &t)
3.338 + {
3.339 + _Dijkstra<SetPredNodeMapTraits<T> > r;
3.340 + r.G=G;
3.341 + r.length=length;
3.342 + r.predecessor=predecessor;
3.343 + r.pred_node=&t;
3.344 + r.distance=distance;
3.345 + r.source=source;
3.346 + return r;
3.347 + }
3.348 +
3.349 + template<class T>
3.350 + struct SetDistMapTraits : public Traits {typedef T DistMap;};
3.351 + ///\e
3.352 + template<class T>
3.353 + _Dijkstra<SetDistMapTraits<T> > setDistMap(const T &t)
3.354 + {
3.355 + _Dijkstra<SetPredMapTraits<T> > r;
3.356 + r.G=G;
3.357 + r.length=length;
3.358 + r.predecessor=predecessor;
3.359 + r.pred_node=pred_node;
3.360 + r.distance=&t;
3.361 + r.source=source;
3.362 + return r;
3.363 + }
3.364 +
3.365 + ///\e
3.366 + _Dijkstra<TR> &setSource(Node s)
3.367 + {
3.368 + source=s;
3.369 + return *this;
3.370 + }
3.371 +
3.372 + };
3.373
3.374 + ///\e
3.375 +
3.376 + ///\e
3.377 + ///
3.378 + template<class GR, class LM>
3.379 + _Dijkstra<DijkstraDefaultTraits<GR,LM> >
3.380 + dijkstra(const GR &g,const LM &l,typename GR::Node s)
3.381 + {
3.382 + return _Dijkstra<DijkstraDefaultTraits<GR,LM> >(g,l,s);
3.383 + }
3.384 +
3.385 /// @}
3.386
3.387 } //END OF NAMESPACE LEMON