1#include <random>
2
3#include <ogdf/planarity/PlanarSubgraphBoyerMyrvold.h>
4#include <ogdf/planarity/PlanarSubgraphFast.h>
5#include <ogdf/planarity/MaximalPlanarSubgraphSimple.h>
6#include <ogdf/planarity/MaximumPlanarSubgraph.h>
7#include <ogdf/planarity/PlanarSubgraphCactus.h>
8#include <ogdf/planarity/PlanarSubgraphTree.h>
9
10#include <graphs.h>
11
12using std::minstd_rand;
13
14template <typename TCost>
15void testSubgraphInstance(Graph &graph, PlanarSubgraphModule<TCost> &psm, PlanarityModule &tester, bool assertMaximality, bool weighEdges, bool connects) {
16 makeSimpleUndirected(graph);
17 makeConnected(graph);
18
19 EdgeArray<TCost> costs;
20 edge mustHaveEdge = nullptr;
21
22 if(weighEdges) {
23 costs.init(graph);
24
25 for(edge e : graph.edges) {
26 costs[e] = TCost(1);
27 }
28
29 mustHaveEdge = graph.chooseEdge();
30 costs[mustHaveEdge] = TCost(1 + graph.numberOfEdges());
31 }
32
33 List<edge> removedEdges;
34 if(weighEdges) {
35 psm.call(graph, costs, removedEdges);
36 } else {
37 psm.call(graph, removedEdges);
38 }
39
40 std::cout << std::endl << " removed " << removedEdges.size() << " edges" << std::endl;
41 bool connected = isConnected(graph);
42
43 Graph::HiddenEdgeSet set(graph);
44 List<edge> hiddenEdges;
45 for(edge e : removedEdges) {
46 set.hide(e);
47 hiddenEdges.pushBack(e);
48 AssertThat(e, Is().Not().EqualTo(mustHaveEdge));
49 }
50
51 if(connects) {
52 AssertThat(isConnected(graph), Equals(connected));
53 }
54
55 AssertThat(tester.isPlanar(graph), Equals(true));
56
57 if(assertMaximality) {
58 ListConstIterator<edge> it = removedEdges.begin();
59 for(edge e : hiddenEdges) {
60 set.restore(e);
61 AssertThat(tester.isPlanar(graph), Equals(false));
62 set.hide(e);
63 it = it.succ();
64 }
65 }
66}
67
68void testSubgraphInstanceForIntAndDouble(Graph &graph, PlanarSubgraphModule<int> &psmi, PlanarSubgraphModule<double> &psmd) {
69 makeSimpleUndirected(graph);
70 makeConnected(graph);
71 EdgeArray<int> costsInt(graph);
72 EdgeArray<double> costsDouble(graph);
73 int cnt = 0;
74 for(edge e : graph.edges) {
75 cnt++;
76 costsInt(e) = cnt;
77 costsDouble(e) = double(cnt);
78 }
79 List<edge> removedEdgesInt;
80 List<edge> removedEdgesDouble;
81 psmi.call(graph, costsInt, removedEdgesInt);
82 psmd.call(graph, costsDouble, removedEdgesDouble);
83 int sumOfRemovedInt = 0;
84 double sumRemovedDouble = 0;
85 for (edge e: removedEdgesInt) { sumOfRemovedInt += costsInt(e); }
86 for (edge e: removedEdgesDouble) { sumRemovedDouble += costsDouble(e); }
87 AssertThat( sumOfRemovedInt, Equals(int(sumRemovedDouble)) );
88}
89
90void performGenericTests(const string &name, bool optimal, bool respectsEdgeWeight, bool skip, std::function<void(Graph &, bool)> callFunc) {
91 describe(name, [&]() {
92 auto doTest = [&](bool weighted) {
93 forEachGraphItWorks({GraphProperty::sparse}, [&](Graph G) { callFunc(G, weighted); }, optimal ? GraphSizes(10) : GraphSizes());
94 };
95
96 doTest(false);
97
98 if(respectsEdgeWeight) {
99 describe("weighted", [&] { doTest(true); });
100 }
101 }, skip);
102}
103
104template <typename TCost>
105void testSubgraphAlgorithm(const string &name, PlanarSubgraphModule<TCost> &psm, bool optimal, bool maximal, bool respectsEdgeWeight, bool connects, bool skip = false) {
106 maximal |= optimal;
107 BoothLueker bl;
108 performGenericTests(name, optimal, respectsEdgeWeight, skip, [&](Graph &graph, bool weighEdges) {
109 testSubgraphInstance<TCost>(graph, psm, bl, maximal, weighEdges, connects);
110 });
111}
112
113void testSubgraphAlgorithmForIntAndDouble(const string &name, PlanarSubgraphModule<int> &psmi, PlanarSubgraphModule<double> &psmd) {
114 performGenericTests(name + " int VS double", false, true, false, [&](Graph &graph, bool weighEdges) {
115 testSubgraphInstanceForIntAndDouble(graph, psmi, psmd);
116 });
117}
118
119template<template<typename> class Algorithm>
120void describeAlgorithm(const string &name, bool optimal, bool maximal, bool respectsEdgeWeight, bool connects, bool skip = false) {
121 Algorithm<int> algoInt;
122 testSubgraphAlgorithm(name + "<int>", algoInt, optimal, maximal, respectsEdgeWeight, connects, skip);
123
124 Algorithm<double> algoDouble;
125 testSubgraphAlgorithm(name + "<double>", algoDouble, optimal, maximal, respectsEdgeWeight, connects, skip);
126}
127
128go_bandit([]() {
129 describe("Planar Subgraphs", []() {
130 PlanarSubgraphBoyerMyrvold bms;
131 MaximumPlanarSubgraph mps;
132
133 testSubgraphAlgorithm("PlanarSubgraphBoyerMyrvold", bms, false, false, true, true, true);
134 describeAlgorithm<PlanarSubgraphFast>("PlanarSubgraphFast", false, false, false, true);
135 describeAlgorithm<PlanarSubgraphCactus>("PlanarSubgraphCactus", false, false, false, true);
136 describeAlgorithm<PlanarSubgraphTree>("PlanarSubgraphTree", false, false, false, true);
137 testSubgraphAlgorithm("MaximumPlanarSubgraph", mps, true, true, true, true);
138 describeAlgorithm<PlanarSubgraphEmpty>("PlanarSubgraphEmpty", false, false, false, false);
139
140 MaximalPlanarSubgraphSimple<int> mpss;
141 PlanarSubgraphCactus<int> psc;
142 MaximalPlanarSubgraphSimple<int> mpssPsc(psc);
143 PlanarSubgraphFast<int> fps;
144 MaximalPlanarSubgraphSimple<int> mpssFps(fps);
145 MaximalPlanarSubgraphSimple<int> mpssBms(bms);
146
147 testSubgraphAlgorithm("MaximalPlanarSubgraphSimple", mpss, false, true, false, true);
148 testSubgraphAlgorithm("Maximal PlanarSubgraphCactus", mpssPsc, false, true, false, true);
149 testSubgraphAlgorithm("Maximal PlanarSubgraphFast", mpssFps, false, true, false, true);
150 testSubgraphAlgorithm("Maximal PlanarSubgraphBoyerMyrvold", mpssBms, false, true, false, true, true);
151
152 PlanarSubgraphCactus<double> pscd;
153 MaximalPlanarSubgraphSimple<double> mpssPscd(pscd);
154 testSubgraphAlgorithmForIntAndDouble("Maximal PlanarSubgraphCactus", mpssPsc, mpssPscd);
155 });
156});
157