# 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