1/** \file
2 * \brief Tests for several energy-based layout classes
3 *
4 * \author Carsten Gutwenger, 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#include <ogdf/energybased/DavidsonHarelLayout.h>
33#include <ogdf/energybased/DTreeMultilevelEmbedder.h>
34#include <ogdf/energybased/FastMultipoleEmbedder.h>
35#include <ogdf/energybased/FMMMLayout.h>
36#include <ogdf/energybased/GEMLayout.h>
37#include <ogdf/energybased/MultilevelLayout.h>
38#include <ogdf/energybased/NodeRespecterLayout.h>
39#include <ogdf/energybased/PivotMDS.h>
40#include <ogdf/energybased/SpringEmbedderFRExact.h>
41#include <ogdf/energybased/SpringEmbedderGridVariant.h>
42#include <ogdf/energybased/SpringEmbedderKK.h>
43#include <ogdf/energybased/StressMinimization.h>
44#include <ogdf/energybased/TutteLayout.h>
45
46#include "layout_helpers.h"
47
48#define TEST_ENERGY_BASED_LAYOUT(NAME, EXTRA_ATTR, ...) describeEnergyBasedLayout<NAME>(#NAME, EXTRA_ATTR, {__VA_ARGS__})
49
50template<class T>
51void init(T& layout) {
52 // just keep the default
53}
54
55template<>
56void init(DavidsonHarelLayout& layout) {
57 layout.setNumberOfIterations(50);
58}
59
60template<>
61void init(FastMultipoleEmbedder& layout) {
62 layout.setNumIterations(50);
63 layout.setNumberOfThreads(System::numberOfProcessors());
64}
65
66template<>
67void init(FastMultipoleMultilevelEmbedder& layout) {
68 layout.maxNumThreads(System::numberOfProcessors());
69}
70
71template<>
72void init(FMMMLayout& layout) {
73 layout.fixedIterations(50);
74}
75
76template<>
77void init(GEMLayout& layout) {
78 layout.numberOfRounds(50);
79}
80
81template<>
82void init(NodeRespecterLayout& layout) {
83 layout.setNumberOfIterations(50);
84}
85
86template<>
87void init(SpringEmbedderFRExact& layout) {
88 layout.iterations(50);
89}
90
91template<>
92void init(SpringEmbedderGridVariant& layout) {
93 layout.iterations(25);
94 layout.iterationsImprove(25);
95}
96
97template<>
98void init(StressMinimization& layout) {
99 layout.setIterations(50);
100}
101
102template<class T>
103void describeEnergyBasedLayout(const string &name, int extraAttr, std::initializer_list<GraphProperty> requirements) {
104 T layout;
105 init(layout);
106 describeLayout(name, layout, extraAttr, requirements);
107}
108
109void describeFMMM() {
110 TEST_ENERGY_BASED_LAYOUT(FMMMLayout, 0);
111
112 FMMMLayout fmmm;
113
114 fmmm.fixedIterations(50);
115 fmmm.useHighLevelOptions(true);
116 fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::GorgeousAndEfficient);
117 describeLayout("FMMMLayout with high quality settings", fmmm);
118
119 fmmm.qualityVersusSpeed(FMMMOptions::QualityVsSpeed::NiceAndIncredibleSpeed);
120 describeLayout("FMMMLayout with nice quality and incredible speed", fmmm);
121
122 fmmm.allowedPositions(FMMMOptions::AllowedPositions::Exponent);
123 fmmm.edgeLengthMeasurement(FMMMOptions::EdgeLengthMeasurement::Midpoint);
124 fmmm.forceModel(FMMMOptions::ForceModel::Eades);
125 fmmm.galaxyChoice(FMMMOptions::GalaxyChoice::UniformProb);
126 fmmm.initialPlacementForces(FMMMOptions::InitialPlacementForces::UniformGrid);
127 fmmm.maxIterChange(FMMMOptions::MaxIterChange::RapidlyDecreasing);
128 fmmm.minGraphSize(10);
129 fmmm.nmParticlesInLeaves(70);
130 fmmm.nmSmallCell(FMMMOptions::SmallestCellFinding::Aluru);
131 fmmm.nmTreeConstruction(FMMMOptions::ReducedTreeConstruction::PathByPath);
132 fmmm.pageFormat(FMMMOptions::PageFormatType::Landscape);
133 fmmm.presortCCs(FMMMOptions::PreSort::None);
134 fmmm.stopCriterion(FMMMOptions::StopCriterion::FixedIterations);
135 fmmm.tipOverCCs(FMMMOptions::TipOver::None);
136 fmmm.useHighLevelOptions(false);
137 describeLayout("FMMMLayout with very specific configuration (using NewMultipoleMethod))", fmmm);
138
139 fmmm.allowedPositions(FMMMOptions::AllowedPositions::All);
140 fmmm.forceModel(FMMMOptions::ForceModel::FruchtermanReingold);
141 fmmm.galaxyChoice(FMMMOptions::GalaxyChoice::NonUniformProbHigherMass);
142 fmmm.initialPlacementForces(FMMMOptions::InitialPlacementForces::RandomTime);
143 fmmm.initialPlacementMult(FMMMOptions::InitialPlacementMult::Simple);
144 fmmm.maxIterChange(FMMMOptions::MaxIterChange::Constant);
145 fmmm.pageFormat(FMMMOptions::PageFormatType::Portrait);
146 fmmm.presortCCs(FMMMOptions::PreSort::DecreasingWidth);
147 fmmm.repulsiveForcesCalculation(FMMMOptions::RepulsiveForcesMethod::GridApproximation);
148 fmmm.stopCriterion(FMMMOptions::StopCriterion::Threshold);
149 fmmm.tipOverCCs(FMMMOptions::TipOver::Always);
150 describeLayout("FMMMLayout with very specific configuration (using GridApproximation)", fmmm);
151}
152
153go_bandit([] { describe("Energy-based layouts", [] {
154 TEST_ENERGY_BASED_LAYOUT(DavidsonHarelLayout, 0);
155
156 TEST_ENERGY_BASED_LAYOUT(DTreeMultilevelEmbedder2D, 0, GraphProperty::connected);
157 TEST_ENERGY_BASED_LAYOUT(DTreeMultilevelEmbedder3D, GraphAttributes::threeD, GraphProperty::connected);
158
159 TEST_ENERGY_BASED_LAYOUT(FastMultipoleEmbedder, 0, GraphProperty::connected);
160 TEST_ENERGY_BASED_LAYOUT(FastMultipoleMultilevelEmbedder, 0, GraphProperty::connected);
161
162 describeFMMM();
163
164 TEST_ENERGY_BASED_LAYOUT(GEMLayout, 0);
165
166 TEST_ENERGY_BASED_LAYOUT(MultilevelLayout, 0);
167
168 TEST_ENERGY_BASED_LAYOUT(NodeRespecterLayout, 0);
169
170 TEST_ENERGY_BASED_LAYOUT(PivotMDS, 0, GraphProperty::connected);
171
172 TEST_ENERGY_BASED_LAYOUT(SpringEmbedderFRExact, 0);
173
174 TEST_ENERGY_BASED_LAYOUT(SpringEmbedderGridVariant, 0);
175
176 TEST_ENERGY_BASED_LAYOUT(SpringEmbedderKK, 0, GraphProperty::connected);
177
178 TEST_ENERGY_BASED_LAYOUT(StressMinimization, 0);
179
180 TEST_ENERGY_BASED_LAYOUT(TutteLayout, 0, GraphProperty::triconnected, GraphProperty::planar, GraphProperty::simple);
181}); });
182