23 #include <lemon/lgf_reader.h> |
23 #include <lemon/lgf_reader.h> |
24 #include <lemon/path.h> |
24 #include <lemon/path.h> |
25 #include <lemon/concepts/digraph.h> |
25 #include <lemon/concepts/digraph.h> |
26 #include <lemon/concept_check.h> |
26 #include <lemon/concept_check.h> |
27 |
27 |
28 #include <lemon/karp.h> |
28 #include <lemon/karp_mmc.h> |
29 #include <lemon/hartmann_orlin.h> |
29 #include <lemon/hartmann_orlin_mmc.h> |
30 #include <lemon/howard.h> |
30 #include <lemon/howard_mmc.h> |
31 |
31 |
32 #include "test_tools.h" |
32 #include "test_tools.h" |
33 |
33 |
34 using namespace lemon; |
34 using namespace lemon; |
35 |
35 |
61 "6 7 1 1 1 1 0 0 0 0\n" |
61 "6 7 1 1 1 1 0 0 0 0\n" |
62 "7 7 4 4 4 -1 0 0 0 1\n"; |
62 "7 7 4 4 4 -1 0 0 0 1\n"; |
63 |
63 |
64 |
64 |
65 // Check the interface of an MMC algorithm |
65 // Check the interface of an MMC algorithm |
66 template <typename GR, typename Value> |
66 template <typename GR, typename Cost> |
67 struct MmcClassConcept |
67 struct MmcClassConcept |
68 { |
68 { |
69 template <typename MMC> |
69 template <typename MMC> |
70 struct Constraints { |
70 struct Constraints { |
71 void constraints() { |
71 void constraints() { |
72 const Constraints& me = *this; |
72 const Constraints& me = *this; |
73 |
73 |
74 typedef typename MMC |
74 typedef typename MMC |
75 ::template SetPath<ListPath<GR> > |
75 ::template SetPath<ListPath<GR> > |
76 ::template SetLargeValue<Value> |
76 ::template SetLargeCost<Cost> |
77 ::Create MmcAlg; |
77 ::Create MmcAlg; |
78 MmcAlg mmc(me.g, me.length); |
78 MmcAlg mmc(me.g, me.cost); |
79 const MmcAlg& const_mmc = mmc; |
79 const MmcAlg& const_mmc = mmc; |
80 |
80 |
81 typename MmcAlg::Tolerance tol = const_mmc.tolerance(); |
81 typename MmcAlg::Tolerance tol = const_mmc.tolerance(); |
82 mmc.tolerance(tol); |
82 mmc.tolerance(tol); |
83 |
83 |
84 b = mmc.cycle(p).run(); |
84 b = mmc.cycle(p).run(); |
85 b = mmc.findMinMean(); |
85 b = mmc.findCycleMean(); |
86 b = mmc.findCycle(); |
86 b = mmc.findCycle(); |
87 |
87 |
88 v = const_mmc.cycleLength(); |
88 v = const_mmc.cycleCost(); |
89 i = const_mmc.cycleArcNum(); |
89 i = const_mmc.cycleSize(); |
90 d = const_mmc.cycleMean(); |
90 d = const_mmc.cycleMean(); |
91 p = const_mmc.cycle(); |
91 p = const_mmc.cycle(); |
92 } |
92 } |
93 |
93 |
94 typedef concepts::ReadMap<typename GR::Arc, Value> LM; |
94 typedef concepts::ReadMap<typename GR::Arc, Cost> CM; |
95 |
95 |
96 GR g; |
96 GR g; |
97 LM length; |
97 CM cost; |
98 ListPath<GR> p; |
98 ListPath<GR> p; |
99 Value v; |
99 Cost v; |
100 int i; |
100 int i; |
101 double d; |
101 double d; |
102 bool b; |
102 bool b; |
103 }; |
103 }; |
104 }; |
104 }; |
106 // Perform a test with the given parameters |
106 // Perform a test with the given parameters |
107 template <typename MMC> |
107 template <typename MMC> |
108 void checkMmcAlg(const SmartDigraph& gr, |
108 void checkMmcAlg(const SmartDigraph& gr, |
109 const SmartDigraph::ArcMap<int>& lm, |
109 const SmartDigraph::ArcMap<int>& lm, |
110 const SmartDigraph::ArcMap<int>& cm, |
110 const SmartDigraph::ArcMap<int>& cm, |
111 int length, int size) { |
111 int cost, int size) { |
112 MMC alg(gr, lm); |
112 MMC alg(gr, lm); |
113 alg.findMinMean(); |
113 alg.findCycleMean(); |
114 check(alg.cycleMean() == static_cast<double>(length) / size, |
114 check(alg.cycleMean() == static_cast<double>(cost) / size, |
115 "Wrong cycle mean"); |
115 "Wrong cycle mean"); |
116 alg.findCycle(); |
116 alg.findCycle(); |
117 check(alg.cycleLength() == length && alg.cycleArcNum() == size, |
117 check(alg.cycleCost() == cost && alg.cycleSize() == size, |
118 "Wrong path"); |
118 "Wrong path"); |
119 SmartDigraph::ArcMap<int> cycle(gr, 0); |
119 SmartDigraph::ArcMap<int> cycle(gr, 0); |
120 for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) { |
120 for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) { |
121 ++cycle[a]; |
121 ++cycle[a]; |
122 } |
122 } |
146 |
146 |
147 // Check the interface |
147 // Check the interface |
148 { |
148 { |
149 typedef concepts::Digraph GR; |
149 typedef concepts::Digraph GR; |
150 |
150 |
151 // Karp |
151 // KarpMmc |
152 checkConcept< MmcClassConcept<GR, int>, |
152 checkConcept< MmcClassConcept<GR, int>, |
153 Karp<GR, concepts::ReadMap<GR::Arc, int> > >(); |
153 KarpMmc<GR, concepts::ReadMap<GR::Arc, int> > >(); |
154 checkConcept< MmcClassConcept<GR, float>, |
154 checkConcept< MmcClassConcept<GR, float>, |
155 Karp<GR, concepts::ReadMap<GR::Arc, float> > >(); |
155 KarpMmc<GR, concepts::ReadMap<GR::Arc, float> > >(); |
156 |
156 |
157 // HartmannOrlin |
157 // HartmannOrlinMmc |
158 checkConcept< MmcClassConcept<GR, int>, |
158 checkConcept< MmcClassConcept<GR, int>, |
159 HartmannOrlin<GR, concepts::ReadMap<GR::Arc, int> > >(); |
159 HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, int> > >(); |
160 checkConcept< MmcClassConcept<GR, float>, |
160 checkConcept< MmcClassConcept<GR, float>, |
161 HartmannOrlin<GR, concepts::ReadMap<GR::Arc, float> > >(); |
161 HartmannOrlinMmc<GR, concepts::ReadMap<GR::Arc, float> > >(); |
162 |
162 |
163 // Howard |
163 // HowardMmc |
164 checkConcept< MmcClassConcept<GR, int>, |
164 checkConcept< MmcClassConcept<GR, int>, |
165 Howard<GR, concepts::ReadMap<GR::Arc, int> > >(); |
165 HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > >(); |
166 checkConcept< MmcClassConcept<GR, float>, |
166 checkConcept< MmcClassConcept<GR, float>, |
167 Howard<GR, concepts::ReadMap<GR::Arc, float> > >(); |
167 HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > >(); |
168 |
168 |
169 if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, int> >::LargeValue, |
169 check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, int> > |
170 long_int>::result == 0) check(false, "Wrong LargeValue type"); |
170 ::LargeCost, long_int>::result == 1), "Wrong LargeCost type"); |
171 if (IsSameType<Howard<GR, concepts::ReadMap<GR::Arc, float> >::LargeValue, |
171 check((IsSameType<HowardMmc<GR, concepts::ReadMap<GR::Arc, float> > |
172 double>::result == 0) check(false, "Wrong LargeValue type"); |
172 ::LargeCost, double>::result == 1), "Wrong LargeCost type"); |
173 } |
173 } |
174 |
174 |
175 // Run various tests |
175 // Run various tests |
176 { |
176 { |
177 typedef SmartDigraph GR; |
177 typedef SmartDigraph GR; |
192 arcMap("c3", c3). |
192 arcMap("c3", c3). |
193 arcMap("c4", c4). |
193 arcMap("c4", c4). |
194 run(); |
194 run(); |
195 |
195 |
196 // Karp |
196 // Karp |
197 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
197 checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
198 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
198 checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
199 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
199 checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
200 checkMmcAlg<Karp<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
200 checkMmcAlg<KarpMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
201 |
201 |
202 // HartmannOrlin |
202 // HartmannOrlin |
203 checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
203 checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
204 checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
204 checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
205 checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
205 checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
206 checkMmcAlg<HartmannOrlin<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
206 checkMmcAlg<HartmannOrlinMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
207 |
207 |
208 // Howard |
208 // Howard |
209 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
209 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l1, c1, 6, 3); |
210 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
210 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2, 5, 2); |
211 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
211 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1); |
212 checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
212 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1); |
213 } |
213 } |
214 |
214 |
215 return 0; |
215 return 0; |
216 } |
216 } |