Changeset 1228:45befc97b1bc in lemon

Timestamp:

02/28/13 23:44:35 (11 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Merge test files of Preflow and EdmondsKarp? (#177)

Files:

• lemon/edmonds_karp.h (modified) (1 diff)
• test/CMakeLists.txt (modified) (3 diffs)
• test/edmonds_karp_test.cc (deleted)
• test/max_flow_test.cc (moved) (moved from test/preflow_test.cc) (7 diffs)

lemon/edmonds_karp.h

@@ -168 +168 @@
   public:
 
+    typedef EdmondsKarp Create;
+
     ///\name Named template parameters
 

test/CMakeLists.txt

@@ -26 +26 @@
   dim_test
   edge_set_test
-  edmonds_karp_test
   error_test
   euler_test
@@ -43 +42 @@
   max_cardinality_search_test
   max_clique_test
+  max_flow_test
   min_cost_arborescence_test
   min_cost_flow_test
@@ -49 +49 @@
   path_test
   planarity_test
-  preflow_test
   radix_sort_test
   random_test

test/max_flow_test.cc

@@ -22 +22 @@
 #include <lemon/smart_graph.h>
 #include <lemon/preflow.h>
+#include <lemon/edmonds_karp.h>
 #include <lemon/concepts/digraph.h>
 #include <lemon/concepts/maps.h>
@@ -65 +66 @@
   "target 8\n";
 
+
+// Checks the general interface of a max flow algorithm
+template <typename GR, typename CAP>
+struct MaxFlowClassConcept
+{
+
+  template <typename MF>
+  struct Constraints {
+
+    typedef typename GR::Node Node;
+    typedef typename GR::Arc Arc;
+    typedef typename CAP::Value Value;
+    typedef concepts::ReadWriteMap<Arc, Value> FlowMap;
+    typedef concepts::WriteMap<Node, bool> CutMap;
+
+    GR g;
+    Node n;
+    Arc e;
+    CAP cap;
+    FlowMap flow;
+    CutMap cut;
+    Value v;
+    bool b;
+
+    void constraints() {
+      checkConcept<concepts::Digraph, GR>();
+
+      const Constraints& me = *this;
+
+      typedef typename MF
+          ::template SetFlowMap<FlowMap>
+          ::Create MaxFlowType;
+      typedef typename MF::Create MaxFlowType2;
+      MaxFlowType max_flow(me.g, me.cap, me.n, me.n);
+      const MaxFlowType& const_max_flow = max_flow;
+
+      max_flow
+          .capacityMap(cap)
+          .flowMap(flow)
+          .source(n)
+          .target(n);
+
+      typename MaxFlowType::Tolerance tol = const_max_flow.tolerance();
+      max_flow.tolerance(tol);
+
+      max_flow.init();
+      max_flow.init(cap);
+      max_flow.run();
+
+      v = const_max_flow.flowValue();
+      v = const_max_flow.flow(e);
+      const FlowMap& fm = const_max_flow.flowMap();
+
+      b = const_max_flow.minCut(n);
+      const_max_flow.minCutMap(cut);
+
+      ignore_unused_variable_warning(fm);
+    }
+
+  };
+
+};
+
+// Checks the specific parts of Preflow's interface
 void checkPreflowCompile()
 {
-  typedef int VType;
+  typedef int Value;
   typedef concepts::Digraph Digraph;
-
-  typedef Digraph::Node Node;
-  typedef Digraph::Arc Arc;
-  typedef concepts::ReadMap<Arc,VType> CapMap;
-  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
-  typedef concepts::WriteMap<Node,bool> CutMap;
-
+  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
   typedef Elevator<Digraph, Digraph::Node> Elev;
   typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 
   Digraph g;
-  Node n;
-  Arc e;
+  Digraph::Node n;
   CapMap cap;
-  FlowMap flow;
-  CutMap cut;
-  VType v;
-  bool b;
-  ignore_unused_variable_warning(v,b);
 
   typedef Preflow<Digraph, CapMap>
-            ::SetFlowMap<FlowMap>
-            ::SetElevator<Elev>
-            ::SetStandardElevator<LinkedElev>
-            ::Create PreflowType;
+      ::SetElevator<Elev>
+      ::SetStandardElevator<LinkedElev>
+      ::Create PreflowType;
   PreflowType preflow_test(g, cap, n, n);
   const PreflowType& const_preflow_test = preflow_test;
@@ -99 +151 @@
   const PreflowType::Elevator& elev = const_preflow_test.elevator();
   preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
-  PreflowType::Tolerance tol = const_preflow_test.tolerance();
-  preflow_test.tolerance(tol);
-
-  preflow_test
-    .capacityMap(cap)
-    .flowMap(flow)
-    .source(n)
-    .target(n);
-
-  preflow_test.init();
-  preflow_test.init(cap);
+
+  bool b = preflow_test.init(cap);
   preflow_test.startFirstPhase();
   preflow_test.startSecondPhase();
-  preflow_test.run();
   preflow_test.runMinCut();
 
-  v = const_preflow_test.flowValue();
-  v = const_preflow_test.flow(e);
-  const FlowMap& fm = const_preflow_test.flowMap();
-  b = const_preflow_test.minCut(n);
-  const_preflow_test.minCutMap(cut);
-
-  ignore_unused_variable_warning(fm);
-}
-
-int cutValue (const SmartDigraph& g,
+  ignore_unused_variable_warning(b);
+}
+
+// Checks the specific parts of EdmondsKarp's interface
+void checkEdmondsKarpCompile()
+{
+  typedef int Value;
+  typedef concepts::Digraph Digraph;
+  typedef concepts::ReadMap<Digraph::Arc, Value> CapMap;
+  typedef Elevator<Digraph, Digraph::Node> Elev;
+  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
+
+  Digraph g;
+  Digraph::Node n;
+  CapMap cap;
+
+  EdmondsKarp<Digraph, CapMap> ek_test(g, cap, n, n);
+
+  ek_test.init(cap);
+  bool b = ek_test.checkedInit(cap);
+  b = ek_test.augment();
+  ek_test.start();
+
+  ignore_unused_variable_warning(b);
+}
+
+
+template <typename T>
+T cutValue (const SmartDigraph& g,
               const SmartDigraph::NodeMap<bool>& cut,
-              const SmartDigraph::ArcMap<int>& cap) {
-
-  int c=0;
+              const SmartDigraph::ArcMap<T>& cap) {
+
+  T c=0;
   for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
     if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
@@ -135 +196 @@
 }
 
+template <typename T>
 bool checkFlow(const SmartDigraph& g,
-               const SmartDigraph::ArcMap<int>& flow,
-               const SmartDigraph::ArcMap<int>& cap,
+               const SmartDigraph::ArcMap<T>& flow,
+               const SmartDigraph::ArcMap<T>& cap,
                SmartDigraph::Node s, SmartDigraph::Node t) {
 
@@ -146 +208 @@
   for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
     if (n == s || n == t) continue;
-    int sum = 0;
+    T sum = 0;
     for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
       sum += flow[e];
@@ -181 +243 @@
 }
 
-
-int main() {
-
+template <typename MF, typename SF>
+void checkMaxFlowAlg() {
   typedef SmartDigraph Digraph;
-
-  typedef Digraph::Node Node;
-  typedef Digraph::NodeIt NodeIt;
-  typedef Digraph::ArcIt ArcIt;
-  typedef Digraph::ArcMap<int> CapMap;
-  typedef Digraph::ArcMap<int> FlowMap;
-  typedef Digraph::NodeMap<bool> CutMap;
-
-  typedef Preflow<Digraph, CapMap> PType;
+  DIGRAPH_TYPEDEFS(Digraph);
+
+  typedef typename MF::Value Value;
+  typedef Digraph::ArcMap<Value> CapMap;
+  typedef CapMap FlowMap;
+  typedef BoolNodeMap CutMap;
 
   Digraph g;
@@ -199 +257 @@
   CapMap cap(g);
   std::istringstream input(test_lgf);
-  DigraphReader<Digraph>(g,input).
-    arcMap("capacity", cap).
-    node("source",s).
-    node("target",t).
-    run();
-
-  PType preflow_test(g, cap, s, t);
-  preflow_test.run();
-
-  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+  DigraphReader<Digraph>(g,input)
+      .arcMap("capacity", cap)
+      .node("source",s)
+      .node("target",t)
+      .run();
+
+  MF max_flow(g, cap, s, t);
+  max_flow.run();
+
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
         "The flow is not feasible.");
 
   CutMap min_cut(g);
-  preflow_test.minCutMap(min_cut);
-  int min_cut_value=cutValue(g,min_cut,cap);
-
-  check(preflow_test.flowValue() == min_cut_value,
-        "The max flow value is not equal to the three min cut values.");
+  max_flow.minCutMap(min_cut);
+  Value min_cut_value = cutValue(g, min_cut, cap);
+
+  check(max_flow.flowValue() == min_cut_value,
+        "The max flow value is not equal to the min cut value.");
 
   FlowMap flow(g);
-  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
-
-  int flow_value=preflow_test.flowValue();
-
-  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
-  preflow_test.init(flow);
-  preflow_test.startFirstPhase();
+  for (ArcIt e(g); e != INVALID; ++e) flow[e] = max_flow.flowMap()[e];
+
+  Value flow_value = max_flow.flowValue();
+
+  for (ArcIt e(g); e != INVALID; ++e) cap[e] = 2 * cap[e];
+  max_flow.init(flow);
+
+  SF::startFirstPhase(max_flow);       // start first phase of the algorithm
 
   CutMap min_cut1(g);
-  preflow_test.minCutMap(min_cut1);
-  min_cut_value=cutValue(g,min_cut1,cap);
-
-  check(preflow_test.flowValue() == min_cut_value &&
-        min_cut_value == 2*flow_value,
+  max_flow.minCutMap(min_cut1);
+  min_cut_value = cutValue(g, min_cut1, cap);
+
+  check(max_flow.flowValue() == min_cut_value &&
+        min_cut_value == 2 * flow_value,
         "The max flow value or the min cut value is wrong.");
 
-  preflow_test.startSecondPhase();
-
-  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
+  SF::startSecondPhase(max_flow);       // start second phase of the algorithm
+
+  check(checkFlow(g, max_flow.flowMap(), cap, s, t),
         "The flow is not feasible.");
 
   CutMap min_cut2(g);
-  preflow_test.minCutMap(min_cut2);
-  min_cut_value=cutValue(g,min_cut2,cap);
-
-  check(preflow_test.flowValue() == min_cut_value &&
-        min_cut_value == 2*flow_value,
-        "The max flow value or the three min cut values were not doubled");
-
-
-  preflow_test.flowMap(flow);
-
-  NodeIt tmp1(g,s);
+  max_flow.minCutMap(min_cut2);
+  min_cut_value = cutValue(g, min_cut2, cap);
+
+  check(max_flow.flowValue() == min_cut_value &&
+        min_cut_value == 2 * flow_value,
+        "The max flow value or the min cut value was not doubled");
+
+
+  max_flow.flowMap(flow);
+
+  NodeIt tmp1(g, s);
   ++tmp1;
-  if ( tmp1 != INVALID ) s=tmp1;
-
-  NodeIt tmp2(g,t);
+  if (tmp1 != INVALID) s = tmp1;
+
+  NodeIt tmp2(g, t);
   ++tmp2;
-  if ( tmp2 != INVALID ) t=tmp2;
-
-  preflow_test.source(s);
-  preflow_test.target(t);
-
-  preflow_test.run();
+  if (tmp2 != INVALID) t = tmp2;
+
+  max_flow.source(s);
+  max_flow.target(t);
+
+  max_flow.run();
 
   CutMap min_cut3(g);
-  preflow_test.minCutMap(min_cut3);
-  min_cut_value=cutValue(g,min_cut3,cap);
-
-
-  check(preflow_test.flowValue() == min_cut_value,
-        "The max flow value or the three min cut values are incorrect.");
+  max_flow.minCutMap(min_cut3);
+  min_cut_value=cutValue(g, min_cut3, cap);
+
+  check(max_flow.flowValue() == min_cut_value,
+        "The max flow value or the min cut value is wrong.");
+}
+
+// Struct for calling start functions of a general max flow algorithm
+template <typename MF>
+struct GeneralStartFunctions {
+
+  static void startFirstPhase(MF& mf) {
+    mf.start();
+  }
+
+  static void startSecondPhase(MF& mf) {
+    ignore_unused_variable_warning(mf);
+  }
+
+};
+
+// Struct for calling start functions of Preflow
+template <typename MF>
+struct PreflowStartFunctions {
+
+  static void startFirstPhase(MF& mf) {
+    mf.startFirstPhase();
+  }
+
+  static void startSecondPhase(MF& mf) {
+    mf.startSecondPhase();
+  }
+
+};
+
+int main() {
+
+  typedef concepts::Digraph GR;
+  typedef concepts::ReadMap<GR::Arc, int> CM1;
+  typedef concepts::ReadMap<GR::Arc, double> CM2;
+
+  // Check the interface of Preflow
+  checkConcept< MaxFlowClassConcept<GR, CM1>,
+                Preflow<GR, CM1> >();
+  checkConcept< MaxFlowClassConcept<GR, CM2>,
+                Preflow<GR, CM2> >();
+
+  // Check the interface of EdmondsKarp
+  checkConcept< MaxFlowClassConcept<GR, CM1>,
+                EdmondsKarp<GR, CM1> >();
+  checkConcept< MaxFlowClassConcept<GR, CM2>,
+                EdmondsKarp<GR, CM2> >();
+
+  // Check Preflow
+  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<int> > PType1;
+  typedef Preflow<SmartDigraph, SmartDigraph::ArcMap<float> > PType2;
+  checkMaxFlowAlg<PType1, PreflowStartFunctions<PType1> >();
+  checkMaxFlowAlg<PType2, PreflowStartFunctions<PType2> >();
+  initFlowTest();
+  
+  // Check EdmondsKarp
+  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<int> > EKType1;
+  typedef EdmondsKarp<SmartDigraph, SmartDigraph::ArcMap<float> > EKType2;
+  checkMaxFlowAlg<EKType1, GeneralStartFunctions<EKType1> >();
+  checkMaxFlowAlg<EKType2, GeneralStartFunctions<EKType2> >();
 
   initFlowTest();