Loading [MathJax]/extensions/tex2jax.js

Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Loading...
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.
138 edge e1 = graphCopy.original(v->firstAdj()->theEdge());
139 edge e2 = graphCopy.original(v->lastAdj()->theEdge());
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
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.