1/** \file
2 * \brief Test helpers for layout algorithms
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 <iomanip>
35#include <random>
36#include <regex>
37
38#include <ogdf/basic/DisjointSets.h>
39#include <ogdf/basic/GraphAttributes.h>
40#include <ogdf/basic/PriorityQueue.h>
41#include <ogdf/module/LayoutModule.h>
42#include <ogdf/basic/LayoutStatistics.h>
43
44#include <ogdf/planarity/PlanarSubgraphCactus.h>
45#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>
46
47#include <graphs.h>
48
49//#define OGDF_LAYOUT_HELPERS_PRINT_DRAWINGS
50
51#define TEST_LAYOUT(TYPE, ...) describeLayout<TYPE>(#TYPE, 0, {__VA_ARGS__})
52
53#ifdef OGDF_LAYOUT_HELPERS_PRINT_DRAWINGS
54namespace layout_helpers {
55 int drawingCounter = 0;
56}
57#endif
58
59inline void getRandomLayout(GraphAttributes &GA)
60{
61 const Graph &G = GA.constGraph();
62 double max_x = 2.0 * sqrt(G.numberOfNodes());
63 double max_y = max_x;
64
65 std::minstd_rand rng(randomSeed());
66 std::uniform_real_distribution<> rand_x(0.0,max_x);
67 std::uniform_real_distribution<> rand_y(0.0,max_y);
68
69 for(node v : G.nodes) {
70 GA.x(v) = rand_x(rng);
71 GA.y(v) = rand_y(rng);
72 }
73}
74
75//! Calls the layout algorithm \p L on \p G.
76/**
77 * Executes the layout algorithm, prints statistics and performs several assertions.
78 *
79 * @param name Name of the instance. Used only for debug output.
80 * @param G Input graph.
81 * @param L Algorithm to execute.
82 * @param extraAttributes GraphAttribute flags that this algorithm requires (besides graphics and style).
83 * @param algoPlanarizes Whether the algorithm planarizes non-planar graphs internally (i.e., produces drawings with a reasonable crossing number).
84 * @param algoRequiresPlanar Whether the algorithm requires planar graphs (not necessarily embeddings) as input.
85 * @param instanceIsPlanar Whether \p L is a planar graph.
86 *
87 **/
88inline int64_t callLayout(const string& name, const Graph &G, LayoutModule &L, long extraAttributes, bool algoPlanarizes, bool algoRequiresPlanar, bool instanceIsPlanar)
89{
90 GraphAttributes GA(G, extraAttributes | GraphAttributes::nodeGraphics | GraphAttributes::nodeStyle | GraphAttributes::edgeGraphics | GraphAttributes::edgeStyle);
91 getRandomLayout(GA);
92
93 int64_t result;
94 int64_t time;
95 System::usedRealTime(time);
96 L.call(GA);
97 result = System::usedRealTime(time);
98
99#ifdef OGDF_LAYOUT_HELPERS_PRINT_DRAWINGS
100 double sumWidths = 0;
101 double sumHeights = 0;
102
103 GA.addAttributes(GraphAttributes::nodeLabel | GraphAttributes::edgeArrow);
104
105 for (node v : G.nodes) {
106 sumWidths += GA.width(v);
107 sumHeights += GA.height(v);
108
109 GA.fillColor(v) = Color::Name::Red;
110 GA.strokeColor(v) = Color::Name::Black;
111 GA.label(v) = to_string(v->index());
112 }
113
114 for(edge e : G.edges) {
115 GA.strokeWidth(e) = 1;
116 GA.strokeColor(e) = Color::Name::Blue;
117 GA.arrowType(e) = EdgeArrow::Last;
118 }
119
120 GA.scale(sumWidths / GA.boundingBox().width(), sumHeights / GA.boundingBox().height(), false);
121 GA.scale(1.5, false);
122
123 std::regex reg("\\W+");
124 string filename = name;
125 std::transform(filename.begin(), filename.end(), filename.begin(), ::tolower);
126 std::ofstream of("drawing-" + std::regex_replace(filename, reg, "_")
127 + "-n=" + to_string(G.numberOfNodes()) + "-m=" + to_string(G.numberOfEdges())
128 + "-" + to_string(layout_helpers::drawingCounter) + ".svg");
129 GraphIO::drawSVG(GA, of);
130 layout_helpers::drawingCounter++;
131#endif
132
133 string indent = " ";
134 std::cout << std::endl;
135 double resolution = (Math::minValue(LayoutStatistics::angles(GA))*100) / (2*Math::pi);
136 double avgEdgeLength = Math::mean(LayoutStatistics::edgeLengths(GA));
137 double avgBends = Math::mean(LayoutStatistics::numberOfBends(GA));
138 double avgNodeCrossings = Math::mean(LayoutStatistics::numberOfNodeCrossings(GA));
139 double avgNodeOverlaps = Math::mean(LayoutStatistics::numberOfNodeOverlaps(GA));
140 std::cout << indent << "angular resolution: " << std::setw(18) << std::setprecision(2) << std::fixed << resolution << " %" << std::endl;
141 std::cout << indent << "average edge length: " << std::setw(17) << avgEdgeLength << std::endl;
142 std::cout << indent << "average bends per edge: " << std::setw(14) << avgBends << std::endl;
143 std::cout << indent << "average node crossings per edge: " << std::setw(5) << avgNodeCrossings << std::endl;
144 std::cout << indent << "average node overlaps per node: " << std::setw(6) << avgNodeOverlaps << std::endl;
145
146 // Assert that we do not have any needless bendpoints
147 for(edge e : G.edges) {
148 auto toPoint = [&](node v) { return DPoint(GA.x(v), GA.y(v)); };
149 DPolyline bends = GA.bends(e);
150
151 if(!bends.empty()) {
152 AssertThat(bends.front(), !Equals(toPoint(e->source())));
153 AssertThat(bends.back(), !Equals(toPoint(e->target())));
154 }
155
156 int size = bends.size();
157 bends.normalize();
158 AssertThat(bends.size(), Equals(size));
159 }
160
161 // Assume that any layout algorithm that requires planar graphs or planarize produces planar drawings
162 if(algoPlanarizes || algoRequiresPlanar) {
163 int crossingNumber = Math::sum(LayoutStatistics::numberOfCrossings(GA)) / 2;
164
165 std::cout << indent << "crossing number: " << std::setw(9) << crossingNumber << std::endl;
166
167 if(instanceIsPlanar) {
168 AssertThat(crossingNumber, Equals(0));
169 }
170 }
171
172 return result;
173}
174
175/**
176 * Runs several tests for a given layout module.
177 * The layout algorithm is executed for different graphs.
178 * There are no assertions yet.
179 *
180 * \param name
181 * the name to be used for describing this module
182 * \param L
183 * the module to be tested
184 * \param extraAttributes
185 * init attributes for GraphAttributes
186 * \param req
187 * the requirements for graphs to be drawn, see GraphPropertyFlags for details
188 * \param sizes
189 * determines the approximate number of nodes (and instances) of randomly generated graphs
190 * \param planarizes
191 * whether the layout computes a planarization (i.e., we can expect few crossings for non-planar graphs)
192 * \param skipMe
193 * set this to true to skip the entire test
194 */
195inline void describeLayout(
196 const std::string name,
197 LayoutModule &L,
198 long extraAttributes = 0,
199 std::set<GraphProperty> req = {},
200 bool planarizes = false,
201 const GraphSizes& sizes = GraphSizes(),
202 bool skipMe = false)
203{
204 describe(name, [&] {
205 forEachGraphItWorks(req, [&](const Graph& G, const std::string& graphName, const std::set<GraphProperty>& props) {
206 callLayout(graphName, G, L, extraAttributes, planarizes,
207 doesInclude({GraphProperty::planar}, req),
208 doesInclude({GraphProperty::planar}, props));
209 }, sizes);
210 }, skipMe);
211}
212
213template<typename T>
214inline void describeLayout(
215 const string &name,
216 int extraAttr = 0,
217 std::set<GraphProperty> req = {},
218 bool planarizes = false,
219 const GraphSizes& sizes = GraphSizes(),
220 bool skipMe = false) {
221 T layout;
222 describeLayout(name, layout, extraAttr, req, planarizes, sizes, skipMe);
223}
224