1/** \file
2 * \brief Declaration of class PlanarSubgraphTree.
3 *
4 * \author 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#pragma once
33
34#include <ogdf/module/PlanarSubgraphModule.h>
35#include <ogdf/basic/simple_graph_alg.h>
36#include <ogdf/basic/DisjointSets.h>
37#include <ogdf/basic/extended_graph_alg.h>
38#include <ogdf/basic/Math.h>
39
40namespace ogdf {
41
42//! Maximum planar subgraph heuristic that yields a spanning tree.
43//! @ingroup ga-plansub
44template<typename TCost>
45class PlanarSubgraphTree : public PlanarSubgraphModule<TCost>
46{
47public:
48 virtual PlanarSubgraphTree *clone() const override {
49 return new PlanarSubgraphTree();
50 }
51
52protected:
53 virtual Module::ReturnType doCall(
54 const Graph &graph,
55 const List<edge> &preferredEdges,
56 List<edge> &delEdges,
57 const EdgeArray<TCost> *pCost,
58 bool preferedImplyPlanar) override {
59 delEdges.clear();
60
61 if (pCost) {
62 GraphCopy copy(graph);
63 EdgeArray<TCost> weight(copy);
64 TCost maxCost = std::numeric_limits<TCost>::min();
65
66 for (edge e : graph.edges) {
67 Math::updateMax(maxCost, (*pCost)[e]);
68 }
69
70 for (edge e : copy.edges) {
71 weight[e] = maxCost - (*pCost)[copy.original(e)];
72 }
73
74 makeMinimumSpanningTree(copy, weight);
75
76 for (edge e : graph.edges) {
77 if (copy.copy(e) == nullptr) {
78 delEdges.pushBack(e);
79 }
80 }
81 } else if (!graph.empty()) {
82 // Will contain the parent of each node in the computed forest.
83 // parent[v] == v iff v is a root node.
84 // parent[v] == nullptr iff v wasn't visited yet.
85 NodeArray<node> parent(graph, nullptr);
86 ArrayBuffer<node> nodes(graph.numberOfNodes());
87
88 for (node v : graph.nodes) {
89 if (parent[v] == nullptr) {
90 parent[v] = v;
91 nodes.push(v);
92
93 while (!nodes.empty()) {
94 node u = nodes.popRet();
95
96 for (adjEntry adj : u->adjEntries) {
97 node w = adj->twinNode();
98
99 if (parent[w] == nullptr) {
100 parent[w] = u;
101 nodes.push(w);
102 }
103 }
104 }
105 }
106 }
107
108 for (edge e : graph.edges) {
109 node v = e->source();
110 node w = e->target();
111
112 bool vIsParent = v == parent[w];
113 bool wIsParent = w == parent[v];
114
115 // Delete edges that are not in the tree.
116 // In particular, do not pick parallel edges or self-loops.
117 if (e->isSelfLoop() || (!vIsParent && !wIsParent)) {
118 delEdges.pushBack(e);
119 } else if (vIsParent) {
120 parent[w] = nullptr;
121 } else if (wIsParent) {
122 parent[v] = nullptr;
123 }
124 }
125 }
126
127#ifdef OGDF_DEBUG
128 NodeArray<int> tmp(graph);
129 int numberOfComponents = connectedComponents(graph, tmp);
130 int numberOfEdgesInForest = graph.numberOfEdges() - delEdges.size();
131 // Euler characteristic for forests
132 OGDF_ASSERT(numberOfEdgesInForest == graph.numberOfNodes() - numberOfComponents);
133#endif
134
135 return Module::ReturnType::Feasible;
136 }
137};
138
139}
140