Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PlanarSubgraphTriangles.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39
41
53template<typename TCost>
55public:
57
62
64 virtual PlanarSubgraphTriangles* clone() const override {
66 }
67
68protected:
69 virtual Module::ReturnType doCall(const Graph& graph, const List<edge>&, List<edge>& delEdges,
70 const EdgeArray<TCost>* pCost, bool preferredImplyPlanar = false) override {
73
74 delEdges.clear();
75 GraphCopy copy(graph);
76 List<edge> edges;
77 copy.allEdges(edges);
78 EdgeArray<bool> includeEdges(copy, false);
79
80 // sort weighted edges
81 if (pCost != nullptr) {
83 [&](edge e) { return (*pCost)[copy.original(e)]; });
85 [&](adjEntry a) { return (*pCost)[copy.original(a->theEdge())]; });
86 edges.quicksort(edgeCmp);
87
88 for (node v : copy.nodes) {
89 List<adjEntry> newOrder;
90 v->allAdjEntries(newOrder);
91 newOrder.quicksort(adjCmp);
92 copy.sort(v, newOrder);
93 }
94 }
95
97 NodeArray<int> set(copy);
98 for (node v : copy.nodes) {
99 set[v] = components.makeSet();
100 }
101
102 if (!m_onlyTriangles) {
103 // First step: Find as many diamonds as we can.
104 for (edge currentEdge : edges) {
105 // Skip if we already include this edge
107 continue;
108 }
109
110 // We assume this edge to be the cord of our diamond. This means we have to find two
111 // distinct triangles to make a diamond, and we will try to prefer ones with higher
112 // weights given by our pCost parameter
113
114 node source = currentEdge->source();
115 node target = currentEdge->target();
116
117 edge triangleEdge1 = nullptr, triangleEdge2 = nullptr;
118 node triangleNode = nullptr;
119 int triangleSet = -1;
120
121 findTriangle(copy, currentEdge, pCost, components, set, [&](node v, edge e1, edge e2) {
122 // Only use the found triangle if none of the nodes are in the same component.
123 // We know that each individually found triangle does not have two nodes in the
124 // same component, so we only have to check the opposite ones.
125 int potentialSet = components.find(set[v]);
126 if (potentialSet == triangleSet) {
127 return false; // This is not a triangle we can use, keep looking!
128 }
129
130 if (triangleNode == nullptr) {
131 // We don't have a triangle yet, mark this one down as the best we can find from this edge.
132 triangleNode = v;
136 return false; // continue searching for a second triangle to make our diamond
137 } else {
138 // We already found a triangle before, so this is the second-best triangle we can find,
139 // making a diamond.
142 true;
143
144 // Link up diamond nodes' components. These cannot be on the same connected subgraph yet.
145 int sourceSet = components.find(set[source]);
146 int targetSet = components.find(set[target]);
147 components.link(
150 return true; // stop looking
151 }
152 });
153 }
154 }
155
156 // Second step: Find as many triangles as we can.
157 for (edge currentEdge : edges) {
159 continue;
160 }
161
162 node source = currentEdge->source();
163 node target = currentEdge->target();
164
165 findTriangle(copy, currentEdge, pCost, components, set, [&](node v, edge e1, edge e2) {
167 int potentialSet = components.find(set[v]);
168 int sourceSet = components.find(set[source]);
169 int targetSet = components.find(set[target]);
171 return true;
172 });
173 }
174
175 // Third step: Link unconnected sub graphs
176 for (edge currentEdge : edges) {
177 node source = currentEdge->source();
178 node target = currentEdge->target();
179 int sourceSet = components.find(set[source]);
180 int targetSet = components.find(set[target]);
181 if (sourceSet != targetSet) {
184 }
185
187 delEdges.pushBack(copy.original(currentEdge));
188 }
189 }
190
192 }
193
194
195private:
197
199
208 while (connectionIterator != source->adjEntries.end()) {
209 if ((*connectionIterator)->twinNode() == target) {
210 return (*connectionIterator)->theEdge();
211 }
213 }
214 return nullptr;
215 }
216
218
236 std::function<bool(node, edge, edge)> callback) {
237 node source = currentEdge->source();
238 node target = currentEdge->target();
239 auto sourceIt = source->adjEntries.begin();
240 auto targetIt = target->adjEntries.begin();
241 int sourceSet = components.find(set[source]);
242 int targetSet = components.find(set[target]);
243 // Our nodes cannot be in the same set.
244 if (sourceSet == targetSet) {
245 return;
246 }
247
248 while (sourceIt != source->adjEntries.end() && targetIt != target->adjEntries.end()) {
249 if ((*sourceIt)->theEdge() == currentEdge) {
250 sourceIt++;
251 continue; // re-check loop condition
252 }
253 if ((*targetIt)->theEdge() == currentEdge) {
254 targetIt++;
255 continue; // re-check loop condition
256 }
257
258 // Look for a triangle, starting with the edge with next highest weight
259 // If no weights are given, it does not matter which edge we start with
263 if (pCost == nullptr
264 || (*pCost)[copy.original((*sourceIt)->theEdge())]
265 > (*pCost)[copy.original((*targetIt)->theEdge())]) {
267 potentialConnection = target;
269 sourceIt++;
270 } else {
272 potentialConnection = source;
274 targetIt++;
275 }
276 // Note: sourceIt and targetIt may be invalid until next loop
277
279 int potentialSet = components.find(set[potentialNode]);
280
281 // Only use this edge if it doesn't connect back to one of the components
285 if (potentialEdge != nullptr) {
286 // We found a triangle.
287 // If our callback returns true, it's signalling that we're done and don't
288 // want to look for another triangle.
289 // If it returns false, we continue looking.
291 return;
292 }
293 }
294 }
295 }
296 }
297};
298
299}
Implementation of disjoint sets data structures (union-find functionality).
Declaration of interface for planar subgraph algorithms.
Class for adjacency list elements.
Definition Graph_d.h:79
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition Graph_d.h:97
A Union/Find data structure for maintaining disjoint sets.
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
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
void sort(node v, const ADJ_ENTRY_LIST &newOrder)
Sorts the adjacency list of node v according to newOrder.
Definition Graph_d.h:1086
void allEdges(CONTAINER &edgeContainer) const
Returns a container with all edges of the graph.
Definition Graph_d.h:695
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
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
void quicksort()
Sorts the list using Quicksort.
Definition List.h:1315
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 approximation algorithms by Chalermsook/Schmid and Calinescu et al.
void findTriangle(GraphCopy &copy, edge currentEdge, const EdgeArray< TCost > *pCost, DisjointSets<> &components, NodeArray< int > &set, std::function< bool(node, edge, edge)> callback)
Finds all triangles from a given edge and calls a callback function on them.
edge searchEdge(node target, node source, internal::GraphIterator< adjEntry > connectionIterator)
Finds an edge, starting at a given iterator.
PlanarSubgraphTriangles(bool onlyTriangles=false)
Creates a planarization module based on triangle or diamond matching.
bool m_onlyTriangles
Whether we want to only check for triangles.
virtual PlanarSubgraphTriangles * clone() const override
Returns a new instance of the planarization module with the same settings.
virtual Module::ReturnType doCall(const Graph &graph, const List< edge > &, List< edge > &delEdges, const EdgeArray< TCost > *pCost, bool preferredImplyPlanar=false) override
Computes the set of edges delEdges which have to be deleted to obtain the planar subgraph.
bool isConnected(const Graph &G)
Returns true iff G is connected.
bool isSimpleUndirected(const Graph &G)
Returns true iff G contains neither self-loops nor undirected parallel edges.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Declaration of simple graph algorithms.
Compare elements based on a single comparable attribute.
Definition comparer.h:398