29 namespace lemon { |
29 namespace lemon { |
30 |
30 |
31 /// \brief Default traits class of Preflow class. |
31 /// \brief Default traits class of Preflow class. |
32 /// |
32 /// |
33 /// Default traits class of Preflow class. |
33 /// Default traits class of Preflow class. |
34 /// \tparam _Digraph Digraph type. |
34 /// \tparam GR Digraph type. |
35 /// \tparam _CapacityMap Capacity map type. |
35 /// \tparam CM Capacity map type. |
36 template <typename _Digraph, typename _CapacityMap> |
36 template <typename GR, typename CM> |
37 struct PreflowDefaultTraits { |
37 struct PreflowDefaultTraits { |
38 |
38 |
39 /// \brief The type of the digraph the algorithm runs on. |
39 /// \brief The type of the digraph the algorithm runs on. |
40 typedef _Digraph Digraph; |
40 typedef GR Digraph; |
41 |
41 |
42 /// \brief The type of the map that stores the arc capacities. |
42 /// \brief The type of the map that stores the arc capacities. |
43 /// |
43 /// |
44 /// The type of the map that stores the arc capacities. |
44 /// The type of the map that stores the arc capacities. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
46 typedef _CapacityMap CapacityMap; |
46 typedef CM CapacityMap; |
47 |
47 |
48 /// \brief The type of the flow values. |
48 /// \brief The type of the flow values. |
49 typedef typename CapacityMap::Value Value; |
49 typedef typename CapacityMap::Value Value; |
50 |
50 |
51 /// \brief The type of the map that stores the flow values. |
51 /// \brief The type of the map that stores the flow values. |
102 /// |
102 /// |
103 /// The algorithm consists of two phases. After the first phase |
103 /// The algorithm consists of two phases. After the first phase |
104 /// the maximum flow value and the minimum cut is obtained. The |
104 /// the maximum flow value and the minimum cut is obtained. The |
105 /// second phase constructs a feasible maximum flow on each arc. |
105 /// second phase constructs a feasible maximum flow on each arc. |
106 /// |
106 /// |
107 /// \tparam _Digraph The type of the digraph the algorithm runs on. |
107 /// \tparam GR The type of the digraph the algorithm runs on. |
108 /// \tparam _CapacityMap The type of the capacity map. The default map |
108 /// \tparam CM The type of the capacity map. The default map |
109 /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". |
109 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
110 #ifdef DOXYGEN |
110 #ifdef DOXYGEN |
111 template <typename _Digraph, typename _CapacityMap, typename _Traits> |
111 template <typename GR, typename CM, typename TR> |
112 #else |
112 #else |
113 template <typename _Digraph, |
113 template <typename GR, |
114 typename _CapacityMap = typename _Digraph::template ArcMap<int>, |
114 typename CM = typename GR::template ArcMap<int>, |
115 typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> > |
115 typename TR = PreflowDefaultTraits<GR, CM> > |
116 #endif |
116 #endif |
117 class Preflow { |
117 class Preflow { |
118 public: |
118 public: |
119 |
119 |
120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. |
120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. |
121 typedef _Traits Traits; |
121 typedef TR Traits; |
122 ///The type of the digraph the algorithm runs on. |
122 ///The type of the digraph the algorithm runs on. |
123 typedef typename Traits::Digraph Digraph; |
123 typedef typename Traits::Digraph Digraph; |
124 ///The type of the capacity map. |
124 ///The type of the capacity map. |
125 typedef typename Traits::CapacityMap CapacityMap; |
125 typedef typename Traits::CapacityMap CapacityMap; |
126 ///The type of the flow values. |
126 ///The type of the flow values. |