Changeset 807:78071e00de00 in lemon-main for lemon

Timestamp:

11/12/09 23:27:21 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Rebase:

33336539313938363364303661336366373764356634303962303164663663353665313137343963

Message:

Traits class + a named parameter for CapacityScaling? (#180)
to specify the heap used in internal Dijkstra computations.

File:

• lemon/capacity_scaling.h (modified) (8 diffs)

lemon/capacity_scaling.h

@@ -31 +31 @@
 
 namespace lemon {
+
+  /// \brief Default traits class of CapacityScaling algorithm.
+  ///
+  /// Default traits class of CapacityScaling algorithm.
+  /// \tparam GR Digraph type.
+  /// \tparam V The value type used for flow amounts, capacity bounds
+  /// and supply values. By default it is \c int.
+  /// \tparam C The value type used for costs and potentials.
+  /// By default it is the same as \c V.
+  template <typename GR, typename V = int, typename C = V>
+  struct CapacityScalingDefaultTraits
+  {
+    /// The type of the digraph
+    typedef GR Digraph;
+    /// The type of the flow amounts, capacity bounds and supply values
+    typedef V Value;
+    /// The type of the arc costs
+    typedef C Cost;
+
+    /// \brief The type of the heap used for internal Dijkstra computations.
+    ///
+    /// The type of the heap used for internal Dijkstra computations.
+    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
+    /// its priority type must be \c Cost and its cross reference type
+    /// must be \ref RangeMap "RangeMap<int>".
+    typedef BinHeap<Cost, RangeMap<int> > Heap;
+  };
 
   /// \addtogroup min_cost_flow_algs
@@ -58 +85 @@
   /// \warning This algorithm does not support negative costs for such
   /// arcs that have infinite upper bound.
-  template <typename GR, typename V = int, typename C = V>
+#ifdef DOXYGEN
+  template <typename GR, typename V, typename C, typename TR>
+#else
+  template < typename GR, typename V = int, typename C = V,
+             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
+#endif
   class CapacityScaling
   {
   public:
 
+    /// The type of the digraph
+    typedef typename TR::Digraph Digraph;
     /// The type of the flow amounts, capacity bounds and supply values
-    typedef V Value;
+    typedef typename TR::Value Value;
     /// The type of the arc costs
-    typedef C Cost;
+    typedef typename TR::Cost Cost;
+
+    /// The type of the heap used for internal Dijkstra computations
+    typedef typename TR::Heap Heap;
+
+    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
+    typedef TR Traits;
 
   public:
@@ -93 +133 @@
     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 
-    typedef std::vector<Arc> ArcVector;
-    typedef std::vector<Node> NodeVector;
     typedef std::vector<int> IntVector;
     typedef std::vector<bool> BoolVector;
@@ -156 +194 @@
     class ResidualDijkstra
     {
-      typedef RangeMap<int> HeapCrossRef;
-      typedef BinHeap<Cost, HeapCrossRef> Heap;
-
     private:
 
@@ -183 +218 @@
 
       int run(int s, Value delta = 1) {
-        HeapCrossRef heap_cross_ref(_node_num, Heap::PRE_HEAP);
+        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
         Heap heap(heap_cross_ref);
         heap.push(s, 0);
@@ -234 +269 @@
   public:
 
+    /// \name Named Template Parameters
+    /// @{
+
+    template <typename T>
+    struct SetHeapTraits : public Traits {
+      typedef T Heap;
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting
+    /// \c Heap type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting \c Heap
+    /// type, which is used for internal Dijkstra computations.
+    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
+    /// its priority type must be \c Cost and its cross reference type
+    /// must be \ref RangeMap "RangeMap<int>".
+    template <typename T>
+    struct SetHeap
+      : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
+      typedef  CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
+    };
+
+    /// @}
+
+  public:
+
     /// \brief Constructor.
     ///
@@ -432 +493 @@
 
     /// \name Execution control
+    /// The algorithm can be executed using \ref run().
 
     /// @{
@@ -748 +810 @@
     // Execute the capacity scaling algorithm
     ProblemType startWithScaling() {
-      // Process capacity scaling phases
+      // Perform capacity scaling phases
       int s, t;
       int phase_cnt = 0;