Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PlanarSubgraphTree.h
Go to the documentation of this file.
1
32#pragma once
33
35#include <ogdf/basic/Math.h>
39
40namespace ogdf {
41
44template<typename TCost>
46public:
47 virtual PlanarSubgraphTree* clone() const override { return new PlanarSubgraphTree(); }
48
49protected:
51 List<edge>& delEdges, const EdgeArray<TCost>* pCost, bool preferedImplyPlanar) override {
52 delEdges.clear();
53
54 if (pCost) {
55 GraphCopy copy(graph);
56 EdgeArray<TCost> weight(copy);
57 TCost maxCost = std::numeric_limits<TCost>::min();
58
59 for (edge e : graph.edges) {
61 }
62
63 for (edge e : copy.edges) {
64 weight[e] = maxCost - (*pCost)[copy.original(e)];
65 }
66
67 makeMinimumSpanningTree(copy, weight);
68
69 for (edge e : graph.edges) {
70 if (copy.copy(e) == nullptr) {
71 delEdges.pushBack(e);
72 }
73 }
74 } else if (!graph.empty()) {
75 // Will contain the parent of each node in the computed forest.
76 // parent[v] == v iff v is a root node.
77 // parent[v] == nullptr iff v wasn't visited yet.
78 NodeArray<node> parent(graph, nullptr);
79 ArrayBuffer<node> nodes(graph.numberOfNodes());
80
81 for (node v : graph.nodes) {
82 if (parent[v] == nullptr) {
83 parent[v] = v;
84 nodes.push(v);
85
86 while (!nodes.empty()) {
87 node u = nodes.popRet();
88
89 for (adjEntry adj : u->adjEntries) {
90 node w = adj->twinNode();
91
92 if (parent[w] == nullptr) {
93 parent[w] = u;
94 nodes.push(w);
95 }
96 }
97 }
98 }
99 }
100
101 for (edge e : graph.edges) {
102 node v = e->source();
103 node w = e->target();
104
105 bool vIsParent = v == parent[w];
106 bool wIsParent = w == parent[v];
107
108 // Delete edges that are not in the tree.
109 // In particular, do not pick parallel edges or self-loops.
110 if (e->isSelfLoop() || (!vIsParent && !wIsParent)) {
111 delEdges.pushBack(e);
112 } else if (vIsParent) {
113 parent[w] = nullptr;
114 } else if (wIsParent) {
115 parent[v] = nullptr;
116 }
117 }
118 }
119
120#ifdef OGDF_DEBUG
121 NodeArray<int> tmp(graph);
123 int numberOfEdgesInForest = graph.numberOfEdges() - delEdges.size();
124 // Euler characteristic for forests
126#endif
127
129 }
130};
131
132}
Implementation of disjoint sets data structures (union-find functionality).
Declaration of interface for planar subgraph algorithms.
Mathematical Helpers.
Class for adjacency list elements.
Definition Graph_d.h:79
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
E popRet()
Removes the newest element from the buffer and returns it.
void push(E e)
Puts a new element in the buffer.
bool empty() const
Returns true if the buffer is empty, false otherwise.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition GraphCopy.h:338
const Graph & original() const
Returns a reference to the original graph.
Definition GraphCopy.h:289
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition Graph_d.h:622
int numberOfEdges() const
Returns the number of edges in the graph.
Definition Graph_d.h:625
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
bool empty() const
Returns true iff the graph is empty, i.e., contains no nodes.
Definition Graph_d.h:619
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
int size() const
Returns the number of elements in the list.
Definition List.h:1472
void clear()
Removes all elements from the list.
Definition List.h:1610
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition List.h:1531
ReturnType
The return type of a module.
Definition Module.h:50
@ Feasible
The solution is feasible.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Interface for planar subgraph algorithms.
Maximum planar subgraph heuristic that yields a spanning tree.
virtual PlanarSubgraphTree * clone() const override
Returns a new instance of the planar subgraph module with the same option settings.
virtual Module::ReturnType doCall(const Graph &graph, const List< edge > &preferredEdges, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferedImplyPlanar) override
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
Declaration of extended graph algorithms.
int connectedComponents(const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
Computes the connected components of G and optionally generates a list of isolated nodes.
T makeMinimumSpanningTree(Graph &G, const EdgeArray< T > &weight)
Reduce a graph to its minimum spanning tree (MST) using Kruskal's algorithm.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
void updateMax(T &max, const T &newValue)
Stores the maximum of max and newValue in max.
Definition Math.h:90
The namespace for all OGDF objects.
Declaration of simple graph algorithms.