31 #include <lemon/list_graph.h> |
31 #include <lemon/list_graph.h> |
32 #include <lemon/dijkstra.h> |
32 #include <lemon/dijkstra.h> |
33 #include <lemon/maps.h> |
33 #include <lemon/maps.h> |
34 |
34 |
35 namespace lemon { |
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 arc-disjoint 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 /// \addtogroup shortest_path |
80 /// \addtogroup shortest_path |
38 /// @{ |
81 /// @{ |
39 |
82 |
40 /// \brief Algorithm for finding arc-disjoint paths between two nodes |
83 /// \brief Algorithm for finding arc-disjoint paths between two nodes |
59 /// \warning Length values should be \e non-negative. |
102 /// \warning Length values should be \e non-negative. |
60 /// |
103 /// |
61 /// \note For finding \e node-disjoint paths, this algorithm can be used |
104 /// \note For finding \e node-disjoint paths, this algorithm can be used |
62 /// along with the \ref SplitNodes adaptor. |
105 /// along with the \ref SplitNodes adaptor. |
63 #ifdef DOXYGEN |
106 #ifdef DOXYGEN |
64 template <typename GR, typename LEN> |
107 template <typename GR, typename LEN, typename TR> |
65 #else |
108 #else |
66 template < typename GR, |
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 #endif |
112 #endif |
69 class Suurballe |
113 class Suurballe |
70 { |
114 { |
71 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
115 TEMPLATE_DIGRAPH_TYPEDEFS(GR); |
72 |
116 |
73 typedef ConstMap<Arc, int> ConstArcMap; |
117 typedef ConstMap<Arc, int> ConstArcMap; |
74 typedef typename GR::template NodeMap<Arc> PredMap; |
118 typedef typename GR::template NodeMap<Arc> PredMap; |
75 |
119 |
76 public: |
120 public: |
77 |
121 |
78 /// The type of the digraph the algorithm runs on. |
122 /// The type of the digraph. |
79 typedef GR Digraph; |
123 typedef typename TR::Digraph Digraph; |
80 /// The type of the length map. |
124 /// The type of the length map. |
81 typedef LEN LengthMap; |
125 typedef typename TR::LengthMap LengthMap; |
82 /// The type of the lengths. |
126 /// The type of the lengths. |
83 typedef typename LengthMap::Value Length; |
127 typedef typename TR::Length Length; |
84 #ifdef DOXYGEN |
128 |
85 /// The type of the flow map. |
129 /// The type of the flow map. |
86 typedef GR::ArcMap<int> FlowMap; |
130 typedef typename TR::FlowMap FlowMap; |
87 /// The type of the potential map. |
131 /// The type of the potential map. |
88 typedef GR::NodeMap<Length> PotentialMap; |
132 typedef typename TR::PotentialMap 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 |
|
96 /// The type of the path structures. |
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 private: |
143 private: |
100 |
|
101 typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
|
102 typedef BinHeap<Length, HeapCrossRef> Heap; |
|
103 |
144 |
104 // ResidualDijkstra is a special implementation of the |
145 // ResidualDijkstra is a special implementation of the |
105 // Dijkstra algorithm for finding shortest paths in the |
146 // Dijkstra algorithm for finding shortest paths in the |
106 // residual network with respect to the reduced arc lengths |
147 // residual network with respect to the reduced arc lengths |
107 // and modifying the node potentials according to the |
148 // and modifying the node potentials according to the |
252 return true; |
293 return true; |
253 } |
294 } |
254 |
295 |
255 }; //class ResidualDijkstra |
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 named-templ-param "Named parameter" for setting |
|
309 /// \c FlowMap type. |
|
310 /// |
|
311 /// \ref named-templ-param "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 named-templ-param "Named parameter" for setting |
|
325 /// \c PotentialMap type. |
|
326 /// |
|
327 /// \ref named-templ-param "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 named-templ-param "Named parameter" for setting |
|
341 /// \c %Path type. |
|
342 /// |
|
343 /// \ref named-templ-param "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 named-templ-param "Named parameter" for setting |
|
359 /// \c Heap and \c HeapCrossRef types. |
|
360 /// |
|
361 /// \ref named-templ-param "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 private: |
375 private: |
258 |
376 |
259 // The digraph the algorithm runs on |
377 // The digraph the algorithm runs on |
260 const Digraph &_graph; |
378 const Digraph &_graph; |
261 // The length map |
379 // The length map |