alpar@209
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@200
|
2 |
*
|
alpar@209
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@200
|
4 |
*
|
deba@200
|
5 |
* Copyright (C) 2003-2008
|
deba@200
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@200
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@200
|
8 |
*
|
deba@200
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@200
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@200
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@200
|
12 |
*
|
deba@200
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@200
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@200
|
15 |
* purpose.
|
deba@200
|
16 |
*
|
deba@200
|
17 |
*/
|
deba@200
|
18 |
|
deba@200
|
19 |
#include <lemon/smart_graph.h>
|
deba@200
|
20 |
#include <lemon/list_graph.h>
|
deba@200
|
21 |
#include <lemon/lgf_reader.h>
|
deba@200
|
22 |
#include <lemon/error.h>
|
deba@200
|
23 |
|
deba@200
|
24 |
#include "test_tools.h"
|
deba@200
|
25 |
|
deba@200
|
26 |
using namespace std;
|
deba@200
|
27 |
using namespace lemon;
|
deba@200
|
28 |
|
deba@200
|
29 |
void digraph_copy_test() {
|
deba@200
|
30 |
const int nn = 10;
|
deba@200
|
31 |
|
kpeter@416
|
32 |
// Build a digraph
|
deba@200
|
33 |
SmartDigraph from;
|
deba@200
|
34 |
SmartDigraph::NodeMap<int> fnm(from);
|
deba@200
|
35 |
SmartDigraph::ArcMap<int> fam(from);
|
deba@200
|
36 |
SmartDigraph::Node fn = INVALID;
|
deba@200
|
37 |
SmartDigraph::Arc fa = INVALID;
|
deba@200
|
38 |
|
deba@200
|
39 |
std::vector<SmartDigraph::Node> fnv;
|
deba@200
|
40 |
for (int i = 0; i < nn; ++i) {
|
deba@200
|
41 |
SmartDigraph::Node node = from.addNode();
|
deba@200
|
42 |
fnv.push_back(node);
|
deba@200
|
43 |
fnm[node] = i * i;
|
deba@200
|
44 |
if (i == 0) fn = node;
|
deba@200
|
45 |
}
|
deba@200
|
46 |
|
deba@200
|
47 |
for (int i = 0; i < nn; ++i) {
|
deba@200
|
48 |
for (int j = 0; j < nn; ++j) {
|
deba@200
|
49 |
SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
|
deba@200
|
50 |
fam[arc] = i + j * j;
|
deba@200
|
51 |
if (i == 0 && j == 0) fa = arc;
|
deba@200
|
52 |
}
|
deba@200
|
53 |
}
|
deba@200
|
54 |
|
kpeter@416
|
55 |
// Test digraph copy
|
deba@200
|
56 |
ListDigraph to;
|
deba@200
|
57 |
ListDigraph::NodeMap<int> tnm(to);
|
deba@200
|
58 |
ListDigraph::ArcMap<int> tam(to);
|
deba@200
|
59 |
ListDigraph::Node tn;
|
deba@200
|
60 |
ListDigraph::Arc ta;
|
deba@200
|
61 |
|
deba@200
|
62 |
SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
|
deba@200
|
63 |
SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
|
deba@200
|
64 |
|
deba@200
|
65 |
ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
|
deba@200
|
66 |
ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
|
deba@200
|
67 |
|
kpeter@282
|
68 |
digraphCopy(from, to).
|
kpeter@282
|
69 |
nodeMap(fnm, tnm).arcMap(fam, tam).
|
deba@200
|
70 |
nodeRef(nr).arcRef(er).
|
deba@200
|
71 |
nodeCrossRef(ncr).arcCrossRef(ecr).
|
kpeter@282
|
72 |
node(fn, tn).arc(fa, ta).run();
|
kpeter@416
|
73 |
|
kpeter@416
|
74 |
check(countNodes(from) == countNodes(to), "Wrong copy.");
|
kpeter@416
|
75 |
check(countArcs(from) == countArcs(to), "Wrong copy.");
|
deba@200
|
76 |
|
deba@200
|
77 |
for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
|
deba@200
|
78 |
check(ncr[nr[it]] == it, "Wrong copy.");
|
deba@200
|
79 |
check(fnm[it] == tnm[nr[it]], "Wrong copy.");
|
deba@200
|
80 |
}
|
deba@200
|
81 |
|
deba@200
|
82 |
for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
|
deba@200
|
83 |
check(ecr[er[it]] == it, "Wrong copy.");
|
deba@200
|
84 |
check(fam[it] == tam[er[it]], "Wrong copy.");
|
deba@200
|
85 |
check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
|
deba@200
|
86 |
check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
|
deba@200
|
87 |
}
|
deba@200
|
88 |
|
deba@200
|
89 |
for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
|
deba@200
|
90 |
check(nr[ncr[it]] == it, "Wrong copy.");
|
deba@200
|
91 |
}
|
deba@200
|
92 |
|
deba@200
|
93 |
for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
|
deba@200
|
94 |
check(er[ecr[it]] == it, "Wrong copy.");
|
deba@200
|
95 |
}
|
deba@200
|
96 |
check(tn == nr[fn], "Wrong copy.");
|
deba@200
|
97 |
check(ta == er[fa], "Wrong copy.");
|
kpeter@416
|
98 |
|
kpeter@416
|
99 |
// Test repeated copy
|
kpeter@416
|
100 |
digraphCopy(from, to).run();
|
kpeter@416
|
101 |
|
kpeter@416
|
102 |
check(countNodes(from) == countNodes(to), "Wrong copy.");
|
kpeter@416
|
103 |
check(countArcs(from) == countArcs(to), "Wrong copy.");
|
deba@200
|
104 |
}
|
deba@200
|
105 |
|
deba@200
|
106 |
void graph_copy_test() {
|
deba@200
|
107 |
const int nn = 10;
|
deba@200
|
108 |
|
kpeter@416
|
109 |
// Build a graph
|
deba@200
|
110 |
SmartGraph from;
|
deba@200
|
111 |
SmartGraph::NodeMap<int> fnm(from);
|
deba@200
|
112 |
SmartGraph::ArcMap<int> fam(from);
|
deba@200
|
113 |
SmartGraph::EdgeMap<int> fem(from);
|
deba@200
|
114 |
SmartGraph::Node fn = INVALID;
|
deba@200
|
115 |
SmartGraph::Arc fa = INVALID;
|
deba@200
|
116 |
SmartGraph::Edge fe = INVALID;
|
deba@200
|
117 |
|
deba@200
|
118 |
std::vector<SmartGraph::Node> fnv;
|
deba@200
|
119 |
for (int i = 0; i < nn; ++i) {
|
deba@200
|
120 |
SmartGraph::Node node = from.addNode();
|
deba@200
|
121 |
fnv.push_back(node);
|
deba@200
|
122 |
fnm[node] = i * i;
|
deba@200
|
123 |
if (i == 0) fn = node;
|
deba@200
|
124 |
}
|
deba@200
|
125 |
|
deba@200
|
126 |
for (int i = 0; i < nn; ++i) {
|
deba@200
|
127 |
for (int j = 0; j < nn; ++j) {
|
deba@200
|
128 |
SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
|
deba@200
|
129 |
fem[edge] = i * i + j * j;
|
deba@200
|
130 |
fam[from.direct(edge, true)] = i + j * j;
|
deba@200
|
131 |
fam[from.direct(edge, false)] = i * i + j;
|
deba@200
|
132 |
if (i == 0 && j == 0) fa = from.direct(edge, true);
|
deba@200
|
133 |
if (i == 0 && j == 0) fe = edge;
|
deba@200
|
134 |
}
|
deba@200
|
135 |
}
|
alpar@209
|
136 |
|
kpeter@416
|
137 |
// Test graph copy
|
deba@200
|
138 |
ListGraph to;
|
deba@200
|
139 |
ListGraph::NodeMap<int> tnm(to);
|
deba@200
|
140 |
ListGraph::ArcMap<int> tam(to);
|
deba@200
|
141 |
ListGraph::EdgeMap<int> tem(to);
|
deba@200
|
142 |
ListGraph::Node tn;
|
deba@200
|
143 |
ListGraph::Arc ta;
|
deba@200
|
144 |
ListGraph::Edge te;
|
deba@200
|
145 |
|
deba@200
|
146 |
SmartGraph::NodeMap<ListGraph::Node> nr(from);
|
deba@200
|
147 |
SmartGraph::ArcMap<ListGraph::Arc> ar(from);
|
deba@200
|
148 |
SmartGraph::EdgeMap<ListGraph::Edge> er(from);
|
deba@200
|
149 |
|
deba@200
|
150 |
ListGraph::NodeMap<SmartGraph::Node> ncr(to);
|
deba@200
|
151 |
ListGraph::ArcMap<SmartGraph::Arc> acr(to);
|
deba@200
|
152 |
ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
|
deba@200
|
153 |
|
kpeter@282
|
154 |
graphCopy(from, to).
|
kpeter@282
|
155 |
nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
|
deba@200
|
156 |
nodeRef(nr).arcRef(ar).edgeRef(er).
|
deba@200
|
157 |
nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
|
kpeter@282
|
158 |
node(fn, tn).arc(fa, ta).edge(fe, te).run();
|
deba@200
|
159 |
|
kpeter@416
|
160 |
check(countNodes(from) == countNodes(to), "Wrong copy.");
|
kpeter@416
|
161 |
check(countEdges(from) == countEdges(to), "Wrong copy.");
|
kpeter@416
|
162 |
check(countArcs(from) == countArcs(to), "Wrong copy.");
|
kpeter@416
|
163 |
|
deba@200
|
164 |
for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
|
deba@200
|
165 |
check(ncr[nr[it]] == it, "Wrong copy.");
|
deba@200
|
166 |
check(fnm[it] == tnm[nr[it]], "Wrong copy.");
|
deba@200
|
167 |
}
|
deba@200
|
168 |
|
deba@200
|
169 |
for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
|
deba@200
|
170 |
check(acr[ar[it]] == it, "Wrong copy.");
|
deba@200
|
171 |
check(fam[it] == tam[ar[it]], "Wrong copy.");
|
deba@200
|
172 |
check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
|
deba@200
|
173 |
check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
|
deba@200
|
174 |
}
|
deba@200
|
175 |
|
deba@200
|
176 |
for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
|
deba@200
|
177 |
check(ecr[er[it]] == it, "Wrong copy.");
|
deba@200
|
178 |
check(fem[it] == tem[er[it]], "Wrong copy.");
|
alpar@209
|
179 |
check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
|
alpar@209
|
180 |
"Wrong copy.");
|
alpar@209
|
181 |
check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
|
alpar@209
|
182 |
"Wrong copy.");
|
alpar@209
|
183 |
check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
|
alpar@209
|
184 |
"Wrong copy.");
|
deba@200
|
185 |
}
|
deba@200
|
186 |
|
deba@200
|
187 |
for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
|
deba@200
|
188 |
check(nr[ncr[it]] == it, "Wrong copy.");
|
deba@200
|
189 |
}
|
deba@200
|
190 |
|
deba@200
|
191 |
for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
|
deba@200
|
192 |
check(ar[acr[it]] == it, "Wrong copy.");
|
deba@200
|
193 |
}
|
deba@200
|
194 |
for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
|
deba@200
|
195 |
check(er[ecr[it]] == it, "Wrong copy.");
|
deba@200
|
196 |
}
|
deba@200
|
197 |
check(tn == nr[fn], "Wrong copy.");
|
deba@200
|
198 |
check(ta == ar[fa], "Wrong copy.");
|
deba@200
|
199 |
check(te == er[fe], "Wrong copy.");
|
kpeter@416
|
200 |
|
kpeter@416
|
201 |
// Test repeated copy
|
kpeter@416
|
202 |
graphCopy(from, to).run();
|
kpeter@416
|
203 |
|
kpeter@416
|
204 |
check(countNodes(from) == countNodes(to), "Wrong copy.");
|
kpeter@416
|
205 |
check(countEdges(from) == countEdges(to), "Wrong copy.");
|
kpeter@416
|
206 |
check(countArcs(from) == countArcs(to), "Wrong copy.");
|
deba@200
|
207 |
}
|
deba@200
|
208 |
|
deba@200
|
209 |
|
deba@200
|
210 |
int main() {
|
deba@200
|
211 |
digraph_copy_test();
|
deba@200
|
212 |
graph_copy_test();
|
deba@200
|
213 |
|
alpar@209
|
214 |
return 0;
|
deba@200
|
215 |
}
|