22 #include <iterator> |
22 #include <iterator> |
23 |
23 |
24 #include <lemon/smart_graph.h> |
24 #include <lemon/smart_graph.h> |
25 #include <lemon/min_cost_arborescence.h> |
25 #include <lemon/min_cost_arborescence.h> |
26 #include <lemon/lgf_reader.h> |
26 #include <lemon/lgf_reader.h> |
|
27 #include <lemon/concepts/digraph.h> |
27 |
28 |
28 #include "test_tools.h" |
29 #include "test_tools.h" |
29 |
30 |
30 using namespace lemon; |
31 using namespace lemon; |
31 using namespace std; |
32 using namespace std; |
68 "1 1 20 60\n" |
69 "1 1 20 60\n" |
69 "0 3 21 40\n" |
70 "0 3 21 40\n" |
70 "@attributes\n" |
71 "@attributes\n" |
71 "source 0\n"; |
72 "source 0\n"; |
72 |
73 |
|
74 |
|
75 void checkMinCostArborescenceCompile() |
|
76 { |
|
77 typedef double VType; |
|
78 typedef concepts::Digraph Digraph; |
|
79 typedef concepts::ReadMap<Digraph::Arc, VType> CostMap; |
|
80 typedef Digraph::Node Node; |
|
81 typedef Digraph::Arc Arc; |
|
82 typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap; |
|
83 typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap; |
|
84 |
|
85 typedef MinCostArborescence<Digraph, CostMap>:: |
|
86 SetArborescenceMap<ArbMap>:: |
|
87 SetPredMap<PredMap>::Create MinCostArbType; |
|
88 |
|
89 Digraph g; |
|
90 Node s, n; |
|
91 Arc e; |
|
92 VType c; |
|
93 bool b; |
|
94 int i; |
|
95 CostMap cost; |
|
96 ArbMap arb; |
|
97 PredMap pred; |
|
98 |
|
99 MinCostArbType mcarb_test(g, cost); |
|
100 const MinCostArbType& const_mcarb_test = mcarb_test; |
|
101 |
|
102 mcarb_test |
|
103 .arborescenceMap(arb) |
|
104 .predMap(pred) |
|
105 .run(s); |
|
106 |
|
107 mcarb_test.init(); |
|
108 mcarb_test.addSource(s); |
|
109 mcarb_test.start(); |
|
110 n = mcarb_test.processNextNode(); |
|
111 b = const_mcarb_test.emptyQueue(); |
|
112 i = const_mcarb_test.queueSize(); |
|
113 |
|
114 c = const_mcarb_test.arborescenceCost(); |
|
115 b = const_mcarb_test.arborescence(e); |
|
116 e = const_mcarb_test.pred(n); |
|
117 const MinCostArbType::ArborescenceMap &am = |
|
118 const_mcarb_test.arborescenceMap(); |
|
119 const MinCostArbType::PredMap &pm = |
|
120 const_mcarb_test.predMap(); |
|
121 b = const_mcarb_test.reached(n); |
|
122 b = const_mcarb_test.processed(n); |
|
123 |
|
124 i = const_mcarb_test.dualNum(); |
|
125 c = const_mcarb_test.dualValue(); |
|
126 i = const_mcarb_test.dualSize(i); |
|
127 c = const_mcarb_test.dualValue(i); |
|
128 |
|
129 ignore_unused_variable_warning(am); |
|
130 ignore_unused_variable_warning(pm); |
|
131 } |
|
132 |
73 int main() { |
133 int main() { |
74 typedef SmartDigraph Digraph; |
134 typedef SmartDigraph Digraph; |
75 DIGRAPH_TYPEDEFS(Digraph); |
135 DIGRAPH_TYPEDEFS(Digraph); |
76 |
136 |
77 typedef Digraph::ArcMap<double> CostMap; |
137 typedef Digraph::ArcMap<double> CostMap; |
108 == dualSolution[i].second.end()) { |
168 == dualSolution[i].second.end()) { |
109 sum += dualSolution[i].first; |
169 sum += dualSolution[i].first; |
110 } |
170 } |
111 } |
171 } |
112 if (mca.arborescence(it)) { |
172 if (mca.arborescence(it)) { |
113 check(sum == cost[it], "INVALID DUAL"); |
173 check(sum == cost[it], "Invalid dual solution"); |
114 } |
174 } |
115 check(sum <= cost[it], "INVALID DUAL"); |
175 check(sum <= cost[it], "Invalid dual solution"); |
116 } |
176 } |
117 } |
177 } |
118 |
178 |
119 |
179 |
120 check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL"); |
180 check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution"); |
121 |
181 |
122 check(mca.reached(source), "INVALID ARBORESCENCE"); |
182 check(mca.reached(source), "Invalid arborescence"); |
123 for (ArcIt a(digraph); a != INVALID; ++a) { |
183 for (ArcIt a(digraph); a != INVALID; ++a) { |
124 check(!mca.reached(digraph.source(a)) || |
184 check(!mca.reached(digraph.source(a)) || |
125 mca.reached(digraph.target(a)), "INVALID ARBORESCENCE"); |
185 mca.reached(digraph.target(a)), "Invalid arborescence"); |
126 } |
186 } |
127 |
187 |
128 for (NodeIt n(digraph); n != INVALID; ++n) { |
188 for (NodeIt n(digraph); n != INVALID; ++n) { |
129 if (!mca.reached(n)) continue; |
189 if (!mca.reached(n)) continue; |
130 int cnt = 0; |
190 int cnt = 0; |
131 for (InArcIt a(digraph, n); a != INVALID; ++a) { |
191 for (InArcIt a(digraph, n); a != INVALID; ++a) { |
132 if (mca.arborescence(a)) { |
192 if (mca.arborescence(a)) { |
133 check(mca.pred(n) == a, "INVALID ARBORESCENCE"); |
193 check(mca.pred(n) == a, "Invalid arborescence"); |
134 ++cnt; |
194 ++cnt; |
135 } |
195 } |
136 } |
196 } |
137 check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE"); |
197 check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence"); |
138 } |
198 } |
139 |
199 |
140 Digraph::ArcMap<bool> arborescence(digraph); |
200 Digraph::ArcMap<bool> arborescence(digraph); |
141 check(mca.arborescenceValue() == |
201 check(mca.arborescenceCost() == |
142 minCostArborescence(digraph, cost, source, arborescence), |
202 minCostArborescence(digraph, cost, source, arborescence), |
143 "WRONG FUNCTION"); |
203 "Wrong result of the function interface"); |
144 |
204 |
145 return 0; |
205 return 0; |
146 } |
206 } |