Changeset 954:5b1ffef43d4c in lemon0.x for src
 Timestamp:
 11/01/04 20:00:19 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1334
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r953 r954 31 31 /// @{ 32 32 33 ///Default traits class of Dijkstra class. 34 35 ///Default traits class of Dijkstra class. 36 ///\param GR Graph type. 37 ///\param LM Type of length map. 33 38 template<class GR, class LM> 34 39 struct DijkstraDefaultTraits 35 40 { 36 /// \e41 ///The graph type the algorithm runs on. 37 42 typedef GR Graph; 38 ///\e39 typedef typename Graph::Node Node;40 ///\e41 typedef typename Graph::Edge Edge;42 43 ///The type of the map that stores the edge lengths. 43 44 … … 45 46 /// 46 47 typedef LM LengthMap; 47 // /The type of the length of the edges.48 //The type of the length of the edges. 48 49 typedef typename LM::ValueType ValueType; 49 ///The heap type used by the dijkstra algorithm.50 ///The heap type used by Dijkstra algorithm. 50 51 typedef BinHeap<typename Graph::Node, 51 52 typename LM::ValueType, … … 58 59 ///It must meet the \ref WriteMap concept. 59 60 /// 60 typedef typename Graph::template NodeMap< Edge> PredMap;61 /// 61 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; 62 ///Instantiates a PredMap. 62 63 63 64 ///\todo Please document... 64 65 /// 65 static PredMap *createPredMap(const G raph&G)66 static PredMap *createPredMap(const GR &G) 66 67 { 67 68 return new PredMap(G); … … 72 73 ///It must meet the \ref WriteMap concept. 73 74 /// 74 typedef typename Graph::template NodeMap< Node> PredNodeMap;75 /// 75 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap; 76 ///Instantiates a PredNodeMap. 76 77 77 78 ///\todo Please document... 78 79 /// 79 static PredNodeMap *createPredNodeMap(const G raph&G)80 static PredNodeMap *createPredNodeMap(const GR &G) 80 81 { 81 82 return new PredNodeMap(G); … … 85 86 ///It must meet the \ref WriteMap concept. 86 87 /// 87 typedef typename Graph::template NodeMap< ValueType> DistMap;88 /// 88 typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap; 89 ///Instantiates a DistMap. 89 90 90 91 ///\todo Please document... 91 92 /// 92 static DistMap *createDistMap(const G raph&G)93 static DistMap *createDistMap(const GR &G) 93 94 { 94 95 return new DistMap(G); … … 109 110 /// 110 111 ///\param GR The graph type the algorithm runs on. The default value is 111 ///\ref ListGraph 112 ///\ref ListGraph. The value of GR is not used directly by %Dijsktra, it 113 ///is only passed to \ref DijkstraDefaultTraits. 112 114 ///\param LM This readonly 113 115 ///EdgeMap … … 116 118 ///may involve in relatively time consuming process to compute the edge 117 119 ///length if it is necessary. The default map type is 118 ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>" 119 ///\param Heap The heap type used by the %Dijkstra 120 ///algorithm. The default 121 ///is using \ref BinHeap "binary heap". 120 ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap<int>". 121 ///The value of LM is not used directly by %Dijsktra, it 122 ///is only passed to \ref DijkstraDefaultTraits. 123 ///\param TR Traits class to set various data types used by the algorithm. 124 ///The default traits class is 125 ///\ref DijkstraDefaultTraits<GR,LM> "DijkstraDefaultTraits<GR,LM>". 126 ///See \ref DijkstraDefaultTraits for the documentation of 127 ///a Dijkstra traits class. 122 128 /// 123 129 ///\author Jacint Szabo and Alpar Juttner 124 130 ///\todo We need a typedefnames should be standardized. (: 125 ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap126 ///should not be fixed. (Problematic to solve).127 131 128 132 #ifdef DOXYGEN … … 139 143 typedef TR Traits; 140 144 ///The type of the underlying graph. 141 typedef GRGraph;145 typedef typename TR::Graph Graph; 142 146 ///\e 143 147 typedef typename Graph::Node Node; … … 150 154 151 155 ///The type of the length of the edges. 152 typedef typename LM::ValueType ValueType;156 typedef typename TR::LengthMap::ValueType ValueType; 153 157 ///The type of the map that stores the edge lengths. 154 typedef LMLengthMap;158 typedef typename TR::LengthMap LengthMap; 155 159 ///\brief The type of the map that stores the last 156 160 ///edges of the shortest paths. … … 161 165 ///The type of the map that stores the dists of the nodes. 162 166 typedef typename TR::DistMap DistMap; 163 164 167 ///The heap type used by the dijkstra algorithm. 165 168 typedef typename TR::Heap Heap; … … 169 172 const Graph *G; 170 173 /// Pointer to the length map 171 const L M*length;174 const LengthMap *length; 172 175 ///Pointer to the map of predecessors edges. 173 176 PredMap *predecessor; … … 220 223 } 221 224 }; 222 ///\ref namedtemplparam "Named parameter" for setting PredMap's type 225 ///\ref namedtemplparam "Named parameter" for setting PredMap type 226 227 ///\ingroup flowalgs 228 ///\ref namedtemplparam "Named parameter" for setting PredMap type 223 229 template <class T> 224 230 class SetPredMap : public Dijkstra< Graph, … … 238 244 } 239 245 }; 240 ///\ref namedtemplparam "Named parameter" for setting PredNodeMap's type 246 ///\ref namedtemplparam "Named parameter" for setting PredNodeMap type 247 248 ///\ingroup flowalgs 249 ///\ref namedtemplparam "Named parameter" for setting PredNodeMap type 241 250 template <class T> 242 251 class SetPredNodeMap : public Dijkstra< Graph, … … 256 265 } 257 266 }; 258 ///\ref namedtemplparam "Named parameter" for setting DistMap's type 267 ///\ref namedtemplparam "Named parameter" for setting DistMap type 268 269 ///\ingroup flowalgs 270 ///\ref namedtemplparam "Named parameter" for setting DistMap type 259 271 template <class T> 260 272 class SetDistMap : public Dijkstra< Graph, … … 266 278 ///\param _G the graph the algorithm will run on. 267 279 ///\param _length the length map used by the algorithm. 268 Dijkstra(const Graph& _G, const L M& _length) :280 Dijkstra(const Graph& _G, const LengthMap& _length) : 269 281 G(&_G), length(&_length), 270 282 predecessor(NULL), local_predecessor(false), … … 285 297 ///Sets the length map. 286 298 ///\return <tt> (*this) </tt> 287 Dijkstra &setLengthMap(const L M&m)299 Dijkstra &setLengthMap(const LengthMap &m) 288 300 { 289 301 length = &m; … … 350 362 /// The shortest path tree. 351 363 /// The distance of each node from the root. 352 364 ///\todo heap_map's type could also be in the traits class. 353 365 void run(Node s) { 354 366 … … 362 374 } 363 375 364 typename G R::template NodeMap<int> heap_map(*G,1);376 typename Graph::template NodeMap<int> heap_map(*G,1); 365 377 366 378 Heap heap(heap_map); … … 584 596 ///\e 585 597 586 ///\ e598 ///\todo Please document... 587 599 /// 588 600 template<class GR, class LM>
Note: See TracChangeset
for help on using the changeset viewer.