1/** \file
2 * \brief Tests for SugiyamaLayout
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/layered/SugiyamaLayout.h>
33#include <ogdf/layered/FastHierarchyLayout.h>
34#include <ogdf/layered/MedianHeuristic.h>
35#include <ogdf/layered/OptimalHierarchyLayout.h>
36#include <ogdf/layered/OptimalRanking.h>
37#include <ogdf/layered/GreedyCycleRemoval.h>
38#include <ogdf/layered/CoffmanGrahamRanking.h>
39#include <ogdf/layered/LongestPathRanking.h>
40#include <ogdf/layered/DfsAcyclicSubgraph.h>
41#include <ogdf/layered/FastSimpleHierarchyLayout.h>
42#include <ogdf/layered/GridSifting.h>
43#include <ogdf/layered/BarycenterHeuristic.h>
44#include <ogdf/layered/GreedyInsertHeuristic.h>
45#include <ogdf/layered/GreedySwitchHeuristic.h>
46#include <ogdf/layered/SplitHeuristic.h>
47#include <ogdf/layered/SiftingHeuristic.h>
48
49#include "layout_helpers.h"
50
51#define DESCRIBE_SUGI_LAYOUT(TYPE, ...) describeSugi<TYPE>(#TYPE, __VA_ARGS__)
52#define DESCRIBE_SUGI_RANKING(TYPE, ...) describeSugiRanking<TYPE>(#TYPE, __VA_ARGS__)
53#define DESCRIBE_SUGI_CROSSMIN(TYPE, ...) describeSugiCrossMin<TYPE>(#TYPE, __VA_ARGS__)
54
55template<class CrossMin>
56void describeSugiCrossMin(const std::string& name, SugiyamaLayout& sugi, const std::set<GraphProperty>& reqs, bool skipMe = false) {
57 sugi.setCrossMin(new CrossMin);
58 describeLayout(name, sugi, 0, reqs, false, GraphSizes(16, 32, 16), skipMe);
59}
60
61template<class Ranking>
62void describeSugiRanking(const std::string& name, SugiyamaLayout& sugi, const std::set<GraphProperty>& reqs, Ranking* ranking = nullptr) {
63 describe(name, [&] {
64 sugi.setRanking(ranking == nullptr ? new Ranking : ranking);
65
66 auto reqsGS = reqs;
67 reqsGS.insert(GraphProperty::connected);
68
69 // TODO GlobalSifting and GridSifting use BlockOrder which appears broken
70 DESCRIBE_SUGI_CROSSMIN(GlobalSifting, sugi, reqs, true);
71 DESCRIBE_SUGI_CROSSMIN(GridSifting, sugi, reqs, true);
72 DESCRIBE_SUGI_CROSSMIN(BarycenterHeuristic, sugi, reqs);
73 DESCRIBE_SUGI_CROSSMIN(GreedyInsertHeuristic, sugi, reqs);
74 DESCRIBE_SUGI_CROSSMIN(GreedySwitchHeuristic, sugi, reqsGS);
75 DESCRIBE_SUGI_CROSSMIN(MedianHeuristic, sugi, reqs);
76 DESCRIBE_SUGI_CROSSMIN(SiftingHeuristic, sugi, reqs);
77 DESCRIBE_SUGI_CROSSMIN(SplitHeuristic, sugi, reqs);
78 });
79}
80
81template<class Layout>
82void describeSugi(const std::string& name, const std::set<GraphProperty>& reqs) {
83 describe(name, [&] {
84 SugiyamaLayout sugi;
85 sugi.runs(std::min(4u, Thread::hardware_concurrency()));
86 sugi.setLayout(new Layout);
87
88 DESCRIBE_SUGI_RANKING(CoffmanGrahamRanking, sugi, reqs);
89 DESCRIBE_SUGI_RANKING(LongestPathRanking, sugi, reqs);
90
91 auto* r = new OptimalRanking;
92 r->setSubgraph(new DfsAcyclicSubgraph);
93 describeSugiRanking<>("OptimalRanking with DfsAcyclicSubgraph", sugi, reqs, r);
94
95 r = new OptimalRanking;
96 r->setSubgraph(new GreedyCycleRemoval);
97 describeSugiRanking<>("OptimalRanking with GreedyCycleRemoval", sugi, reqs, r);
98 });
99}
100
101go_bandit([] {
102 describe("SugiyamaLayout", [] {
103 DESCRIBE_SUGI_LAYOUT(FastHierarchyLayout, {GraphProperty::sparse});
104 DESCRIBE_SUGI_LAYOUT(FastSimpleHierarchyLayout, {GraphProperty::sparse});
105 describeSugi<OptimalHierarchyLayout>("OptimalHierarchyLayout", {GraphProperty::simple, GraphProperty::sparse});
106 });
107});
108