Small changes in min. cost flow algorithms.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
19 #include <lemon/smart_graph.h>
20 #include <lemon/list_graph.h>
21 #include <lemon/graph_reader.h>
22 #include <lemon/graph_utils.h>
23 #include <lemon/error.h>
25 #include "test_tools.h"
28 using namespace lemon;
30 void graph_copy_test() {
34 SmartGraph::NodeMap<int> snm(source);
35 SmartGraph::EdgeMap<int> sem(source);
36 SmartGraph::Node sn = INVALID;
37 SmartGraph::Edge se = INVALID;
39 std::vector<SmartGraph::Node> snv;
40 for (int i = 0; i < nn; ++i) {
41 SmartGraph::Node node = source.addNode();
44 if (i == 0) sn = node;
47 for (int i = 0; i < nn; ++i) {
48 for (int j = 0; j < nn; ++j) {
49 SmartGraph::Edge edge = source.addEdge(snv[i], snv[j]);
50 sem[edge] = i + j * j;
51 if (i == 0 && j == 0) se = edge;
56 ListGraph::NodeMap<int> tnm(target);
57 ListGraph::EdgeMap<int> tem(target);
61 SmartGraph::NodeMap<ListGraph::Node> nr(source);
62 SmartGraph::EdgeMap<ListGraph::Edge> er(source);
64 ListGraph::NodeMap<SmartGraph::Node> ncr(target);
65 ListGraph::EdgeMap<SmartGraph::Edge> ecr(target);
67 GraphCopy<ListGraph, SmartGraph>(target, source).
68 nodeMap(tnm, snm).edgeMap(tem, sem).
69 nodeRef(nr).edgeRef(er).
70 nodeCrossRef(ncr).edgeCrossRef(ecr).
71 node(tn, sn).edge(te, se).run();
73 for (SmartGraph::NodeIt it(source); it != INVALID; ++it) {
74 check(ncr[nr[it]] == it, "Wrong copy.");
75 check(snm[it] == tnm[nr[it]], "Wrong copy.");
78 for (SmartGraph::EdgeIt it(source); it != INVALID; ++it) {
79 check(ecr[er[it]] == it, "Wrong copy.");
80 check(sem[it] == tem[er[it]], "Wrong copy.");
81 check(nr[source.source(it)] ==
82 target.source(er[it]), "Wrong copy.");
83 check(nr[source.target(it)] ==
84 target.target(er[it]), "Wrong copy.");
87 for (ListGraph::NodeIt it(target); it != INVALID; ++it) {
88 check(nr[ncr[it]] == it, "Wrong copy.");
91 for (ListGraph::EdgeIt it(target); it != INVALID; ++it) {
92 check(er[ecr[it]] == it, "Wrong copy.");
94 check(tn == nr[sn], "Wrong copy.");
95 check(te == er[se], "Wrong copy.");
98 void ugraph_copy_test() {
102 SmartUGraph::NodeMap<int> snm(source);
103 SmartUGraph::EdgeMap<int> sem(source);
104 SmartUGraph::UEdgeMap<int> suem(source);
105 SmartUGraph::Node sn = INVALID;
106 SmartUGraph::Edge se = INVALID;
107 SmartUGraph::UEdge sue = INVALID;
109 std::vector<SmartUGraph::Node> snv;
110 for (int i = 0; i < nn; ++i) {
111 SmartUGraph::Node node = source.addNode();
114 if (i == 0) sn = node;
117 for (int i = 0; i < nn; ++i) {
118 for (int j = 0; j < nn; ++j) {
119 SmartUGraph::UEdge edge = source.addEdge(snv[i], snv[j]);
120 suem[edge] = i * i + j * j;
121 sem[source.direct(edge, true)] = i + j * j;
122 sem[source.direct(edge, false)] = i * i + j;
123 if (i == 0 && j == 0) se = source.direct(edge, true);
124 if (i == 0 && j == 0) sue = edge;
129 ListUGraph::NodeMap<int> tnm(target);
130 ListUGraph::EdgeMap<int> tem(target);
131 ListUGraph::UEdgeMap<int> tuem(target);
134 ListUGraph::UEdge tue;
136 SmartUGraph::NodeMap<ListUGraph::Node> nr(source);
137 SmartUGraph::EdgeMap<ListUGraph::Edge> er(source);
138 SmartUGraph::UEdgeMap<ListUGraph::UEdge> uer(source);
140 ListUGraph::NodeMap<SmartUGraph::Node> ncr(target);
141 ListUGraph::EdgeMap<SmartUGraph::Edge> ecr(target);
142 ListUGraph::UEdgeMap<SmartUGraph::UEdge> uecr(target);
144 UGraphCopy<ListUGraph, SmartUGraph>(target, source).
145 nodeMap(tnm, snm).edgeMap(tem, sem).uEdgeMap(tuem, suem).
146 nodeRef(nr).edgeRef(er).uEdgeRef(uer).
147 nodeCrossRef(ncr).edgeCrossRef(ecr).uEdgeCrossRef(uecr).
148 node(tn, sn).edge(te, se).uEdge(tue, sue).run();
150 for (SmartUGraph::NodeIt it(source); it != INVALID; ++it) {
151 check(ncr[nr[it]] == it, "Wrong copy.");
152 check(snm[it] == tnm[nr[it]], "Wrong copy.");
155 for (SmartUGraph::EdgeIt it(source); it != INVALID; ++it) {
156 check(ecr[er[it]] == it, "Wrong copy.");
157 check(sem[it] == tem[er[it]], "Wrong copy.");
158 check(nr[source.source(it)] ==
159 target.source(er[it]), "Wrong copy.");
160 check(nr[source.target(it)] ==
161 target.target(er[it]), "Wrong copy.");
164 for (SmartUGraph::UEdgeIt it(source); it != INVALID; ++it) {
165 check(uecr[uer[it]] == it, "Wrong copy.");
166 check(suem[it] == tuem[uer[it]], "Wrong copy.");
167 check(nr[source.source(it)] == target.source(uer[it]) ||
168 nr[source.source(it)] == target.target(uer[it]),
170 check(nr[source.target(it)] == target.source(uer[it]) ||
171 nr[source.target(it)] == target.target(uer[it]),
173 check((source.source(it) != source.target(it)) ==
174 (target.source(uer[it]) != target.target(uer[it])),
178 for (ListUGraph::NodeIt it(target); it != INVALID; ++it) {
179 check(nr[ncr[it]] == it, "Wrong copy.");
182 for (ListUGraph::EdgeIt it(target); it != INVALID; ++it) {
183 check(er[ecr[it]] == it, "Wrong copy.");
185 for (ListUGraph::UEdgeIt it(target); it != INVALID; ++it) {
186 check(uer[uecr[it]] == it, "Wrong copy.");
188 check(tn == nr[sn], "Wrong copy.");
189 check(te == er[se], "Wrong copy.");
190 check(tue == uer[sue], "Wrong copy.");
193 void bpugraph_copy_test() {
196 SmartBpUGraph source;
197 SmartBpUGraph::ANodeMap<int> sanm(source);
198 SmartBpUGraph::BNodeMap<int> sbnm(source);
199 SmartBpUGraph::NodeMap<int> snm(source);
200 SmartBpUGraph::EdgeMap<int> sem(source);
201 SmartBpUGraph::UEdgeMap<int> suem(source);
202 SmartBpUGraph::Node sn = INVALID;
203 SmartBpUGraph::Edge se = INVALID;
204 SmartBpUGraph::UEdge sue = INVALID;
206 std::vector<SmartBpUGraph::Node> sanv;
207 for (int i = 0; i < nn; ++i) {
208 SmartBpUGraph::Node node = source.addANode();
209 sanv.push_back(node);
211 snm[node] = i * i + i;
212 if (i == 0) sn = node;
215 std::vector<SmartBpUGraph::Node> sbnv;
216 for (int i = 0; i < nn; ++i) {
217 SmartBpUGraph::Node node = source.addBNode();
218 sbnv.push_back(node);
219 sbnm[node] = i * i - i;
220 snm[node] = i * i + i + 1;
223 for (int i = 0; i < nn; ++i) {
224 for (int j = 0; j < nn; ++j) {
225 SmartBpUGraph::UEdge edge = source.addEdge(sanv[i], sbnv[j]);
226 suem[edge] = i * i + j * j;
227 sem[source.direct(edge, true)] = i + j * j;
228 sem[source.direct(edge, false)] = i * i + j;
229 if (i == 0 && j == 0) se = source.direct(edge, true);
230 if (i == 0 && j == 0) sue = edge;
235 ListBpUGraph::ANodeMap<int> tanm(target);
236 ListBpUGraph::BNodeMap<int> tbnm(target);
237 ListBpUGraph::NodeMap<int> tnm(target);
238 ListBpUGraph::EdgeMap<int> tem(target);
239 ListBpUGraph::UEdgeMap<int> tuem(target);
240 ListBpUGraph::Node tn;
241 ListBpUGraph::Edge te;
242 ListBpUGraph::UEdge tue;
244 SmartBpUGraph::ANodeMap<ListBpUGraph::Node> anr(source);
245 SmartBpUGraph::BNodeMap<ListBpUGraph::Node> bnr(source);
246 SmartBpUGraph::NodeMap<ListBpUGraph::Node> nr(source);
247 SmartBpUGraph::EdgeMap<ListBpUGraph::Edge> er(source);
248 SmartBpUGraph::UEdgeMap<ListBpUGraph::UEdge> uer(source);
250 ListBpUGraph::ANodeMap<SmartBpUGraph::Node> ancr(target);
251 ListBpUGraph::BNodeMap<SmartBpUGraph::Node> bncr(target);
252 ListBpUGraph::NodeMap<SmartBpUGraph::Node> ncr(target);
253 ListBpUGraph::EdgeMap<SmartBpUGraph::Edge> ecr(target);
254 ListBpUGraph::UEdgeMap<SmartBpUGraph::UEdge> uecr(target);
256 BpUGraphCopy<ListBpUGraph, SmartBpUGraph>(target, source).
257 aNodeMap(tanm, sanm).bNodeMap(tbnm, sbnm).nodeMap(tnm, snm).
258 edgeMap(tem, sem).uEdgeMap(tuem, suem).
259 aNodeRef(anr).bNodeRef(bnr).nodeRef(nr).edgeRef(er).uEdgeRef(uer).
260 aNodeCrossRef(ancr).bNodeCrossRef(bncr).nodeCrossRef(ncr).
261 edgeCrossRef(ecr).uEdgeCrossRef(uecr).
262 node(tn, sn).edge(te, se).uEdge(tue, sue).run();
264 for (SmartBpUGraph::ANodeIt it(source); it != INVALID; ++it) {
265 check(nr[it] == anr[it], "Wrong copy.");
266 check(ancr[anr[it]] == it, "Wrong copy.");
267 check(sanm[it] == tanm[anr[it]], "Wrong copy.");
270 for (SmartBpUGraph::BNodeIt it(source); it != INVALID; ++it) {
271 check(nr[it] == bnr[it], "Wrong copy.");
272 check(bncr[bnr[it]] == it, "Wrong copy.");
273 check(sbnm[it] == tbnm[bnr[it]], "Wrong copy.");
276 for (SmartBpUGraph::NodeIt it(source); it != INVALID; ++it) {
277 check(ncr[nr[it]] == it, "Wrong copy.");
278 check(snm[it] == tnm[nr[it]], "Wrong copy.");
281 for (SmartBpUGraph::EdgeIt it(source); it != INVALID; ++it) {
282 check(ecr[er[it]] == it, "Wrong copy.");
283 check(sem[it] == tem[er[it]], "Wrong copy.");
284 check(nr[source.source(it)] ==
285 target.source(er[it]), "Wrong copy.");
286 check(nr[source.target(it)] ==
287 target.target(er[it]), "Wrong copy.");
290 for (SmartBpUGraph::UEdgeIt it(source); it != INVALID; ++it) {
291 check(uecr[uer[it]] == it, "Wrong copy.");
292 check(suem[it] == tuem[uer[it]], "Wrong copy.");
293 check(nr[source.aNode(it)] ==
294 target.aNode(uer[it]), "Wrong copy.");
295 check(nr[source.bNode(it)] ==
296 target.bNode(uer[it]), "Wrong copy.");
299 for (ListBpUGraph::ANodeIt it(target); it != INVALID; ++it) {
300 check(ancr[it] == ncr[it], "Wrong copy.");
301 check(anr[ancr[it]] == it, "Wrong copy.");
304 for (ListBpUGraph::BNodeIt it(target); it != INVALID; ++it) {
305 check(bncr[it] == ncr[it], "Wrong copy.");
306 check(bnr[bncr[it]] == it, "Wrong copy.");
309 for (ListBpUGraph::NodeIt it(target); it != INVALID; ++it) {
310 check(nr[ncr[it]] == it, "Wrong copy.");
313 for (ListBpUGraph::EdgeIt it(target); it != INVALID; ++it) {
314 check(er[ecr[it]] == it, "Wrong copy.");
316 for (ListBpUGraph::UEdgeIt it(target); it != INVALID; ++it) {
317 check(uer[uecr[it]] == it, "Wrong copy.");
319 check(tn == nr[sn], "Wrong copy.");
320 check(te == er[se], "Wrong copy.");
321 check(tue == uer[sue], "Wrong copy.");
327 bpugraph_copy_test();