Changeset 931:abb95d48e89e in lemon
 Timestamp:
 10/16/09 09:35:46 (10 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r927 r931 34 34 35 35 namespace lemon { 36 37 /// \brief Default traits class of Suurballe algorithm. 38 /// 39 /// Default traits class of Suurballe algorithm. 40 /// \tparam GR The digraph type the algorithm runs on. 41 /// \tparam LEN The type of the length map. 42 /// The default value is <tt>GR::ArcMap<int></tt>. 43 #ifdef DOXYGEN 44 template <typename GR, typename LEN> 45 #else 46 template < typename GR, 47 typename LEN = typename GR::template ArcMap<int> > 48 #endif 49 struct SuurballeDefaultTraits 50 { 51 /// The type of the digraph. 52 typedef GR Digraph; 53 /// The type of the length map. 54 typedef LEN LengthMap; 55 /// The type of the lengths. 56 typedef typename LEN::Value Length; 57 /// The type of the flow map. 58 typedef typename GR::template ArcMap<int> FlowMap; 59 /// The type of the potential map. 60 typedef typename GR::template NodeMap<Length> PotentialMap; 61 62 /// \brief The path type 63 /// 64 /// The type used for storing the found arcdisjoint paths. 65 /// It must conform to the \ref lemon::concepts::Path "Path" concept 66 /// and it must have an \c addBack() function. 67 typedef lemon::Path<Digraph> Path; 68 69 /// The cross reference type used for the heap. 70 typedef typename GR::template NodeMap<int> HeapCrossRef; 71 72 /// \brief The heap type used for internal Dijkstra computations. 73 /// 74 /// The type of the heap used for internal Dijkstra computations. 75 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept 76 /// and its priority type must be \c Length. 77 typedef BinHeap<Length, HeapCrossRef> Heap; 78 }; 36 79 37 80 /// \addtogroup shortest_path … … 62 105 /// along with the \ref SplitNodes adaptor. 63 106 #ifdef DOXYGEN 64 template <typename GR, typename LEN >107 template <typename GR, typename LEN, typename TR> 65 108 #else 66 109 template < typename GR, 67 typename LEN = typename GR::template ArcMap<int> > 110 typename LEN = typename GR::template ArcMap<int>, 111 typename TR = SuurballeDefaultTraits<GR, LEN> > 68 112 #endif 69 113 class Suurballe … … 76 120 public: 77 121 78 /// The type of the digraph the algorithm runs on.79 typedef GRDigraph;122 /// The type of the digraph. 123 typedef typename TR::Digraph Digraph; 80 124 /// The type of the length map. 81 typedef LENLengthMap;125 typedef typename TR::LengthMap LengthMap; 82 126 /// The type of the lengths. 83 typedef typename LengthMap::ValueLength;84 #ifdef DOXYGEN 127 typedef typename TR::Length Length; 128 85 129 /// The type of the flow map. 86 typedef GR::ArcMap<int>FlowMap;130 typedef typename TR::FlowMap FlowMap; 87 131 /// The type of the potential map. 88 typedef GR::NodeMap<Length> PotentialMap; 89 #else 90 /// The type of the flow map. 91 typedef typename Digraph::template ArcMap<int> FlowMap; 92 /// The type of the potential map. 93 typedef typename Digraph::template NodeMap<Length> PotentialMap; 94 #endif 95 132 typedef typename TR::PotentialMap PotentialMap; 96 133 /// The type of the path structures. 97 typedef SimplePath<GR> Path; 134 typedef typename TR::Path Path; 135 /// The cross reference type used for the heap. 136 typedef typename TR::HeapCrossRef HeapCrossRef; 137 /// The heap type used for internal Dijkstra computations. 138 typedef typename TR::Heap Heap; 139 140 /// The \ref SuurballeDefaultTraits "traits class" of the algorithm. 141 typedef TR Traits; 98 142 99 143 private: 100 101 typedef typename Digraph::template NodeMap<int> HeapCrossRef;102 typedef BinHeap<Length, HeapCrossRef> Heap;103 144 104 145 // ResidualDijkstra is a special implementation of the … … 255 296 }; //class ResidualDijkstra 256 297 298 public: 299 300 /// \name Named Template Parameters 301 /// @{ 302 303 template <typename T> 304 struct SetFlowMapTraits : public Traits { 305 typedef T FlowMap; 306 }; 307 308 /// \brief \ref namedtemplparam "Named parameter" for setting 309 /// \c FlowMap type. 310 /// 311 /// \ref namedtemplparam "Named parameter" for setting 312 /// \c FlowMap type. 313 template <typename T> 314 struct SetFlowMap 315 : public Suurballe<GR, LEN, SetFlowMapTraits<T> > { 316 typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create; 317 }; 318 319 template <typename T> 320 struct SetPotentialMapTraits : public Traits { 321 typedef T PotentialMap; 322 }; 323 324 /// \brief \ref namedtemplparam "Named parameter" for setting 325 /// \c PotentialMap type. 326 /// 327 /// \ref namedtemplparam "Named parameter" for setting 328 /// \c PotentialMap type. 329 template <typename T> 330 struct SetPotentialMap 331 : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > { 332 typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create; 333 }; 334 335 template <typename T> 336 struct SetPathTraits : public Traits { 337 typedef T Path; 338 }; 339 340 /// \brief \ref namedtemplparam "Named parameter" for setting 341 /// \c %Path type. 342 /// 343 /// \ref namedtemplparam "Named parameter" for setting \c %Path type. 344 /// It must conform to the \ref lemon::concepts::Path "Path" concept 345 /// and it must have an \c addBack() function. 346 template <typename T> 347 struct SetPath 348 : public Suurballe<GR, LEN, SetPathTraits<T> > { 349 typedef Suurballe<GR, LEN, SetPathTraits<T> > Create; 350 }; 351 352 template <typename H, typename CR> 353 struct SetHeapTraits : public Traits { 354 typedef H Heap; 355 typedef CR HeapCrossRef; 356 }; 357 358 /// \brief \ref namedtemplparam "Named parameter" for setting 359 /// \c Heap and \c HeapCrossRef types. 360 /// 361 /// \ref namedtemplparam "Named parameter" for setting \c Heap 362 /// and \c HeapCrossRef types with automatic allocation. 363 /// They will be used for internal Dijkstra computations. 364 /// The heap type must conform to the \ref lemon::concepts::Heap "Heap" 365 /// concept and its priority type must be \c Length. 366 template <typename H, 367 typename CR = typename Digraph::template NodeMap<int> > 368 struct SetHeap 369 : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > { 370 typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create; 371 }; 372 373 /// @} 374 257 375 private: 258 376 
test/suurballe_test.cc
r927 r931 24 24 #include <lemon/suurballe.h> 25 25 #include <lemon/concepts/digraph.h> 26 #include <lemon/concepts/heap.h> 26 27 27 28 #include "test_tools.h" … … 82 83 typedef concepts::ReadMap<Arc, VType> LengthMap; 83 84 84 typedef Suurballe<Digraph, LengthMap> SuurballeType; 85 typedef Suurballe<Digraph, LengthMap> ST; 86 typedef Suurballe<Digraph, LengthMap> 87 ::SetFlowMap<ST::FlowMap> 88 ::SetPotentialMap<ST::PotentialMap> 89 ::SetPath<SimplePath<Digraph> > 90 ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > > 91 ::Create SuurballeType; 85 92 86 93 Digraph g;
Note: See TracChangeset
for help on using the changeset viewer.