# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1249649560 -7200
# Node ID 93cd93e82f9b5aed29a1b15b8c8a9c3d42259655
# Parent  03887b5e0f6fa77571cf1dc76f655ba2f286acef
Add a detailed test file for MinMeanCycle and fix test_tools.h (#179)

diff -r 03887b5e0f6f -r 93cd93e82f9b lemon/min_mean_cycle.h
--- a/lemon/min_mean_cycle.h	Thu Aug 06 20:31:04 2009 +0200
+++ b/lemon/min_mean_cycle.h	Fri Aug 07 14:52:40 2009 +0200
@@ -25,6 +25,7 @@
 /// \brief Howard's algorithm for finding a minimum mean cycle.
 
 #include <vector>
+#include <limits>
 #include <lemon/core.h>
 #include <lemon/path.h>
 #include <lemon/tolerance.h>
diff -r 03887b5e0f6f -r 93cd93e82f9b test/CMakeLists.txt
--- a/test/CMakeLists.txt	Thu Aug 06 20:31:04 2009 +0200
+++ b/test/CMakeLists.txt	Fri Aug 07 14:52:40 2009 +0200
@@ -31,6 +31,7 @@
   matching_test
   min_cost_arborescence_test
   min_cost_flow_test
+  min_mean_cycle_test
   path_test
   preflow_test
   radix_sort_test
diff -r 03887b5e0f6f -r 93cd93e82f9b test/Makefile.am
--- a/test/Makefile.am	Thu Aug 06 20:31:04 2009 +0200
+++ b/test/Makefile.am	Fri Aug 07 14:52:40 2009 +0200
@@ -29,6 +29,7 @@
 	test/matching_test \
 	test/min_cost_arborescence_test \
 	test/min_cost_flow_test \
+	test/min_mean_cycle_test \
 	test/path_test \
 	test/preflow_test \
 	test/radix_sort_test \
@@ -76,6 +77,7 @@
 test_matching_test_SOURCES = test/matching_test.cc
 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_preflow_test_SOURCES = test/preflow_test.cc
 test_radix_sort_test_SOURCES = test/radix_sort_test.cc
diff -r 03887b5e0f6f -r 93cd93e82f9b test/min_mean_cycle_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/min_mean_cycle_test.cc	Fri Aug 07 14:52:40 2009 +0200
@@ -0,0 +1,184 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+#include <sstream>
+
+#include <lemon/smart_graph.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/min_mean_cycle.h>
+#include <lemon/path.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concept_check.h>
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+char test_lgf[] =
+  "@nodes\n"
+  "label\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@arcs\n"
+  "    len1 len2 len3 len4  c1 c2 c3 c4\n"
+  "1 2    1    1    1    1   0  0  0  0\n"
+  "2 4    5    5    5    5   1  0  0  0\n"
+  "2 3    8    8    8    8   0  0  0  0\n"
+  "3 2   -2    0    0    0   1  0  0  0\n"
+  "3 4    4    4    4    4   0  0  0  0\n"
+  "3 7   -4   -4   -4   -4   0  0  0  0\n"
+  "4 1    2    2    2    2   0  0  0  0\n"
+  "4 3    3    3    3    3   1  0  0  0\n"
+  "4 4    3    3    0    0   0  0  1  0\n"
+  "5 2    4    4    4    4   0  0  0  0\n"
+  "5 6    3    3    3    3   0  1  0  0\n"
+  "6 5    2    2    2    2   0  1  0  0\n"
+  "6 4   -1   -1   -1   -1   0  0  0  0\n"
+  "6 7    1    1    1    1   0  0  0  0\n"
+  "7 7    4    4    4   -1   0  0  0  1\n";
+
+                        
+// Check the interface of an MMC algorithm
+template <typename GR, typename Value>
+struct MmcClassConcept
+{
+  template <typename MMC>
+  struct Constraints {
+    void constraints() {
+      const Constraints& me = *this;
+
+      typedef typename MMC
+        ::template SetPath<ListPath<GR> >
+        ::template SetLargeValue<Value>
+        ::Create MmcAlg;
+      MmcAlg mmc(me.g, me.length);
+      const MmcAlg& const_mmc = mmc;
+      
+      b = mmc.cycle(p).run();
+      b = mmc.findMinMean();
+      b = mmc.findCycle();
+
+      v = const_mmc.cycleLength();
+      i = const_mmc.cycleArcNum();
+      d = const_mmc.cycleMean();
+      p = const_mmc.cycle();
+    }
+
+    typedef concepts::ReadMap<typename GR::Arc, Value> LM;
+  
+    GR g;
+    LM length;
+    ListPath<GR> p;
+    Value v;
+    int i;
+    double d;
+    bool b;
+  };
+};
+
+// Perform a test with the given parameters
+template <typename MMC>
+void checkMmcAlg(const SmartDigraph& gr,
+                 const SmartDigraph::ArcMap<int>& lm,
+                 const SmartDigraph::ArcMap<int>& cm,
+                 int length, int size) {
+  MMC alg(gr, lm);
+  alg.findMinMean();
+  check(alg.cycleMean() == static_cast<double>(length) / size,
+        "Wrong cycle mean");
+  alg.findCycle();
+  check(alg.cycleLength() == length && alg.cycleArcNum() == size,
+        "Wrong path");
+  SmartDigraph::ArcMap<int> cycle(gr, 0);
+  for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
+    ++cycle[a];
+  }
+  for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
+    check(cm[a] == cycle[a], "Wrong path");
+  }
+}
+
+// Class for comparing types
+template <typename T1, typename T2>
+struct IsSameType {
+  static const int result = 0;
+};
+
+template <typename T>
+struct IsSameType<T,T> {
+  static const int result = 1;
+};
+
+
+int main() {
+  #ifdef LEMON_HAVE_LONG_LONG
+    typedef long long long_int;
+  #else
+    typedef long long_int;
+  #endif
+
+  // Check the interface
+  {
+    typedef concepts::Digraph GR;
+    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
+    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
+    
+    checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
+    checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
+  
+    if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)
+      check(false, "Wrong LargeValue type");
+    if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)
+      check(false, "Wrong LargeValue type");
+  }
+
+  // Run various tests
+  {
+    typedef SmartDigraph GR;
+    DIGRAPH_TYPEDEFS(GR);
+    
+    GR gr;
+    IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
+    IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
+    
+    std::istringstream input(test_lgf);
+    digraphReader(gr, input).
+      arcMap("len1", l1).
+      arcMap("len2", l2).
+      arcMap("len3", l3).
+      arcMap("len4", l4).
+      arcMap("c1", c1).
+      arcMap("c2", c2).
+      arcMap("c3", c3).
+      arcMap("c4", c4).
+      run();
+
+    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1,  6, 3);
+    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2,  5, 2);
+    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3,  0, 1);
+    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+  }
+
+  return 0;
+}
diff -r 03887b5e0f6f -r 93cd93e82f9b test/test_tools.h
--- a/test/test_tools.h	Thu Aug 06 20:31:04 2009 +0200
+++ b/test/test_tools.h	Fri Aug 07 14:52:40 2009 +0200
@@ -37,10 +37,14 @@
 ///\code check(0==1,"This is obviously false.");\endcode will
 ///print something like this (and then exits).
 ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
-#define check(rc, msg) \
-  if(!(rc)) { \
-    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
-    abort(); \
-  } else { } \
+#define check(rc, msg)                                                  \
+  {                                                                     \
+    if(!(rc)) {                                                         \
+      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
+                << msg << std::endl;                                    \
+      abort();                                                          \
+    } else { }                                                          \
+  }                                                                     \
+    
 
 #endif