|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
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 <lemon/smart_graph.h> |
|
20 #include <lemon/list_graph.h> |
|
21 #include <lemon/lgf_reader.h> |
|
22 #include <lemon/graph_utils.h> |
|
23 #include <lemon/error.h> |
|
24 |
|
25 #include "test_tools.h" |
|
26 |
|
27 using namespace std; |
|
28 using namespace lemon; |
|
29 |
|
30 void digraph_copy_test() { |
|
31 const int nn = 10; |
|
32 |
|
33 SmartDigraph from; |
|
34 SmartDigraph::NodeMap<int> fnm(from); |
|
35 SmartDigraph::ArcMap<int> fam(from); |
|
36 SmartDigraph::Node fn = INVALID; |
|
37 SmartDigraph::Arc fa = INVALID; |
|
38 |
|
39 std::vector<SmartDigraph::Node> fnv; |
|
40 for (int i = 0; i < nn; ++i) { |
|
41 SmartDigraph::Node node = from.addNode(); |
|
42 fnv.push_back(node); |
|
43 fnm[node] = i * i; |
|
44 if (i == 0) fn = node; |
|
45 } |
|
46 |
|
47 for (int i = 0; i < nn; ++i) { |
|
48 for (int j = 0; j < nn; ++j) { |
|
49 SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]); |
|
50 fam[arc] = i + j * j; |
|
51 if (i == 0 && j == 0) fa = arc; |
|
52 } |
|
53 } |
|
54 |
|
55 ListDigraph to; |
|
56 ListDigraph::NodeMap<int> tnm(to); |
|
57 ListDigraph::ArcMap<int> tam(to); |
|
58 ListDigraph::Node tn; |
|
59 ListDigraph::Arc ta; |
|
60 |
|
61 SmartDigraph::NodeMap<ListDigraph::Node> nr(from); |
|
62 SmartDigraph::ArcMap<ListDigraph::Arc> er(from); |
|
63 |
|
64 ListDigraph::NodeMap<SmartDigraph::Node> ncr(to); |
|
65 ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to); |
|
66 |
|
67 DigraphCopy<ListDigraph, SmartDigraph>(to, from). |
|
68 nodeMap(tnm, fnm).arcMap(tam, fam). |
|
69 nodeRef(nr).arcRef(er). |
|
70 nodeCrossRef(ncr).arcCrossRef(ecr). |
|
71 node(tn, fn).arc(ta, fa).run(); |
|
72 |
|
73 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { |
|
74 check(ncr[nr[it]] == it, "Wrong copy."); |
|
75 check(fnm[it] == tnm[nr[it]], "Wrong copy."); |
|
76 } |
|
77 |
|
78 for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) { |
|
79 check(ecr[er[it]] == it, "Wrong copy."); |
|
80 check(fam[it] == tam[er[it]], "Wrong copy."); |
|
81 check(nr[from.source(it)] == to.source(er[it]), "Wrong copy."); |
|
82 check(nr[from.target(it)] == to.target(er[it]), "Wrong copy."); |
|
83 } |
|
84 |
|
85 for (ListDigraph::NodeIt it(to); it != INVALID; ++it) { |
|
86 check(nr[ncr[it]] == it, "Wrong copy."); |
|
87 } |
|
88 |
|
89 for (ListDigraph::ArcIt it(to); it != INVALID; ++it) { |
|
90 check(er[ecr[it]] == it, "Wrong copy."); |
|
91 } |
|
92 check(tn == nr[fn], "Wrong copy."); |
|
93 check(ta == er[fa], "Wrong copy."); |
|
94 } |
|
95 |
|
96 void graph_copy_test() { |
|
97 const int nn = 10; |
|
98 |
|
99 SmartGraph from; |
|
100 SmartGraph::NodeMap<int> fnm(from); |
|
101 SmartGraph::ArcMap<int> fam(from); |
|
102 SmartGraph::EdgeMap<int> fem(from); |
|
103 SmartGraph::Node fn = INVALID; |
|
104 SmartGraph::Arc fa = INVALID; |
|
105 SmartGraph::Edge fe = INVALID; |
|
106 |
|
107 std::vector<SmartGraph::Node> fnv; |
|
108 for (int i = 0; i < nn; ++i) { |
|
109 SmartGraph::Node node = from.addNode(); |
|
110 fnv.push_back(node); |
|
111 fnm[node] = i * i; |
|
112 if (i == 0) fn = node; |
|
113 } |
|
114 |
|
115 for (int i = 0; i < nn; ++i) { |
|
116 for (int j = 0; j < nn; ++j) { |
|
117 SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]); |
|
118 fem[edge] = i * i + j * j; |
|
119 fam[from.direct(edge, true)] = i + j * j; |
|
120 fam[from.direct(edge, false)] = i * i + j; |
|
121 if (i == 0 && j == 0) fa = from.direct(edge, true); |
|
122 if (i == 0 && j == 0) fe = edge; |
|
123 } |
|
124 } |
|
125 |
|
126 ListGraph to; |
|
127 ListGraph::NodeMap<int> tnm(to); |
|
128 ListGraph::ArcMap<int> tam(to); |
|
129 ListGraph::EdgeMap<int> tem(to); |
|
130 ListGraph::Node tn; |
|
131 ListGraph::Arc ta; |
|
132 ListGraph::Edge te; |
|
133 |
|
134 SmartGraph::NodeMap<ListGraph::Node> nr(from); |
|
135 SmartGraph::ArcMap<ListGraph::Arc> ar(from); |
|
136 SmartGraph::EdgeMap<ListGraph::Edge> er(from); |
|
137 |
|
138 ListGraph::NodeMap<SmartGraph::Node> ncr(to); |
|
139 ListGraph::ArcMap<SmartGraph::Arc> acr(to); |
|
140 ListGraph::EdgeMap<SmartGraph::Edge> ecr(to); |
|
141 |
|
142 GraphCopy<ListGraph, SmartGraph>(to, from). |
|
143 nodeMap(tnm, fnm).arcMap(tam, fam).edgeMap(tem, fem). |
|
144 nodeRef(nr).arcRef(ar).edgeRef(er). |
|
145 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). |
|
146 node(tn, fn).arc(ta, fa).edge(te, fe).run(); |
|
147 |
|
148 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { |
|
149 check(ncr[nr[it]] == it, "Wrong copy."); |
|
150 check(fnm[it] == tnm[nr[it]], "Wrong copy."); |
|
151 } |
|
152 |
|
153 for (SmartGraph::ArcIt it(from); it != INVALID; ++it) { |
|
154 check(acr[ar[it]] == it, "Wrong copy."); |
|
155 check(fam[it] == tam[ar[it]], "Wrong copy."); |
|
156 check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy."); |
|
157 check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy."); |
|
158 } |
|
159 |
|
160 for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) { |
|
161 check(ecr[er[it]] == it, "Wrong copy."); |
|
162 check(fem[it] == tem[er[it]], "Wrong copy."); |
|
163 check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]), |
|
164 "Wrong copy."); |
|
165 check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]), |
|
166 "Wrong copy."); |
|
167 check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])), |
|
168 "Wrong copy."); |
|
169 } |
|
170 |
|
171 for (ListGraph::NodeIt it(to); it != INVALID; ++it) { |
|
172 check(nr[ncr[it]] == it, "Wrong copy."); |
|
173 } |
|
174 |
|
175 for (ListGraph::ArcIt it(to); it != INVALID; ++it) { |
|
176 check(ar[acr[it]] == it, "Wrong copy."); |
|
177 } |
|
178 for (ListGraph::EdgeIt it(to); it != INVALID; ++it) { |
|
179 check(er[ecr[it]] == it, "Wrong copy."); |
|
180 } |
|
181 check(tn == nr[fn], "Wrong copy."); |
|
182 check(ta == ar[fa], "Wrong copy."); |
|
183 check(te == er[fe], "Wrong copy."); |
|
184 } |
|
185 |
|
186 |
|
187 int main() { |
|
188 digraph_copy_test(); |
|
189 graph_copy_test(); |
|
190 |
|
191 return 0; |
|
192 } |