summaryrefslogtreecommitdiff
path: root/lemon/test/min_mean_cycle_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'lemon/test/min_mean_cycle_test.cc')
-rw-r--r--lemon/test/min_mean_cycle_test.cc216
1 files changed, 216 insertions, 0 deletions
diff --git a/lemon/test/min_mean_cycle_test.cc b/lemon/test/min_mean_cycle_test.cc
new file mode 100644
index 0000000..e9fb8da
--- /dev/null
+++ b/lemon/test/min_mean_cycle_test.cc
@@ -0,0 +1,216 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * 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/path.h>
+#include <lemon/concepts/digraph.h>
+#include <lemon/concept_check.h>
+
+#include <lemon/karp_mmc.h>
+#include <lemon/hartmann_orlin_mmc.h>
+#include <lemon/howard_mmc.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 Cost>
+struct MmcClassConcept
+{
+ template <typename MMC>
+ struct Constraints {
+ void constraints() {
+ const Constraints& me = *this;
+
+ typedef typename MMC
+ ::template SetPath<ListPath<GR> >
+ ::template SetLargeCost<Cost>
+ ::Create MmcAlg;
+ MmcAlg mmc(me.g, me.cost);
+ const MmcAlg& const_mmc = mmc;
+
+ typename MmcAlg::Tolerance tol = const_mmc.tolerance();
+ mmc.tolerance(tol);
+
+ b = mmc.cycle(p).run();
+ b = mmc.findCycleMean();
+ b = mmc.findCycle();
+
+ v = const_mmc.cycleCost();
+ i = const_mmc.cycleSize();
+ d = const_mmc.cycleMean();
+ p = const_mmc.cycle();
+ }
+
+ typedef concepts::ReadMap<typename GR::Arc, Cost> CM;
+
+ GR g;
+ CM cost;
+ ListPath<GR> p;
+ Cost 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 cost, int size) {
+ MMC alg(gr, lm);
+ alg.findCycleMean();
+ check(alg.cycleMean() == static_cast<double>(cost) / size,
+ "Wrong cycle mean");
+ alg.findCycle();
+ check(alg.cycleCost() == cost && alg.cycleSize() == 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;
+
+ // KarpMmc
+ checkConcept< MmcClassConcept<GR, int>,
+ KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
+ checkConcept< MmcClassConcept<GR, float>,
+ KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
+
+ // HartmannOrlinMmc
+ checkConcept< MmcClassConcept<GR, int>,
+ HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
+ checkConcept< MmcClassConcept<GR, float>,
+ HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
+
+ // HowardMmc
+ checkConcept< MmcClassConcept<GR, int>,
+ HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >();
+ checkConcept< MmcClassConcept<GR, float>,
+ HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >();
+
+ check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> >
+ ::LargeCost, long_int>::result == 1), "Wrong LargeCost type");
+ check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> >
+ ::LargeCost, double>::result == 1), "Wrong LargeCost 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();
+
+ // Karp
+ checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
+ checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
+ checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
+ checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+
+ // HartmannOrlin
+ checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
+ checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
+ checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
+ checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+
+ // Howard
+ checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3);
+ checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2);
+ checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1);
+ checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+ }
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.46.2) at 2024-11-10 07:28:45 +0000