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/path.h>
25 #include <lemon/concepts/digraph.h>
26 #include <lemon/concept_check.h>
28 #include <lemon/karp.h>
29 #include <lemon/howard.h>
31 #include "test_tools.h"
33 using namespace lemon;
46 " len1 len2 len3 len4 c1 c2 c3 c4\n"
47 "1 2 1 1 1 1 0 0 0 0\n"
48 "2 4 5 5 5 5 1 0 0 0\n"
49 "2 3 8 8 8 8 0 0 0 0\n"
50 "3 2 -2 0 0 0 1 0 0 0\n"
51 "3 4 4 4 4 4 0 0 0 0\n"
52 "3 7 -4 -4 -4 -4 0 0 0 0\n"
53 "4 1 2 2 2 2 0 0 0 0\n"
54 "4 3 3 3 3 3 1 0 0 0\n"
55 "4 4 3 3 0 0 0 0 1 0\n"
56 "5 2 4 4 4 4 0 0 0 0\n"
57 "5 6 3 3 3 3 0 1 0 0\n"
58 "6 5 2 2 2 2 0 1 0 0\n"
59 "6 4 -1 -1 -1 -1 0 0 0 0\n"
60 "6 7 1 1 1 1 0 0 0 0\n"
61 "7 7 4 4 4 -1 0 0 0 1\n";
64 // Check the interface of an MMC algorithm
65 template <typename GR, typename Value>
66 struct MmcClassConcept
68 template <typename MMC>
71 const Constraints& me = *this;
74 ::template SetPath<ListPath<GR> >
75 ::template SetLargeValue<Value>
77 MmcAlg mmc(me.g, me.length);
78 const MmcAlg& const_mmc = mmc;
80 b = mmc.cycle(p).run();
81 b = mmc.findMinMean();
84 v = const_mmc.cycleLength();
85 i = const_mmc.cycleArcNum();
86 d = const_mmc.cycleMean();
87 p = const_mmc.cycle();
90 typedef concepts::ReadMap<typename GR::Arc, Value> LM;
102 // Perform a test with the given parameters
103 template <typename MMC>
104 void checkMmcAlg(const SmartDigraph& gr,
105 const SmartDigraph::ArcMap<int>& lm,
106 const SmartDigraph::ArcMap<int>& cm,
107 int length, int size) {
110 check(alg.cycleMean() == static_cast<double>(length) / size,
113 check(alg.cycleLength() == length && alg.cycleArcNum() == size,
115 SmartDigraph::ArcMap<int> cycle(gr, 0);
116 for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
119 for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
120 check(cm[a] == cycle[a], "Wrong path");
124 // Class for comparing types
125 template <typename T1, typename T2>
127 static const int result = 0;
130 template <typename T>
131 struct IsSameType<T,T> {
132 static const int result = 1;
137 #ifdef LEMON_HAVE_LONG_LONG
138 typedef long long long_int;
140 typedef long long_int;
143 // Check the interface
145 typedef concepts::Digraph GR;
148 checkConcept< MmcClassConcept<GR, int>,
149 Karp<GR, concepts::ReadMap<GR::Arc, int> > >();
150 checkConcept< MmcClassConcept<GR, float>,
151 Karp<GR, concepts::ReadMap<GR::Arc, float> > >();
154 checkConcept< MmcClassConcept<GR, int>,
155 Howard<GR, concepts::ReadMap<GR::Arc, int> > >();
156 checkConcept< MmcClassConcept<GR, float>,
157 Howard<GR, concepts::ReadMap<GR::Arc, float> > >();
159 if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue,
160 long_int>::result == 0) check(false, "Wrong LargeValue type");
161 if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue,
162 double>::result == 0) check(false, "Wrong LargeValue type");
167 typedef SmartDigraph GR;
168 DIGRAPH_TYPEDEFS(GR);
171 IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
172 IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
174 std::istringstream input(test_lgf);
175 digraphReader(gr, input).
187 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1, 6, 3);
188 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2, 5, 2);
189 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3, 0, 1);
190 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1);
193 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1, 6, 3);
194 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2, 5, 2);
195 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3, 0, 1);
196 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);