|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
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. |
|
12 * |
|
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 |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <sstream> |
|
21 |
|
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> |
|
28 |
|
29 #include "test_tools.h" |
|
30 |
|
31 using namespace lemon; |
|
32 |
|
33 char test_lgf[] = |
|
34 "@nodes\n" |
|
35 "label\n" |
|
36 "1\n" |
|
37 "2\n" |
|
38 "3\n" |
|
39 "4\n" |
|
40 "5\n" |
|
41 "6\n" |
|
42 "7\n" |
|
43 "@arcs\n" |
|
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"; |
|
60 |
|
61 |
|
62 // Check the interface of an MMC algorithm |
|
63 template <typename GR, typename Value> |
|
64 struct MmcClassConcept |
|
65 { |
|
66 template <typename MMC> |
|
67 struct Constraints { |
|
68 void constraints() { |
|
69 const Constraints& me = *this; |
|
70 |
|
71 typedef typename MMC |
|
72 ::template SetPath<ListPath<GR> > |
|
73 ::template SetLargeValue<Value> |
|
74 ::Create MmcAlg; |
|
75 MmcAlg mmc(me.g, me.length); |
|
76 const MmcAlg& const_mmc = mmc; |
|
77 |
|
78 b = mmc.cycle(p).run(); |
|
79 b = mmc.findMinMean(); |
|
80 b = mmc.findCycle(); |
|
81 |
|
82 v = const_mmc.cycleLength(); |
|
83 i = const_mmc.cycleArcNum(); |
|
84 d = const_mmc.cycleMean(); |
|
85 p = const_mmc.cycle(); |
|
86 } |
|
87 |
|
88 typedef concepts::ReadMap<typename GR::Arc, Value> LM; |
|
89 |
|
90 GR g; |
|
91 LM length; |
|
92 ListPath<GR> p; |
|
93 Value v; |
|
94 int i; |
|
95 double d; |
|
96 bool b; |
|
97 }; |
|
98 }; |
|
99 |
|
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) { |
|
106 MMC alg(gr, lm); |
|
107 alg.findMinMean(); |
|
108 check(alg.cycleMean() == static_cast<double>(length) / size, |
|
109 "Wrong cycle mean"); |
|
110 alg.findCycle(); |
|
111 check(alg.cycleLength() == length && alg.cycleArcNum() == size, |
|
112 "Wrong path"); |
|
113 SmartDigraph::ArcMap<int> cycle(gr, 0); |
|
114 for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) { |
|
115 ++cycle[a]; |
|
116 } |
|
117 for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) { |
|
118 check(cm[a] == cycle[a], "Wrong path"); |
|
119 } |
|
120 } |
|
121 |
|
122 // Class for comparing types |
|
123 template <typename T1, typename T2> |
|
124 struct IsSameType { |
|
125 static const int result = 0; |
|
126 }; |
|
127 |
|
128 template <typename T> |
|
129 struct IsSameType<T,T> { |
|
130 static const int result = 1; |
|
131 }; |
|
132 |
|
133 |
|
134 int main() { |
|
135 #ifdef LEMON_HAVE_LONG_LONG |
|
136 typedef long long long_int; |
|
137 #else |
|
138 typedef long long_int; |
|
139 #endif |
|
140 |
|
141 // Check the interface |
|
142 { |
|
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; |
|
146 |
|
147 checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>(); |
|
148 checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>(); |
|
149 |
|
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"); |
|
154 } |
|
155 |
|
156 // Run various tests |
|
157 { |
|
158 typedef SmartDigraph GR; |
|
159 DIGRAPH_TYPEDEFS(GR); |
|
160 |
|
161 GR gr; |
|
162 IntArcMap l1(gr), l2(gr), l3(gr), l4(gr); |
|
163 IntArcMap c1(gr), c2(gr), c3(gr), c4(gr); |
|
164 |
|
165 std::istringstream input(test_lgf); |
|
166 digraphReader(gr, input). |
|
167 arcMap("len1", l1). |
|
168 arcMap("len2", l2). |
|
169 arcMap("len3", l3). |
|
170 arcMap("len4", l4). |
|
171 arcMap("c1", c1). |
|
172 arcMap("c2", c2). |
|
173 arcMap("c3", c3). |
|
174 arcMap("c4", c4). |
|
175 run(); |
|
176 |
|
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); |
|
181 } |
|
182 |
|
183 return 0; |
|
184 } |