29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \brief Default traits class of Circulation class. |
31 /// \brief Default traits class of Circulation class. |
32 /// |
32 /// |
33 /// Default traits class of Circulation class. |
33 /// Default traits class of Circulation class. |
34 /// \tparam _Diraph Digraph type. |
34 /// \tparam GR Digraph type. |
35 /// \tparam _LCapMap Lower bound capacity map type. |
35 /// \tparam LM Lower bound capacity map type. |
36 /// \tparam _UCapMap Upper bound capacity map type. |
36 /// \tparam UM Upper bound capacity map type. |
37 /// \tparam _DeltaMap Delta map type. |
37 /// \tparam DM Delta map type. |
38 template <typename _Diraph, typename _LCapMap, |
38 template <typename GR, typename LM, |
39 typename _UCapMap, typename _DeltaMap> |
39 typename UM, typename DM> |
40 struct CirculationDefaultTraits { |
40 struct CirculationDefaultTraits { |
41 |
41 |
42 /// \brief The type of the digraph the algorithm runs on. |
42 /// \brief The type of the digraph the algorithm runs on. |
43 typedef _Diraph Digraph; |
43 typedef GR Digraph; |
44 |
44 |
45 /// \brief The type of the map that stores the circulation lower |
45 /// \brief The type of the map that stores the circulation lower |
46 /// bound. |
46 /// bound. |
47 /// |
47 /// |
48 /// The type of the map that stores the circulation lower bound. |
48 /// The type of the map that stores the circulation lower bound. |
49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
50 typedef _LCapMap LCapMap; |
50 typedef LM LCapMap; |
51 |
51 |
52 /// \brief The type of the map that stores the circulation upper |
52 /// \brief The type of the map that stores the circulation upper |
53 /// bound. |
53 /// bound. |
54 /// |
54 /// |
55 /// The type of the map that stores the circulation upper bound. |
55 /// The type of the map that stores the circulation upper bound. |
56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
57 typedef _UCapMap UCapMap; |
57 typedef UM UCapMap; |
58 |
58 |
59 /// \brief The type of the map that stores the lower bound for |
59 /// \brief The type of the map that stores the lower bound for |
60 /// the supply of the nodes. |
60 /// the supply of the nodes. |
61 /// |
61 /// |
62 /// The type of the map that stores the lower bound for the supply |
62 /// The type of the map that stores the lower bound for the supply |
63 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" |
63 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" |
64 /// concept. |
64 /// concept. |
65 typedef _DeltaMap DeltaMap; |
65 typedef DM DeltaMap; |
66 |
66 |
67 /// \brief The type of the flow values. |
67 /// \brief The type of the flow values. |
68 typedef typename DeltaMap::Value Value; |
68 typedef typename DeltaMap::Value Value; |
69 |
69 |
70 /// \brief The type of the map that stores the flow values. |
70 /// \brief The type of the map that stores the flow values. |
135 will be \e equal \e to \f$delta(v)\f$, if a circulation can be found. |
135 will be \e equal \e to \f$delta(v)\f$, if a circulation can be found. |
136 Thus a feasible solution for the |
136 Thus a feasible solution for the |
137 \ref min_cost_flow "minimum cost flow" problem can be calculated |
137 \ref min_cost_flow "minimum cost flow" problem can be calculated |
138 in this way. |
138 in this way. |
139 |
139 |
140 \tparam _Digraph The type of the digraph the algorithm runs on. |
140 \tparam GR The type of the digraph the algorithm runs on. |
141 \tparam _LCapMap The type of the lower bound capacity map. The default |
141 \tparam LM The type of the lower bound capacity map. The default |
142 map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". |
142 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
143 \tparam _UCapMap The type of the upper bound capacity map. The default |
143 \tparam UM The type of the upper bound capacity map. The default |
144 map type is \c _LCapMap. |
144 map type is \c LM. |
145 \tparam _DeltaMap The type of the map that stores the lower bound |
145 \tparam DM The type of the map that stores the lower bound |
146 for the supply of the nodes. The default map type is |
146 for the supply of the nodes. The default map type is |
147 \c _Digraph::ArcMap<_UCapMap::Value>. |
147 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". |
148 */ |
148 */ |
149 #ifdef DOXYGEN |
149 #ifdef DOXYGEN |
150 template< typename _Digraph, |
150 template< typename GR, |
151 typename _LCapMap, |
151 typename LM, |
152 typename _UCapMap, |
152 typename UM, |
153 typename _DeltaMap, |
153 typename DM, |
154 typename _Traits > |
154 typename TR > |
155 #else |
155 #else |
156 template< typename _Digraph, |
156 template< typename GR, |
157 typename _LCapMap = typename _Digraph::template ArcMap<int>, |
157 typename LM = typename GR::template ArcMap<int>, |
158 typename _UCapMap = _LCapMap, |
158 typename UM = LM, |
159 typename _DeltaMap = typename _Digraph:: |
159 typename DM = typename GR::template NodeMap<typename UM::Value>, |
160 template NodeMap<typename _UCapMap::Value>, |
160 typename TR = CirculationDefaultTraits<GR, LM, UM, DM> > |
161 typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap, |
|
162 _UCapMap, _DeltaMap> > |
|
163 #endif |
161 #endif |
164 class Circulation { |
162 class Circulation { |
165 public: |
163 public: |
166 |
164 |
167 ///The \ref CirculationDefaultTraits "traits class" of the algorithm. |
165 ///The \ref CirculationDefaultTraits "traits class" of the algorithm. |
168 typedef _Traits Traits; |
166 typedef TR Traits; |
169 ///The type of the digraph the algorithm runs on. |
167 ///The type of the digraph the algorithm runs on. |
170 typedef typename Traits::Digraph Digraph; |
168 typedef typename Traits::Digraph Digraph; |
171 ///The type of the flow values. |
169 ///The type of the flow values. |
172 typedef typename Traits::Value Value; |
170 typedef typename Traits::Value Value; |
173 |
171 |