1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2009 |
---|
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 <iostream> |
---|
20 | |
---|
21 | #include <lemon/planarity.h> |
---|
22 | |
---|
23 | #include <lemon/smart_graph.h> |
---|
24 | #include <lemon/lgf_reader.h> |
---|
25 | #include <lemon/connectivity.h> |
---|
26 | #include <lemon/dim2.h> |
---|
27 | |
---|
28 | #include "test_tools.h" |
---|
29 | |
---|
30 | using namespace lemon; |
---|
31 | using namespace lemon::dim2; |
---|
32 | |
---|
33 | const int lgfn = 4; |
---|
34 | const std::string lgf[lgfn] = { |
---|
35 | "@nodes\n" |
---|
36 | "label\n" |
---|
37 | "0\n" |
---|
38 | "1\n" |
---|
39 | "2\n" |
---|
40 | "3\n" |
---|
41 | "4\n" |
---|
42 | "@edges\n" |
---|
43 | " label\n" |
---|
44 | "0 1 0\n" |
---|
45 | "0 2 0\n" |
---|
46 | "0 3 0\n" |
---|
47 | "0 4 0\n" |
---|
48 | "1 2 0\n" |
---|
49 | "1 3 0\n" |
---|
50 | "1 4 0\n" |
---|
51 | "2 3 0\n" |
---|
52 | "2 4 0\n" |
---|
53 | "3 4 0\n", |
---|
54 | |
---|
55 | "@nodes\n" |
---|
56 | "label\n" |
---|
57 | "0\n" |
---|
58 | "1\n" |
---|
59 | "2\n" |
---|
60 | "3\n" |
---|
61 | "4\n" |
---|
62 | "@edges\n" |
---|
63 | " label\n" |
---|
64 | "0 1 0\n" |
---|
65 | "0 2 0\n" |
---|
66 | "0 3 0\n" |
---|
67 | "0 4 0\n" |
---|
68 | "1 2 0\n" |
---|
69 | "1 3 0\n" |
---|
70 | "2 3 0\n" |
---|
71 | "2 4 0\n" |
---|
72 | "3 4 0\n", |
---|
73 | |
---|
74 | "@nodes\n" |
---|
75 | "label\n" |
---|
76 | "0\n" |
---|
77 | "1\n" |
---|
78 | "2\n" |
---|
79 | "3\n" |
---|
80 | "4\n" |
---|
81 | "5\n" |
---|
82 | "@edges\n" |
---|
83 | " label\n" |
---|
84 | "0 3 0\n" |
---|
85 | "0 4 0\n" |
---|
86 | "0 5 0\n" |
---|
87 | "1 3 0\n" |
---|
88 | "1 4 0\n" |
---|
89 | "1 5 0\n" |
---|
90 | "2 3 0\n" |
---|
91 | "2 4 0\n" |
---|
92 | "2 5 0\n", |
---|
93 | |
---|
94 | "@nodes\n" |
---|
95 | "label\n" |
---|
96 | "0\n" |
---|
97 | "1\n" |
---|
98 | "2\n" |
---|
99 | "3\n" |
---|
100 | "4\n" |
---|
101 | "5\n" |
---|
102 | "@edges\n" |
---|
103 | " label\n" |
---|
104 | "0 3 0\n" |
---|
105 | "0 4 0\n" |
---|
106 | "0 5 0\n" |
---|
107 | "1 3 0\n" |
---|
108 | "1 4 0\n" |
---|
109 | "1 5 0\n" |
---|
110 | "2 3 0\n" |
---|
111 | "2 5 0\n" |
---|
112 | }; |
---|
113 | |
---|
114 | |
---|
115 | |
---|
116 | typedef SmartGraph Graph; |
---|
117 | GRAPH_TYPEDEFS(Graph); |
---|
118 | |
---|
119 | typedef PlanarEmbedding<SmartGraph> PE; |
---|
120 | typedef PlanarDrawing<SmartGraph> PD; |
---|
121 | typedef PlanarColoring<SmartGraph> PC; |
---|
122 | |
---|
123 | void checkEmbedding(const Graph& graph, PE& pe) { |
---|
124 | int face_num = 0; |
---|
125 | |
---|
126 | Graph::ArcMap<int> face(graph, -1); |
---|
127 | |
---|
128 | for (ArcIt a(graph); a != INVALID; ++a) { |
---|
129 | if (face[a] == -1) { |
---|
130 | Arc b = a; |
---|
131 | while (face[b] == -1) { |
---|
132 | face[b] = face_num; |
---|
133 | b = pe.next(graph.oppositeArc(b)); |
---|
134 | } |
---|
135 | check(face[b] == face_num, "Wrong face"); |
---|
136 | ++face_num; |
---|
137 | } |
---|
138 | } |
---|
139 | check(face_num + countNodes(graph) - countConnectedComponents(graph) == |
---|
140 | countEdges(graph) + 1, "Euler test does not passed"); |
---|
141 | } |
---|
142 | |
---|
143 | void checkKuratowski(const Graph& graph, PE& pe) { |
---|
144 | std::map<int, int> degs; |
---|
145 | for (NodeIt n(graph); n != INVALID; ++n) { |
---|
146 | int deg = 0; |
---|
147 | for (IncEdgeIt e(graph, n); e != INVALID; ++e) { |
---|
148 | if (pe.kuratowski(e)) { |
---|
149 | ++deg; |
---|
150 | } |
---|
151 | } |
---|
152 | ++degs[deg]; |
---|
153 | } |
---|
154 | for (std::map<int, int>::iterator it = degs.begin(); it != degs.end(); ++it) { |
---|
155 | check(it->first == 0 || it->first == 2 || |
---|
156 | (it->first == 3 && it->second == 6) || |
---|
157 | (it->first == 4 && it->second == 5), |
---|
158 | "Wrong degree in Kuratowski graph"); |
---|
159 | } |
---|
160 | |
---|
161 | // Not full test |
---|
162 | check((degs[3] == 0) != (degs[4] == 0), "Wrong Kuratowski graph"); |
---|
163 | } |
---|
164 | |
---|
165 | bool intersect(Point<int> e1, Point<int> e2, Point<int> f1, Point<int> f2) { |
---|
166 | int l, r; |
---|
167 | if (std::min(e1.x, e2.x) > std::max(f1.x, f2.x)) return false; |
---|
168 | if (std::max(e1.x, e2.x) < std::min(f1.x, f2.x)) return false; |
---|
169 | if (std::min(e1.y, e2.y) > std::max(f1.y, f2.y)) return false; |
---|
170 | if (std::max(e1.y, e2.y) < std::min(f1.y, f2.y)) return false; |
---|
171 | |
---|
172 | l = (e2.x - e1.x) * (f1.y - e1.y) - (e2.y - e1.y) * (f1.x - e1.x); |
---|
173 | r = (e2.x - e1.x) * (f2.y - e1.y) - (e2.y - e1.y) * (f2.x - e1.x); |
---|
174 | if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false; |
---|
175 | l = (f2.x - f1.x) * (e1.y - f1.y) - (f2.y - f1.y) * (e1.x - f1.x); |
---|
176 | r = (f2.x - f1.x) * (e2.y - f1.y) - (f2.y - f1.y) * (e2.x - f1.x); |
---|
177 | if (!((l >= 0 && r <= 0) || (l <= 0 && r >= 0))) return false; |
---|
178 | return true; |
---|
179 | } |
---|
180 | |
---|
181 | bool collinear(Point<int> p, Point<int> q, Point<int> r) { |
---|
182 | int v; |
---|
183 | v = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x); |
---|
184 | if (v != 0) return false; |
---|
185 | v = (q.x - p.x) * (r.x - p.x) + (q.y - p.y) * (r.y - p.y); |
---|
186 | if (v < 0) return false; |
---|
187 | return true; |
---|
188 | } |
---|
189 | |
---|
190 | void checkDrawing(const Graph& graph, PD& pd) { |
---|
191 | for (Graph::NodeIt n(graph); n != INVALID; ++n) { |
---|
192 | Graph::NodeIt m(n); |
---|
193 | for (++m; m != INVALID; ++m) { |
---|
194 | check(pd[m] != pd[n], "Two nodes with identical coordinates"); |
---|
195 | } |
---|
196 | } |
---|
197 | |
---|
198 | for (Graph::EdgeIt e(graph); e != INVALID; ++e) { |
---|
199 | for (Graph::EdgeIt f(e); f != e; ++f) { |
---|
200 | Point<int> e1 = pd[graph.u(e)]; |
---|
201 | Point<int> e2 = pd[graph.v(e)]; |
---|
202 | Point<int> f1 = pd[graph.u(f)]; |
---|
203 | Point<int> f2 = pd[graph.v(f)]; |
---|
204 | |
---|
205 | if (graph.u(e) == graph.u(f)) { |
---|
206 | check(!collinear(e1, e2, f2), "Wrong drawing"); |
---|
207 | } else if (graph.u(e) == graph.v(f)) { |
---|
208 | check(!collinear(e1, e2, f1), "Wrong drawing"); |
---|
209 | } else if (graph.v(e) == graph.u(f)) { |
---|
210 | check(!collinear(e2, e1, f2), "Wrong drawing"); |
---|
211 | } else if (graph.v(e) == graph.v(f)) { |
---|
212 | check(!collinear(e2, e1, f1), "Wrong drawing"); |
---|
213 | } else { |
---|
214 | check(!intersect(e1, e2, f1, f2), "Wrong drawing"); |
---|
215 | } |
---|
216 | } |
---|
217 | } |
---|
218 | } |
---|
219 | |
---|
220 | void checkColoring(const Graph& graph, PC& pc, int num) { |
---|
221 | for (NodeIt n(graph); n != INVALID; ++n) { |
---|
222 | check(pc.colorIndex(n) >= 0 && pc.colorIndex(n) < num, |
---|
223 | "Wrong coloring"); |
---|
224 | } |
---|
225 | for (EdgeIt e(graph); e != INVALID; ++e) { |
---|
226 | check(pc.colorIndex(graph.u(e)) != pc.colorIndex(graph.v(e)), |
---|
227 | "Wrong coloring"); |
---|
228 | } |
---|
229 | } |
---|
230 | |
---|
231 | int main() { |
---|
232 | |
---|
233 | for (int i = 0; i < lgfn; ++i) { |
---|
234 | std::istringstream lgfs(lgf[i]); |
---|
235 | |
---|
236 | SmartGraph graph; |
---|
237 | graphReader(graph, lgfs).run(); |
---|
238 | |
---|
239 | check(simpleGraph(graph), "Test graphs must be simple"); |
---|
240 | |
---|
241 | PE pe(graph); |
---|
242 | bool planar = pe.run(); |
---|
243 | check(checkPlanarity(graph) == planar, "Planarity checking failed"); |
---|
244 | |
---|
245 | if (planar) { |
---|
246 | checkEmbedding(graph, pe); |
---|
247 | |
---|
248 | PlanarDrawing<Graph> pd(graph); |
---|
249 | pd.run(pe.embeddingMap()); |
---|
250 | checkDrawing(graph, pd); |
---|
251 | |
---|
252 | PlanarColoring<Graph> pc(graph); |
---|
253 | pc.runFiveColoring(pe.embeddingMap()); |
---|
254 | checkColoring(graph, pc, 5); |
---|
255 | |
---|
256 | } else { |
---|
257 | checkKuratowski(graph, pe); |
---|
258 | } |
---|
259 | } |
---|
260 | |
---|
261 | return 0; |
---|
262 | } |
---|