Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
MultiEdgeApproxInserter.h
Go to the documentation of this file.
1
32#pragma once
33
38
39namespace ogdf {
40
42
51public:
54
57
60
62 virtual EdgeInsertionModule* clone() const override;
63
66
69
71 RemoveReinsertType removeReinsertFix() const { return m_rrOptionFix; }
72
75
77 RemoveReinsertType removeReinsertVar() const { return m_rrOptionVar; }
78
80
84 void percentMostCrossedFix(double percent) { m_percentMostCrossedFix = percent; }
85
87 double percentMostCrossedFix() const { return m_percentMostCrossedFix; }
88
90
94 void percentMostCrossedVar(double percent) { m_percentMostCrossedVar = percent; }
95
97 double percentMostCrossedVar() const { return m_percentMostCrossedVar; }
98
99 void statistics(bool b) { m_statistics = b; }
100
101 bool statistics() const { return m_statistics; }
102
103 int sumInsertionCosts() const { return m_sumInsertionCosts; }
104
105 int sumFEInsertionCosts() const { return m_sumFEInsertionCosts; }
106
107private:
108 enum class PathDir { Left, Right, None };
109
111 static inline PathDir oppDir(PathDir dir) {
112 switch (dir) {
113 case PathDir::Left:
114 return PathDir::Right;
115 case PathDir::Right:
116 return PathDir::Left;
117 default:
118 return PathDir::None;
119 }
120 };
121
123 class Block;
124
127
128 struct VertexBlock {
129 VertexBlock(node v, int b) : m_vertex(v), m_block(b) { }
130
133 };
134
137 const EdgeArray<bool>* forbiddenEdge, const EdgeArray<uint32_t>* edgeSubGraphs) override;
138
139 MultiEdgeApproxInserter::Block* constructBlock(int i);
141
142 static bool dfsPathSPQR(node v, node v2, edge eParent, List<edge>& path);
143 int computePathSPQR(int b, node v, node w, int k);
144
145 bool dfsPathVertex(node v, int parent, int k, node t);
146 bool dfsPathBlock(int b, node parent, int k, node t);
147 void computePathBC(int k);
148
149 void embedBlock(int b, int m);
151 const NodeArray<bool>& visited, StaticPlanarSPQRTree& spqr);
152
153 void cleanup();
154
159 bool m_statistics; // !< Generates further statistic information.
160
161 PlanRepLight* m_pPG; // pointer to plan-rep passed in call
163
164 NodeArray<SList<int>> m_compV; // m_compV[v] = list of blocks containing v
165 Array<SList<node>> m_verticesB; // m_verticesB[i] = list of vertices in block i
166 Array<SList<edge>> m_edgesB; // edgesB[i] = list of edges in block i
167 NodeArray<node> m_GtoBC; // temporary mapping of nodes in PG to copies in block
168 NodeArray<SList<VertexBlock>> m_copyInBlocks; // mapping of nodes in PG to copies in block
169
170 const Array<edge>* m_edge; // pointer to array of edges to be inserted
171 Array<List<VertexBlock>> m_pathBCs; // insertion path in BC-tree for each edge
172 Array<int> m_insertionCosts; // computed insertion costs for each edge
173 Array<Block*> m_block; // array of blocks
174
175 // statistics of last run
178
179 // just for testing
182
187 node m_vS, m_vT;
188};
189
190}
Declaration of interface for edge insertion algorithms.
declaration and implementation of FaceArray class
Definition of RemoveReinsertType (used for postprocessing in edge insertion algorithms).
Declaration of class StaticPlanarSPQRTree.
Class for adjacency list elements.
Definition Graph_d.h:79
Dynamic arrays indexed with adjacency entries.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
Class representing idea of Blocks used in GlobalSifting and GridSifting algorithms.
Definition BlockOrder.h:70
Combinatorial embeddings of planar graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Interface for edge insertion algorithms.
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition FaceArray.h:126
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
ReturnType
The return type of a module.
Definition Module.h:50
Multi edge inserter with approximation guarantee.
virtual EdgeInsertionModule * clone() const override
Returns a new instance of the multi-edge approx inserter with the same option settings.
RemoveReinsertType removeReinsertFix() const
Returns the current setting of the remove-reinsert postprocessing method.
double percentMostCrossedVar() const
Returns the current setting of option percentMostCrossed (variable embedding).
Array< List< VertexBlock > > m_pathBCs
NodeArray< SList< VertexBlock > > m_copyInBlocks
static PathDir oppDir(PathDir dir)
Returns the opposite direction of dir.
RemoveReinsertType m_rrOptionFix
The remove-reinsert method for fixed embedding.
void removeReinsertVar(RemoveReinsertType rrOption)
Sets the remove-reinsert postprocessing method.
double m_percentMostCrossedFix
The portion of most crossed edges considered (fixed embedding).
bool dfsPathVertex(node v, int parent, int k, node t)
ReturnType doCall(PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > *costOrig, const EdgeArray< bool > *forbiddenEdge, const EdgeArray< uint32_t > *edgeSubGraphs) override
Implements the algorithm call.
double percentMostCrossedFix() const
Returns the current setting of option percentMostCrossed.
bool dfsPathBlock(int b, node parent, int k, node t)
int computePathSPQR(int b, node v, node w, int k)
int findShortestPath(node s, node t)
AdjEntryArray< adjEntry > m_primalAdj
MultiEdgeApproxInserter::Block * constructBlock(int i)
node copy(node vOrig, int b)
void embedBlock(int b, int m)
void recFlipPref(adjEntry adjP, NodeArray< EmbeddingPreference > &pi_pick, const NodeArray< bool > &visited, StaticPlanarSPQRTree &spqr)
ConstCombinatorialEmbedding m_E
void constructDual(const PlanRepLight &pr)
RemoveReinsertType m_rrOptionVar
The remove-reinsert method for variable embedding.
void removeReinsertFix(RemoveReinsertType rrOption)
Sets the remove-reinsert postprocessing method.
RemoveReinsertType removeReinsertVar() const
Returns the current setting of the remove-reinsert postprocessing method.
static bool dfsPathSPQR(node v, node v2, edge eParent, List< edge > &path)
MultiEdgeApproxInserter(const MultiEdgeApproxInserter &inserter)
Creates an instance of multi-edge approx inserter with the same settings as inserter.
void percentMostCrossedFix(double percent)
Sets the option percentMostCrossed to percent.
MultiEdgeApproxInserter()
Creates an instance of multi-edge approx inserter with default option settings.
double m_percentMostCrossedVar
The portion of most crossed edges considered (variable embedding).
void percentMostCrossedVar(double percent)
Sets the option percentMostCrossedVar to percent.
MultiEdgeApproxInserter & operator=(const MultiEdgeApproxInserter &inserter)
Assignment operator. Copies option settings only.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Light-weight version of a planarized representation, associated with a PlanRep.
SPQR-trees of planar graphs.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
RemoveReinsertType
The postprocessing method for edge insertion algorithms.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
@ None
Two geometric objects do not intersect.