|
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 if (pe.run()) { |
|
243 checkEmbedding(graph, pe); |
|
244 |
|
245 PlanarDrawing<Graph> pd(graph); |
|
246 pd.run(pe.embedding()); |
|
247 checkDrawing(graph, pd); |
|
248 |
|
249 PlanarColoring<Graph> pc(graph); |
|
250 pc.runFiveColoring(pe.embedding()); |
|
251 checkColoring(graph, pc, 5); |
|
252 |
|
253 } else { |
|
254 checkKuratowski(graph, pe); |
|
255 } |
|
256 } |
|
257 |
|
258 return 0; |
|
259 } |