1#include <ogdf/basic/graph_generators.h>
2#include <ogdf/planarity/EmbedderMaxFace.h>
3#include <ogdf/planarity/EmbedderMaxFaceLayers.h>
4#include <ogdf/planarity/EmbedderMinDepth.h>
5#include <ogdf/planarity/EmbedderMinDepthMaxFace.h>
6#include <ogdf/planarity/EmbedderMinDepthMaxFaceLayers.h>
7#include <ogdf/planarity/EmbedderMinDepthPiTa.h>
8#include <ogdf/planarity/EmbedderOptimalFlexDraw.h>
9#include <ogdf/planarity/SimpleEmbedder.h>
10
11#include <graphs.h>
12
13#define TEST_EMBEDDER(NAME) describeEmbedder<NAME>(#NAME)
14
15void validateCopy(const Graph &graph, const GraphCopy &copy) {
16 AssertThat(graph.numberOfNodes(), Equals(copy.numberOfNodes()));
17 AssertThat(graph.numberOfEdges(), Equals(copy.numberOfEdges()));
18
19 for(node v : copy.nodes) {
20 AssertThat(copy.isDummy(v), IsFalse());
21 }
22
23 for(edge e : copy.edges) {
24 AssertThat(copy.isDummy(e), IsFalse());
25 edge f = copy.original(e);
26 AssertThat(f->source(), Equals(copy.original(e->source())));
27 AssertThat(f->target(), Equals(copy.original(e->target())));
28 }
29}
30
31void shuffleEmbedding(Graph &graph) {
32 for(node v : graph.nodes) {
33 for(adjEntry adj : v->adjEntries) {
34 graph.swapAdjEdges(adj, randomNumber(0, 1) ? v->firstAdj() : v->lastAdj());
35 }
36 }
37}
38
39void testEmbedder(EmbedderModule &embedder, const Graph &graph, bool repeat = true) {
40 GraphCopy copy(graph);
41 if(repeat) {
42 shuffleEmbedding(copy);
43 }
44 // initialize adjExternal with a corrupt value
45 adjEntry adjExternal = graph.firstNode()->firstAdj();
46
47 embedder(copy, adjExternal);
48
49 validateCopy(graph, copy);
50 AssertThat(adjExternal, !IsNull());
51#ifdef OGDF_DEBUG
52 AssertThat(adjExternal->graphOf(), Equals(&copy));
53#endif
54 AssertThat(copy.representsCombEmbedding(), IsTrue());
55
56 // test planarly embedded input
57 if(repeat) {
58 testEmbedder(embedder, copy, false);
59 }
60}
61
62void describeEmbedder(const string &title, EmbedderModule &embedder, std::set<GraphProperty> requirements = {}, bool doSkip = false) {
63 describe(title, [&] {
64 requirements.insert(GraphProperty::connected);
65 requirements.insert(GraphProperty::planar);
66 requirements.insert(GraphProperty::simple);
67
68 forEachGraphItWorks(requirements, [&](const Graph& G) { testEmbedder(embedder, G); });
69
70#ifdef OGDF_USE_ASSERT_EXCEPTIONS
71 it("fails on a K5", [&] {
72 adjEntry adjExternal;
73 Graph G;
74 completeGraph(G, 5);
75 AssertThrows(AssertionFailed, embedder(G, adjExternal));
76 });
77#endif
78 }, doSkip);
79}
80
81template<typename EmbedderType>
82void describeEmbedder(const string &title) {
83 EmbedderType embedder;
84 describeEmbedder(title, embedder);
85}
86
87template<>
88void describeEmbedder<EmbedderMinDepthPiTa>(const string &title) {
89 EmbedderMinDepthPiTa embedder;
90 bool extendedDD = embedder.useExtendedDepthDefinition();
91
92 // TODO Why does this embedder require biconnectivity?
93 // A BC-tree is used internally...
94 std::initializer_list<GraphProperty> reqs = {GraphProperty::biconnected};
95 describeEmbedder(title + " [extendedDD=" + to_string(extendedDD) + "]", embedder, reqs);
96 embedder.useExtendedDepthDefinition(!extendedDD);
97 describeEmbedder(title + " [extendedDD=" + to_string(!extendedDD) + "]", embedder, reqs);
98}
99
100// TODO currently skipped since these tests are failing.
101template<>
102void describeEmbedder<EmbedderOptimalFlexDraw>(const string &title) {
103 describe(title, [] {
104 EmbedderOptimalFlexDraw embedder;
105 describeEmbedder("Non-Weighted Version", embedder, {}, true);
106
107 describe_skip("Weighted Edges", [&] {
108 it("works on a random graph", [&] {
109 Graph graph;
110 constexpr int n = 42;
111 randomPlanarConnectedGraph(graph, n, 2*n);
112 EdgeArray<int> costs(graph);
113
114 for(edge e : graph.edges) {
115 costs[e] = randomNumber(1, n);
116 }
117
118 testEmbedder(embedder, graph);
119 });
120 });
121 });
122}
123
124go_bandit([]() {
125 describe("Embedders", []() {
126 TEST_EMBEDDER(EmbedderMaxFace);
127 TEST_EMBEDDER(EmbedderMaxFaceLayers);
128 TEST_EMBEDDER(EmbedderMinDepth);
129 TEST_EMBEDDER(EmbedderMinDepthMaxFace);
130 TEST_EMBEDDER(EmbedderMinDepthMaxFaceLayers);
131 TEST_EMBEDDER(EmbedderMinDepthPiTa);
132 TEST_EMBEDDER(EmbedderOptimalFlexDraw);
133 TEST_EMBEDDER(SimpleEmbedder);
134 });
135});
136