1.1 --- a/lemon/suurballe.h Wed Mar 03 17:14:17 2010 +0000
1.2 +++ b/lemon/suurballe.h Fri Oct 16 09:35:46 2009 +0200
1.3 @@ -34,6 +34,49 @@
1.4
1.5 namespace lemon {
1.6
1.7 + /// \brief Default traits class of Suurballe algorithm.
1.8 + ///
1.9 + /// Default traits class of Suurballe algorithm.
1.10 + /// \tparam GR The digraph type the algorithm runs on.
1.11 + /// \tparam LEN The type of the length map.
1.12 + /// The default value is <tt>GR::ArcMap<int></tt>.
1.13 +#ifdef DOXYGEN
1.14 + template <typename GR, typename LEN>
1.15 +#else
1.16 + template < typename GR,
1.17 + typename LEN = typename GR::template ArcMap<int> >
1.18 +#endif
1.19 + struct SuurballeDefaultTraits
1.20 + {
1.21 + /// The type of the digraph.
1.22 + typedef GR Digraph;
1.23 + /// The type of the length map.
1.24 + typedef LEN LengthMap;
1.25 + /// The type of the lengths.
1.26 + typedef typename LEN::Value Length;
1.27 + /// The type of the flow map.
1.28 + typedef typename GR::template ArcMap<int> FlowMap;
1.29 + /// The type of the potential map.
1.30 + typedef typename GR::template NodeMap<Length> PotentialMap;
1.31 +
1.32 + /// \brief The path type
1.33 + ///
1.34 + /// The type used for storing the found arc-disjoint paths.
1.35 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.36 + /// and it must have an \c addBack() function.
1.37 + typedef lemon::Path<Digraph> Path;
1.38 +
1.39 + /// The cross reference type used for the heap.
1.40 + typedef typename GR::template NodeMap<int> HeapCrossRef;
1.41 +
1.42 + /// \brief The heap type used for internal Dijkstra computations.
1.43 + ///
1.44 + /// The type of the heap used for internal Dijkstra computations.
1.45 + /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
1.46 + /// and its priority type must be \c Length.
1.47 + typedef BinHeap<Length, HeapCrossRef> Heap;
1.48 + };
1.49 +
1.50 /// \addtogroup shortest_path
1.51 /// @{
1.52
1.53 @@ -61,10 +104,11 @@
1.54 /// \note For finding \e node-disjoint paths, this algorithm can be used
1.55 /// along with the \ref SplitNodes adaptor.
1.56 #ifdef DOXYGEN
1.57 - template <typename GR, typename LEN>
1.58 + template <typename GR, typename LEN, typename TR>
1.59 #else
1.60 template < typename GR,
1.61 - typename LEN = typename GR::template ArcMap<int> >
1.62 + typename LEN = typename GR::template ArcMap<int>,
1.63 + typename TR = SuurballeDefaultTraits<GR, LEN> >
1.64 #endif
1.65 class Suurballe
1.66 {
1.67 @@ -75,32 +119,29 @@
1.68
1.69 public:
1.70
1.71 - /// The type of the digraph the algorithm runs on.
1.72 - typedef GR Digraph;
1.73 + /// The type of the digraph.
1.74 + typedef typename TR::Digraph Digraph;
1.75 /// The type of the length map.
1.76 - typedef LEN LengthMap;
1.77 + typedef typename TR::LengthMap LengthMap;
1.78 /// The type of the lengths.
1.79 - typedef typename LengthMap::Value Length;
1.80 -#ifdef DOXYGEN
1.81 + typedef typename TR::Length Length;
1.82 +
1.83 /// The type of the flow map.
1.84 - typedef GR::ArcMap<int> FlowMap;
1.85 + typedef typename TR::FlowMap FlowMap;
1.86 /// The type of the potential map.
1.87 - typedef GR::NodeMap<Length> PotentialMap;
1.88 -#else
1.89 - /// The type of the flow map.
1.90 - typedef typename Digraph::template ArcMap<int> FlowMap;
1.91 - /// The type of the potential map.
1.92 - typedef typename Digraph::template NodeMap<Length> PotentialMap;
1.93 -#endif
1.94 + typedef typename TR::PotentialMap PotentialMap;
1.95 + /// The type of the path structures.
1.96 + typedef typename TR::Path Path;
1.97 + /// The cross reference type used for the heap.
1.98 + typedef typename TR::HeapCrossRef HeapCrossRef;
1.99 + /// The heap type used for internal Dijkstra computations.
1.100 + typedef typename TR::Heap Heap;
1.101
1.102 - /// The type of the path structures.
1.103 - typedef SimplePath<GR> Path;
1.104 + /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
1.105 + typedef TR Traits;
1.106
1.107 private:
1.108
1.109 - typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.110 - typedef BinHeap<Length, HeapCrossRef> Heap;
1.111 -
1.112 // ResidualDijkstra is a special implementation of the
1.113 // Dijkstra algorithm for finding shortest paths in the
1.114 // residual network with respect to the reduced arc lengths
1.115 @@ -254,6 +295,83 @@
1.116
1.117 }; //class ResidualDijkstra
1.118
1.119 + public:
1.120 +
1.121 + /// \name Named Template Parameters
1.122 + /// @{
1.123 +
1.124 + template <typename T>
1.125 + struct SetFlowMapTraits : public Traits {
1.126 + typedef T FlowMap;
1.127 + };
1.128 +
1.129 + /// \brief \ref named-templ-param "Named parameter" for setting
1.130 + /// \c FlowMap type.
1.131 + ///
1.132 + /// \ref named-templ-param "Named parameter" for setting
1.133 + /// \c FlowMap type.
1.134 + template <typename T>
1.135 + struct SetFlowMap
1.136 + : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
1.137 + typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
1.138 + };
1.139 +
1.140 + template <typename T>
1.141 + struct SetPotentialMapTraits : public Traits {
1.142 + typedef T PotentialMap;
1.143 + };
1.144 +
1.145 + /// \brief \ref named-templ-param "Named parameter" for setting
1.146 + /// \c PotentialMap type.
1.147 + ///
1.148 + /// \ref named-templ-param "Named parameter" for setting
1.149 + /// \c PotentialMap type.
1.150 + template <typename T>
1.151 + struct SetPotentialMap
1.152 + : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
1.153 + typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
1.154 + };
1.155 +
1.156 + template <typename T>
1.157 + struct SetPathTraits : public Traits {
1.158 + typedef T Path;
1.159 + };
1.160 +
1.161 + /// \brief \ref named-templ-param "Named parameter" for setting
1.162 + /// \c %Path type.
1.163 + ///
1.164 + /// \ref named-templ-param "Named parameter" for setting \c %Path type.
1.165 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.166 + /// and it must have an \c addBack() function.
1.167 + template <typename T>
1.168 + struct SetPath
1.169 + : public Suurballe<GR, LEN, SetPathTraits<T> > {
1.170 + typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
1.171 + };
1.172 +
1.173 + template <typename H, typename CR>
1.174 + struct SetHeapTraits : public Traits {
1.175 + typedef H Heap;
1.176 + typedef CR HeapCrossRef;
1.177 + };
1.178 +
1.179 + /// \brief \ref named-templ-param "Named parameter" for setting
1.180 + /// \c Heap and \c HeapCrossRef types.
1.181 + ///
1.182 + /// \ref named-templ-param "Named parameter" for setting \c Heap
1.183 + /// and \c HeapCrossRef types with automatic allocation.
1.184 + /// They will be used for internal Dijkstra computations.
1.185 + /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
1.186 + /// concept and its priority type must be \c Length.
1.187 + template <typename H,
1.188 + typename CR = typename Digraph::template NodeMap<int> >
1.189 + struct SetHeap
1.190 + : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
1.191 + typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
1.192 + };
1.193 +
1.194 + /// @}
1.195 +
1.196 private:
1.197
1.198 // The digraph the algorithm runs on
2.1 --- a/test/suurballe_test.cc Wed Mar 03 17:14:17 2010 +0000
2.2 +++ b/test/suurballe_test.cc Fri Oct 16 09:35:46 2009 +0200
2.3 @@ -23,6 +23,7 @@
2.4 #include <lemon/path.h>
2.5 #include <lemon/suurballe.h>
2.6 #include <lemon/concepts/digraph.h>
2.7 +#include <lemon/concepts/heap.h>
2.8
2.9 #include "test_tools.h"
2.10
2.11 @@ -81,7 +82,13 @@
2.12 typedef Digraph::Arc Arc;
2.13 typedef concepts::ReadMap<Arc, VType> LengthMap;
2.14
2.15 - typedef Suurballe<Digraph, LengthMap> SuurballeType;
2.16 + typedef Suurballe<Digraph, LengthMap> ST;
2.17 + typedef Suurballe<Digraph, LengthMap>
2.18 + ::SetFlowMap<ST::FlowMap>
2.19 + ::SetPotentialMap<ST::PotentialMap>
2.20 + ::SetPath<SimplePath<Digraph> >
2.21 + ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
2.22 + ::Create SuurballeType;
2.23
2.24 Digraph g;
2.25 Node n;