1/** \file
2 * \brief Tests for ogdf::DualGraph.
3 *
4 * \author Mirko Wagner, 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/basic/DualGraph.h>
33#include <ogdf/basic/graph_generators.h>
34
35#include <testing.h>
36
37//! Runs all tests on a single randomly generated graph with \c n nodes and \c m edges.
38void performIteration(int n, int m) {
39 Graph graph;
40 randomPlanarConnectedGraph(graph, n, m);
41 ConstCombinatorialEmbedding emb(graph);
42 DualGraph dual(emb);
43
44 it("returns its primal embedding", [&] {
45 AssertThat(&dual.getPrimalEmbedding(), Equals(&emb));
46 });
47
48 it("returns its primal graph", [&] {
49 AssertThat(&dual.getPrimalGraph(), Equals(&graph));
50 });
51
52 it("has a matching number of nodes, faces, and edges", [&] {
53 AssertThat(dual.numberOfFaces(), Equals(graph.numberOfNodes()));
54 AssertThat(dual.getGraph().numberOfNodes(), Equals(emb.numberOfFaces()));
55 AssertThat(dual.getGraph().numberOfEdges(), Equals(graph.numberOfEdges()));
56 });
57
58 it("maps primal faces to dual nodes", [&] {
59 for (face f : emb.faces) {
60 node v = dual.dualNode(f);
61 AssertThat(dual.primalFace(v), Equals(f));
62 AssertThat(v->degree(), Equals(f->size()));
63 }
64 });
65
66 it("maps primal nodes to dual faces", [&] {
67 for (node v: graph.nodes) {
68 face f = dual.dualFace(v);
69 AssertThat(dual.primalNode(f), Equals(v));
70 AssertThat(f->size(), Equals(v->degree()));
71 }
72 });
73
74 it("maps edges and faces", [&] {
75 for (edge e : graph.edges) {
76 edge g = dual.dualEdge(e);
77 AssertThat(g, !Equals(e));
78 AssertThat(dual.primalEdge(g), Equals(e));
79
80 face f = dual.primalFace(g->source());
81 AssertThat(f, Equals(emb.rightFace(e->adjSource())));
82 AssertThat(f, Equals(emb.leftFace(e->adjTarget())));
83
84 f = dual.primalFace(g->target());
85 AssertThat(f, Equals(emb.leftFace(e->adjSource())));
86 AssertThat(f, Equals(emb.rightFace(e->adjTarget())));
87 }
88 });
89}
90
91go_bandit([]() {
92 describe("DualGraph",[] {
93 for(int i = 1; i <= 100; i++) {
94 describe("iteration #" + to_string(i), []() {
95 performIteration(100, 200);
96 });
97 }
98 });
99});
100