1.1 --- a/lemon/preflow.h Thu Mar 05 10:13:20 2009 +0000
1.2 +++ b/lemon/preflow.h Sun Mar 29 23:08:20 2009 +0200
1.3 @@ -32,8 +32,8 @@
1.4 ///
1.5 /// Default traits class of Preflow class.
1.6 /// \tparam GR Digraph type.
1.7 - /// \tparam CM Capacity map type.
1.8 - template <typename GR, typename CM>
1.9 + /// \tparam CAP Capacity map type.
1.10 + template <typename GR, typename CAP>
1.11 struct PreflowDefaultTraits {
1.12
1.13 /// \brief The type of the digraph the algorithm runs on.
1.14 @@ -43,7 +43,7 @@
1.15 ///
1.16 /// The type of the map that stores the arc capacities.
1.17 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.18 - typedef CM CapacityMap;
1.19 + typedef CAP CapacityMap;
1.20
1.21 /// \brief The type of the flow values.
1.22 typedef typename CapacityMap::Value Value;
1.23 @@ -94,8 +94,9 @@
1.24 /// \brief %Preflow algorithm class.
1.25 ///
1.26 /// This class provides an implementation of Goldberg-Tarjan's \e preflow
1.27 - /// \e push-relabel algorithm producing a flow of maximum value in a
1.28 - /// digraph. The preflow algorithms are the fastest known maximum
1.29 + /// \e push-relabel algorithm producing a \ref max_flow
1.30 + /// "flow of maximum value" in a digraph.
1.31 + /// The preflow algorithms are the fastest known maximum
1.32 /// flow algorithms. The current implementation use a mixture of the
1.33 /// \e "highest label" and the \e "bound decrease" heuristics.
1.34 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
1.35 @@ -105,14 +106,14 @@
1.36 /// second phase constructs a feasible maximum flow on each arc.
1.37 ///
1.38 /// \tparam GR The type of the digraph the algorithm runs on.
1.39 - /// \tparam CM The type of the capacity map. The default map
1.40 + /// \tparam CAP The type of the capacity map. The default map
1.41 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.42 #ifdef DOXYGEN
1.43 - template <typename GR, typename CM, typename TR>
1.44 + template <typename GR, typename CAP, typename TR>
1.45 #else
1.46 template <typename GR,
1.47 - typename CM = typename GR::template ArcMap<int>,
1.48 - typename TR = PreflowDefaultTraits<GR, CM> >
1.49 + typename CAP = typename GR::template ArcMap<int>,
1.50 + typename TR = PreflowDefaultTraits<GR, CAP> >
1.51 #endif
1.52 class Preflow {
1.53 public:
1.54 @@ -194,9 +195,9 @@
1.55
1.56 ///@{
1.57
1.58 - template <typename _FlowMap>
1.59 + template <typename T>
1.60 struct SetFlowMapTraits : public Traits {
1.61 - typedef _FlowMap FlowMap;
1.62 + typedef T FlowMap;
1.63 static FlowMap *createFlowMap(const Digraph&) {
1.64 LEMON_ASSERT(false, "FlowMap is not initialized");
1.65 return 0; // ignore warnings
1.66 @@ -208,16 +209,16 @@
1.67 ///
1.68 /// \ref named-templ-param "Named parameter" for setting FlowMap
1.69 /// type.
1.70 - template <typename _FlowMap>
1.71 + template <typename T>
1.72 struct SetFlowMap
1.73 - : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
1.74 + : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
1.75 typedef Preflow<Digraph, CapacityMap,
1.76 - SetFlowMapTraits<_FlowMap> > Create;
1.77 + SetFlowMapTraits<T> > Create;
1.78 };
1.79
1.80 - template <typename _Elevator>
1.81 + template <typename T>
1.82 struct SetElevatorTraits : public Traits {
1.83 - typedef _Elevator Elevator;
1.84 + typedef T Elevator;
1.85 static Elevator *createElevator(const Digraph&, int) {
1.86 LEMON_ASSERT(false, "Elevator is not initialized");
1.87 return 0; // ignore warnings
1.88 @@ -233,16 +234,16 @@
1.89 /// \ref elevator(Elevator&) "elevator()" function before calling
1.90 /// \ref run() or \ref init().
1.91 /// \sa SetStandardElevator
1.92 - template <typename _Elevator>
1.93 + template <typename T>
1.94 struct SetElevator
1.95 - : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
1.96 + : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
1.97 typedef Preflow<Digraph, CapacityMap,
1.98 - SetElevatorTraits<_Elevator> > Create;
1.99 + SetElevatorTraits<T> > Create;
1.100 };
1.101
1.102 - template <typename _Elevator>
1.103 + template <typename T>
1.104 struct SetStandardElevatorTraits : public Traits {
1.105 - typedef _Elevator Elevator;
1.106 + typedef T Elevator;
1.107 static Elevator *createElevator(const Digraph& digraph, int max_level) {
1.108 return new Elevator(digraph, max_level);
1.109 }
1.110 @@ -260,12 +261,12 @@
1.111 /// algorithm with the \ref elevator(Elevator&) "elevator()" function
1.112 /// before calling \ref run() or \ref init().
1.113 /// \sa SetElevator
1.114 - template <typename _Elevator>
1.115 + template <typename T>
1.116 struct SetStandardElevator
1.117 : public Preflow<Digraph, CapacityMap,
1.118 - SetStandardElevatorTraits<_Elevator> > {
1.119 + SetStandardElevatorTraits<T> > {
1.120 typedef Preflow<Digraph, CapacityMap,
1.121 - SetStandardElevatorTraits<_Elevator> > Create;
1.122 + SetStandardElevatorTraits<T> > Create;
1.123 };
1.124
1.125 /// @}
1.126 @@ -946,7 +947,7 @@
1.127 /// could be slightly different if inexact computation is used.
1.128 ///
1.129 /// \note This function calls \ref minCut() for each node, so it runs in
1.130 - /// \f$O(n)\f$ time.
1.131 + /// O(n) time.
1.132 ///
1.133 /// \pre Either \ref run() or \ref init() must be called before
1.134 /// using this function.