1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include <lemon/smart_graph.h>
23 #include <lemon/lgf_reader.h>
24 #include <lemon/min_mean_cycle.h>
25 #include <lemon/path.h>
26 #include <lemon/concepts/digraph.h>
27 #include <lemon/concept_check.h>
29 #include "test_tools.h"
31 using namespace lemon;
44 " len1 len2 len3 len4 c1 c2 c3 c4\n"
45 "1 2 1 1 1 1 0 0 0 0\n"
46 "2 4 5 5 5 5 1 0 0 0\n"
47 "2 3 8 8 8 8 0 0 0 0\n"
48 "3 2 -2 0 0 0 1 0 0 0\n"
49 "3 4 4 4 4 4 0 0 0 0\n"
50 "3 7 -4 -4 -4 -4 0 0 0 0\n"
51 "4 1 2 2 2 2 0 0 0 0\n"
52 "4 3 3 3 3 3 1 0 0 0\n"
53 "4 4 3 3 0 0 0 0 1 0\n"
54 "5 2 4 4 4 4 0 0 0 0\n"
55 "5 6 3 3 3 3 0 1 0 0\n"
56 "6 5 2 2 2 2 0 1 0 0\n"
57 "6 4 -1 -1 -1 -1 0 0 0 0\n"
58 "6 7 1 1 1 1 0 0 0 0\n"
59 "7 7 4 4 4 -1 0 0 0 1\n";
62 // Check the interface of an MMC algorithm
63 template <typename GR, typename Value>
64 struct MmcClassConcept
66 template <typename MMC>
69 const Constraints& me = *this;
72 ::template SetPath<ListPath<GR> >
73 ::template SetLargeValue<Value>
75 MmcAlg mmc(me.g, me.length);
76 const MmcAlg& const_mmc = mmc;
78 b = mmc.cycle(p).run();
79 b = mmc.findMinMean();
82 v = const_mmc.cycleLength();
83 i = const_mmc.cycleArcNum();
84 d = const_mmc.cycleMean();
85 p = const_mmc.cycle();
88 typedef concepts::ReadMap<typename GR::Arc, Value> LM;
100 // Perform a test with the given parameters
101 template <typename MMC>
102 void checkMmcAlg(const SmartDigraph& gr,
103 const SmartDigraph::ArcMap<int>& lm,
104 const SmartDigraph::ArcMap<int>& cm,
105 int length, int size) {
108 check(alg.cycleMean() == static_cast<double>(length) / size,
111 check(alg.cycleLength() == length && alg.cycleArcNum() == size,
113 SmartDigraph::ArcMap<int> cycle(gr, 0);
114 for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
117 for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
118 check(cm[a] == cycle[a], "Wrong path");
122 // Class for comparing types
123 template <typename T1, typename T2>
125 static const int result = 0;
128 template <typename T>
129 struct IsSameType<T,T> {
130 static const int result = 1;
135 #ifdef LEMON_HAVE_LONG_LONG
136 typedef long long long_int;
138 typedef long long_int;
141 // Check the interface
143 typedef concepts::Digraph GR;
144 typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
145 typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
147 checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
148 checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
150 if (IsSameType<IntMmcAlg::LargeValue, long_int>::result == 0)
151 check(false, "Wrong LargeValue type");
152 if (IsSameType<FloatMmcAlg::LargeValue, double>::result == 0)
153 check(false, "Wrong LargeValue type");
158 typedef SmartDigraph GR;
159 DIGRAPH_TYPEDEFS(GR);
162 IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
163 IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
165 std::istringstream input(test_lgf);
166 digraphReader(gr, input).
177 checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1, 6, 3);
178 checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2, 5, 2);
179 checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3, 0, 1);
180 checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);