# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
CrossingMinimizationModule.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Module.h>
37
38namespace ogdf {
39
42public:
45
48
51
53 virtual CrossingMinimizationModule* clone() const = 0;
54
56
71 const EdgeArray<int>* pCostOrig = nullptr,
72 const EdgeArray<bool>* pForbiddenOrig = nullptr,
73 const EdgeArray<uint32_t>* pEdgeSubGraphs = nullptr) {
75 }
76
78
93 const EdgeArray<int>* pCostOrig = nullptr,
94 const EdgeArray<bool>* pForbiddenOrig = nullptr,
95 const EdgeArray<uint32_t>* pEdgeSubGraphs = nullptr) {
97 }
98
99protected:
101
117 int& crossingNumber) = 0;
118
131 if (pCost == nullptr) {
132 return graphCopy.numberOfNodes() - graphCopy.original().numberOfNodes();
133 } else {
134 int crossingNumber = 0;
135 for (node v : graphCopy.nodes) {
136 if (graphCopy.isDummy(v)) {
137 // Dummy node (crossing) found, calculate its cost.
140 if (pEdgeSubGraphs != nullptr) {
141 int subgraphCounter = 0;
142 for (int i = 0; i < 32; i++) {
143 if (((*pEdgeSubGraphs)[e1] & (1 << i)) != 0
144 && ((*pEdgeSubGraphs)[e2] & (1 << i)) != 0) {
146 }
147 }
148 crossingNumber += (subgraphCounter * (*pCost)[e1] * (*pCost)[e2]);
149 } else {
150 crossingNumber += (*pCost)[e1] * (*pCost)[e2];
151 }
152 }
153 }
154 return crossingNumber;
155 }
156 }
157
159};
160
161}
Declares base class for all module types.
Declaration of a base class for planar representations of graphs and cluster graphs.
Declares base class for modules with timeout functionality.
Base class for crossing minimization algorithms.
static int computeCrossingNumber(GraphCopy &graphCopy, const EdgeArray< int > *pCost, const EdgeArray< uint32_t > *pEdgeSubGraphs)
Computes the (weighted) crossing number of the planarization graphCopy.
CrossingMinimizationModule()
Initializes a crossing minimization module (default constructor).
ReturnType call(PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
Computes a planarized representation of the input graph.
ReturnType operator()(PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr)
Computes a planarized representation of the input graph.
virtual ReturnType doCall(PlanRep &pr, int cc, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs, int &crossingNumber)=0
Actual algorithm call that needs to be implemented by derived classes.
virtual CrossingMinimizationModule * clone() const =0
Returns a new instance of the crossing minimization module with the same option settings.
CrossingMinimizationModule(const CrossingMinimizationModule &cmm)
Initializes an crossing minimization module (copy constructor).
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
Base class for modules.
Definition Module.h:47
ReturnType
The return type of a module.
Definition Module.h:50
Class for the representation of nodes.
Definition Graph_d.h:177
Planarized representations (of a connected component) of a graph.
Definition PlanRep.h:57
class for timeout funtionality.
Definition Timeouter.h:46
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_MALLOC_NEW_DELETE
Makes the class use malloc for memory allocation.
Definition memory.h:91