1.1 --- a/lemon/capacity_scaling.h	Thu Nov 12 23:26:13 2009 +0100
     1.2 +++ b/lemon/capacity_scaling.h	Thu Nov 12 23:27:21 2009 +0100
     1.3 @@ -31,6 +31,33 @@
     1.4  
     1.5  namespace lemon {
     1.6  
     1.7 +  /// \brief Default traits class of CapacityScaling algorithm.
     1.8 +  ///
     1.9 +  /// Default traits class of CapacityScaling algorithm.
    1.10 +  /// \tparam GR Digraph type.
    1.11 +  /// \tparam V The value type used for flow amounts, capacity bounds
    1.12 +  /// and supply values. By default it is \c int.
    1.13 +  /// \tparam C The value type used for costs and potentials.
    1.14 +  /// By default it is the same as \c V.
    1.15 +  template <typename GR, typename V = int, typename C = V>
    1.16 +  struct CapacityScalingDefaultTraits
    1.17 +  {
    1.18 +    /// The type of the digraph
    1.19 +    typedef GR Digraph;
    1.20 +    /// The type of the flow amounts, capacity bounds and supply values
    1.21 +    typedef V Value;
    1.22 +    /// The type of the arc costs
    1.23 +    typedef C Cost;
    1.24 +
    1.25 +    /// \brief The type of the heap used for internal Dijkstra computations.
    1.26 +    ///
    1.27 +    /// The type of the heap used for internal Dijkstra computations.
    1.28 +    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
    1.29 +    /// its priority type must be \c Cost and its cross reference type
    1.30 +    /// must be \ref RangeMap "RangeMap<int>".
    1.31 +    typedef BinHeap<Cost, RangeMap<int> > Heap;
    1.32 +  };
    1.33 +
    1.34    /// \addtogroup min_cost_flow_algs
    1.35    /// @{
    1.36  
    1.37 @@ -57,15 +84,28 @@
    1.38    /// be integer.
    1.39    /// \warning This algorithm does not support negative costs for such
    1.40    /// arcs that have infinite upper bound.
    1.41 -  template <typename GR, typename V = int, typename C = V>
    1.42 +#ifdef DOXYGEN
    1.43 +  template <typename GR, typename V, typename C, typename TR>
    1.44 +#else
    1.45 +  template < typename GR, typename V = int, typename C = V,
    1.46 +             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
    1.47 +#endif
    1.48    class CapacityScaling
    1.49    {
    1.50    public:
    1.51  
    1.52 +    /// The type of the digraph
    1.53 +    typedef typename TR::Digraph Digraph;
    1.54      /// The type of the flow amounts, capacity bounds and supply values
    1.55 -    typedef V Value;
    1.56 +    typedef typename TR::Value Value;
    1.57      /// The type of the arc costs
    1.58 -    typedef C Cost;
    1.59 +    typedef typename TR::Cost Cost;
    1.60 +
    1.61 +    /// The type of the heap used for internal Dijkstra computations
    1.62 +    typedef typename TR::Heap Heap;
    1.63 +
    1.64 +    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
    1.65 +    typedef TR Traits;
    1.66  
    1.67    public:
    1.68  
    1.69 @@ -92,8 +132,6 @@
    1.70  
    1.71      TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    1.72  
    1.73 -    typedef std::vector<Arc> ArcVector;
    1.74 -    typedef std::vector<Node> NodeVector;
    1.75      typedef std::vector<int> IntVector;
    1.76      typedef std::vector<bool> BoolVector;
    1.77      typedef std::vector<Value> ValueVector;
    1.78 @@ -155,9 +193,6 @@
    1.79      // potentials according to the found distance labels.
    1.80      class ResidualDijkstra
    1.81      {
    1.82 -      typedef RangeMap<int> HeapCrossRef;
    1.83 -      typedef BinHeap<Cost, HeapCrossRef> Heap;
    1.84 -
    1.85      private:
    1.86  
    1.87        int _node_num;
    1.88 @@ -182,7 +217,7 @@
    1.89        {}
    1.90  
    1.91        int run(int s, Value delta = 1) {
    1.92 -        HeapCrossRef heap_cross_ref(_node_num, Heap::PRE_HEAP);
    1.93 +        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
    1.94          Heap heap(heap_cross_ref);
    1.95          heap.push(s, 0);
    1.96          _pred[s] = -1;
    1.97 @@ -233,6 +268,32 @@
    1.98  
    1.99    public:
   1.100  
   1.101 +    /// \name Named Template Parameters
   1.102 +    /// @{
   1.103 +
   1.104 +    template <typename T>
   1.105 +    struct SetHeapTraits : public Traits {
   1.106 +      typedef T Heap;
   1.107 +    };
   1.108 +
   1.109 +    /// \brief \ref named-templ-param "Named parameter" for setting
   1.110 +    /// \c Heap type.
   1.111 +    ///
   1.112 +    /// \ref named-templ-param "Named parameter" for setting \c Heap
   1.113 +    /// type, which is used for internal Dijkstra computations.
   1.114 +    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
   1.115 +    /// its priority type must be \c Cost and its cross reference type
   1.116 +    /// must be \ref RangeMap "RangeMap<int>".
   1.117 +    template <typename T>
   1.118 +    struct SetHeap
   1.119 +      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
   1.120 +      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
   1.121 +    };
   1.122 +
   1.123 +    /// @}
   1.124 +
   1.125 +  public:
   1.126 +
   1.127      /// \brief Constructor.
   1.128      ///
   1.129      /// The constructor of the class.
   1.130 @@ -431,6 +492,7 @@
   1.131      /// @}
   1.132  
   1.133      /// \name Execution control
   1.134 +    /// The algorithm can be executed using \ref run().
   1.135  
   1.136      /// @{
   1.137  
   1.138 @@ -747,7 +809,7 @@
   1.139  
   1.140      // Execute the capacity scaling algorithm
   1.141      ProblemType startWithScaling() {
   1.142 -      // Process capacity scaling phases
   1.143 +      // Perform capacity scaling phases
   1.144        int s, t;
   1.145        int phase_cnt = 0;
   1.146        int factor = 4;