1/** \file
2 * \brief Graph collection for tests
3 *
4 * \author Tilo Wiedera
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#pragma once
33
34#include <set>
35
36#include <ogdf/basic/graph_generators.h>
37#include <ogdf/basic/simple_graph_alg.h>
38
39#include <resources.h>
40
41class GraphSizes {
42 const int m_min;
43 const int m_max;
44 const int m_step;
45public:
46 //! Creates feasible graph sizes ranging from \p min to \p max
47 //! with a step size of \p step.
48 GraphSizes(int min, int max, int step) :
49 m_min(min), m_max(max), m_step(step) {
50 OGDF_ASSERT(m_min <= m_max);
51 OGDF_ASSERT(m_step > 0);
52 }
53
54 //! Default graphs sizes result in 3 iterations
55 //! over graphs with at most 100 nodes
56 GraphSizes() : GraphSizes(16, 100, 42) {}
57
58 //! Creates just one feasible size that is \p n
59 GraphSizes(int n) : GraphSizes(n, n, 1) {}
60
61 //! calls \p func for each feasible graph size
62 void forEachSize(std::function<void(int size)> func) const {
63 for(int n = m_min; n <= m_max; n += m_step) {
64 func(n);
65 }
66 }
67};
68
69enum class GraphProperty {
70 //! Indicates graphs that are (directed!) acyclic.
71 acyclic,
72
73 arborescenceForest,
74 connected,
75 biconnected,
76 nonPlanar,
77 maxDeg4,
78 planar,
79 triconnected,
80
81 //! Indicates graphs that are (undirected!) simple.
82 simple,
83
84 //! Indicates instances that have a reasonably low number of edges.
85 //! These graphs can, e.g., be used for planarization layouts without raising runtime too much.
86 sparse
87};
88
89//! Randomly adds loops and parallel edges to \p G.
90/**
91 * For each edge, we add parallel edges until an event with probability 1 - \p p is encountered.
92 * For each node, we do the same creating loops.
93 */
94inline void addMultiEdges(Graph& G, double p) {
95 OGDF_ASSERT(p >= 0);
96 OGDF_ASSERT(p < 1);
97
98 auto byChance = [&]() -> bool { return randomDouble(0, 1) < p; };
99
100 List<edge> edges;
101 G.allEdges(edges);
102
103 for (node v : G.nodes) {
104 while (byChance()) {
105 G.newEdge(v, v);
106 }
107 }
108
109 for (edge e : edges) {
110 node v = e->source();
111 node w = e->target();
112
113 while (byChance()) {
114 G.newEdge(v, w);
115
116 if (byChance()) {
117 std::swap(v, w);
118 }
119 }
120 }
121}
122
123/**
124 * Creates a planar disconnected graphs that contains cut vertices.
125 *
126 * @param G Input graph.
127 * @param nMax Approximate maximum number of nodes,
128 * @param densityMin Approximate minimum edge density (relative to actual number of nodes).
129 * @param densityMax Approximate maximum edge density (relative to actual number of nodes).
130 * @param cc Number of connected components to create.
131 * @param bc Number of biconnected components to create per connected component.
132 */
133inline void createDisconnectedGraph(
134 Graph &G,
135 int nMax,
136 double densityMin,
137 double densityMax,
138 int cc,
139 int bc)
140{
141 OGDF_ASSERT(cc > 0);
142 OGDF_ASSERT(bc > 0);
143 OGDF_ASSERT(densityMin > 0);
144 OGDF_ASSERT(densityMax >= densityMin);
145 OGDF_ASSERT(densityMax < 3);
146
147 G.clear();
148
149 int nBcMax = ceil(nMax / (cc*bc));
150 nBcMax = std::max(nBcMax, 2);
151
152 for(int i = 0; i < cc; i++) {
153 int m = ceil(randomDouble(densityMin*nBcMax, densityMax*nBcMax));
154 Graph H;
155 randomPlanarCNBGraph(H, nBcMax, m, bc);
156 G.insert(H);
157 }
158}
159
160inline void createAlmostPlanarGraph(Graph &G, int n, int m, int add_m)
161{
162 randomPlanarBiconnectedGraph(G, n, m);
163
164 Array<node> table(n);
165
166 int i = 0;
167 for(node v : G.nodes) {
168 OGDF_ASSERT(i < n);
169 table[i++] = v;
170 }
171
172 for(i = 0; i < add_m; ++i) {
173 G.newEdge(table[randomNumber(0, n-1)], table[randomNumber(0, n-1)]);
174 }
175
176 makeSimpleUndirected(G);
177}
178
179//! Returns true if \p subset is a subset of \p superset
180inline bool doesInclude(const std::set<GraphProperty>& subset, const std::set<GraphProperty>& superset) {
181 for (auto r : subset) {
182 if(superset.find(r) == superset.end()) {
183 return false;
184 }
185 }
186
187 return true;
188}
189
190inline void imply(std::set<GraphProperty>& props, GraphProperty conclusion, GraphProperty premise) {
191 if (doesInclude({premise}, props)) {
192 props.insert(conclusion);
193 }
194};
195
196inline void performImplications(std::set<GraphProperty>& props) {
197 imply(props, GraphProperty::biconnected, GraphProperty::triconnected);
198 imply(props, GraphProperty::connected, GraphProperty::biconnected);
199 imply(props, GraphProperty::planar, GraphProperty::arborescenceForest);
200 imply(props, GraphProperty::acyclic, GraphProperty::arborescenceForest);
201
202 if (doesInclude({GraphProperty::simple}, props) &&
203 (doesInclude({GraphProperty::maxDeg4}, props) || doesInclude({GraphProperty::planar}, props))) {
204 props.insert(GraphProperty::sparse);
205 }
206
207 OGDF_ASSERT(!doesInclude({GraphProperty::nonPlanar, GraphProperty::planar}, props));
208};
209
210//! Make \p G (undirected) simple by splitting parallel edges.
211//! Compared to ogdf::makeSimpleUndirected, this maintains biconnectivity.
212inline void splitParallelEdges(Graph& G) {
213 List<edge> edges;
214 G.allEdges(edges);
215
216 for(edge e : edges) {
217 for (adjEntry adj : e->source()->adjEntries) {
218 if (adj->twinNode() == e->target() && adj->theEdge() != e) {
219 G.split(e);
220 }
221 }
222 }
223}
224
225/**
226 * Performs tests on a diverse set of graphs.
227 *
228 * @param requirements Required properties that feasible graphs must have.
229 * @param doTest Actual test routine for given graph.
230 * @param sizes Approximate number of nodes (and number of instances) for randomly generated graphs.
231 * @param stepSize Increase for number of nodes between steps for randomly generated graphs.
232 */
233inline void forEachGraphItWorks(std::set<GraphProperty> requirements,
234 std::function<void(const Graph&, const std::string &graphName, const std::set<GraphProperty>& props)> doTest,
235 GraphSizes sizes = GraphSizes()) {
236 auto testInstance = [&](const string& desc, std::set<GraphProperty> props, std::function<void(Graph&)> generateGraph) {
237 performImplications(props);
238
239 if (doesInclude(requirements, props)) {
240 bandit::it("works on a " + desc, [&] {
241 Graph G;
242 generateGraph(G);
243 doTest(G, desc, props);
244 });
245 }
246 };
247
248 auto testInstances = [&](const string& desc, std::set<GraphProperty> props, std::function<void(Graph&, int)> generateGraph) {
249 sizes.forEachSize([&](int n) {
250 testInstance(desc + " [n≈" + to_string(n) + "]", props, [&](Graph& G) { generateGraph(G, n); });
251 });
252 };
253
254 testInstances("arborescence",
255 { GraphProperty::arborescenceForest,
256 GraphProperty::connected,
257 GraphProperty::simple,
258 GraphProperty::sparse },
259 [](Graph &G, int n) { randomTree(G, n); });
260
261 testInstances("arborescence forest",
262 { GraphProperty::arborescenceForest,
263 GraphProperty::simple,
264 GraphProperty::sparse },
265 [](Graph &G, int n) {
266 randomTree(G, n);
267
268 // make graph disconnected
269 for(int i = 0; i < 3; i++) {
270 G.delEdge(G.chooseEdge());
271 }
272 });
273
274 testInstances("3-regular arborescence",
275 { GraphProperty::arborescenceForest,
276 GraphProperty::connected,
277 GraphProperty::maxDeg4,
278 GraphProperty::simple },
279 [](Graph &G, int n) { regularTree(G, n, 3); });
280
281 testInstance("path-like tree",
282 { GraphProperty::connected,
283 GraphProperty::planar,
284 GraphProperty::simple },
285 [](Graph& G) {
286 std::stringstream ss{ResourceFile::get("misc/path-like_tree.gml")->data()};
287 GraphIO::read(G, ss);
288 });
289
290 testInstance("K4",
291 { GraphProperty::maxDeg4,
292 GraphProperty::planar,
293 GraphProperty::simple,
294 GraphProperty::triconnected},
295 [](Graph& G) { completeGraph(G, 4); });
296
297 testInstance("K2,3",
298 { GraphProperty::maxDeg4,
299 GraphProperty::planar,
300 GraphProperty::simple,
301 GraphProperty::biconnected },
302 [](Graph& G) { completeBipartiteGraph(G, 2, 3); });
303
304 testInstance("K5",
305 { GraphProperty::nonPlanar,
306 GraphProperty::maxDeg4,
307 GraphProperty::simple,
308 GraphProperty::triconnected },
309 [](Graph& G) { completeGraph(G, 5); });
310
311 testInstance("K3,3",
312 { GraphProperty::nonPlanar,
313 GraphProperty::maxDeg4,
314 GraphProperty::simple,
315 GraphProperty::triconnected },
316 [](Graph& G) { completeBipartiteGraph(G, 3, 3); });
317
318 testInstances("connected sparse graph",
319 { GraphProperty::connected,
320 GraphProperty::simple,
321 GraphProperty::sparse },
322 [](Graph &G, int n) {
323 randomSimpleGraph(G, n, 2*n);
324 makeConnected(G);
325 });
326
327 testInstances("connected dense graph",
328 { GraphProperty::connected,
329 GraphProperty::simple },
330 [](Graph &G, int n) {
331 randomSimpleGraph(G, n,(n*n)/4);
332 makeConnected(G);
333 });
334
335 testInstances("4-regular graph",
336 { GraphProperty::maxDeg4 },
337 [](Graph &G, int n) { randomRegularGraph(G, n, 4); });
338
339
340 testInstances("acyclic grid graph",
341 { GraphProperty::acyclic,
342 GraphProperty::biconnected,
343 GraphProperty::maxDeg4,
344 GraphProperty::planar,
345 GraphProperty::simple },
346 [](Graph &G, int n) { gridGraph(G, sqrt(n), sqrt(n), false, false); });
347
348 testInstances("wheel graph",
349 { GraphProperty::biconnected,
350 GraphProperty::planar,
351 GraphProperty::simple },
352 [](Graph &G, int n) { wheelGraph(G, n); });
353
354 testInstances("series parallel DAG",
355 { GraphProperty::acyclic,
356 GraphProperty::connected,
357 GraphProperty::planar,
358 GraphProperty::simple },
359 [](Graph &G, int n) { randomSeriesParallelDAG(G, n); });
360
361 testInstances("connected planar graph",
362 { GraphProperty::connected,
363 GraphProperty::planar,
364 GraphProperty::simple },
365 [](Graph &G, int n) { randomPlanarConnectedGraph(G, n, 2*n); });
366
367 testInstances("biconnected almost planar graph",
368 { GraphProperty::biconnected,
369 GraphProperty::nonPlanar,
370 GraphProperty::simple,
371 GraphProperty::sparse },
372 [](Graph &G, int n) { createAlmostPlanarGraph(G, n, 2*n, 10); });
373
374 testInstances("biconnected graph",
375 { GraphProperty::biconnected,
376 GraphProperty::simple,
377 GraphProperty::sparse },
378 [](Graph &G, int n) {
379 randomBiconnectedGraph(G, n, 2*n);
380 splitParallelEdges(G);
381 });
382
383 testInstances("acyclic biconnected planar graph",
384 { GraphProperty::biconnected,
385 GraphProperty::planar,
386 GraphProperty::simple },
387 [](Graph &G, int n) {
388 randomPlanarBiconnectedDigraph(G, n, 2*n);
389 splitParallelEdges(G);
390 });
391
392 testInstances("acyclic biconnected non-planar graph",
393 { GraphProperty::biconnected,
394 GraphProperty::nonPlanar,
395 GraphProperty::simple,
396 GraphProperty::sparse },
397 [](Graph &G, int n) {
398 randomBiconnectedGraph(G, n, 3*n - 5);
399 splitParallelEdges(G);
400 });
401
402 testInstances("triconnected graph",
403 { GraphProperty::simple,
404 GraphProperty::triconnected },
405 [](Graph &G, int n) { randomTriconnectedGraph(G, n, .5, .5); });
406
407 testInstances("triconnected planar graph",
408 { GraphProperty::planar,
409 GraphProperty::simple,
410 GraphProperty::triconnected },
411 [](Graph &G, int n) { randomPlanarTriconnectedGraph(G, n, .5, .5); });
412
413 testInstances("maximal planar graph",
414 { GraphProperty::planar,
415 GraphProperty::simple,
416 GraphProperty::triconnected },
417 [](Graph &G, int n) { randomPlanarBiconnectedGraph(G, n, 3*n - 6); });
418
419 testInstances("disconnected planar graph",
420 { GraphProperty::planar,
421 GraphProperty::simple },
422 [](Graph &G, int n) { createDisconnectedGraph(G, n, 1.4, 2.6, 3, 3); });
423
424 testInstances("planar dense triconnected multi-graph",
425 { GraphProperty::planar,
426 GraphProperty::triconnected },
427 [](Graph &G, int n) {
428 randomPlanarTriconnectedGraph(G, n, .5, .5);
429 addMultiEdges(G, .5);
430 });
431
432 testInstances("planar sparse triconnected multi-graph",
433 { GraphProperty::planar,
434 GraphProperty::sparse,
435 GraphProperty::triconnected },
436 [](Graph &G, int n) {
437 randomPlanarTriconnectedGraph(G, n, .5, .5);
438 addMultiEdges(G, 5.0/n);
439 });
440}
441
442inline void forEachGraphItWorks(std::set<GraphProperty> requirements,
443 std::function<void(const Graph&)> doTest,
444 GraphSizes sizes = GraphSizes()) {
445 forEachGraphItWorks(
446 requirements,
447 [&](const Graph& G, const std::string&, const std::set<GraphProperty>&) { doTest(G); },
448 sizes);
449}
450