Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

NodeRespecterLayout.h
Go to the documentation of this file.
1 
36 #pragma once
37 
39 #include <ogdf/basic/GraphCopy.h>
40 
41 namespace ogdf {
42 
44 
86 {
87 
88 public:
91 
94 
96  virtual void call(GraphAttributes &attr) override;
97 
100  enum class PostProcessingMode {
101  None,
102  KeepMultiEdgeBends,
103  Complete
106  };
108 
111 
113  void setRandomInitialPlacement(bool randomInitialPlacement);
114 
116  void setPostProcessing(PostProcessingMode postProcessing);
117 
119  void setBendNormalizationAngle(double bendNormalizationAngle);
120 
122  void setNumberOfIterations(int numberOfIterations);
123 
125  void setMinimalTemperature(double minimalTemperature);
126 
129  void setInitialTemperature(double initialTemperature);
130 
133  void setTemperatureDecreaseOffset(double temperatureDecreaseOffset);
134 
136  void setGravitation(double gravitation);
137 
139  void setOscillationAngle(double oscillationAngle);
140 
142  void setDesiredMinEdgeLength(double desiredMinEdgeLength);
143 
145  void setInitDummiesPerEdge(int initDummiesPerEdge);
146 
149  void setMaxDummiesPerEdge(int maxDummiesPerEdge);
150 
152  void setDummyInsertionThreshold(double dummyInsertionThreshold);
153 
155  void setMaxDisturbance(double maxDisturbance);
156 
158  void setRepulsionDistance(double repulsionDistance);
159 
161  void setMinDistCC(double minDistCC);
162 
164  void setPageRatio(double pageRatio);
165 
169 
171  bool getRandomInitialPlacement() const { return m_randomInitialPlacement; }
172 
174  PostProcessingMode getPostProcessing() const { return m_postProcessing; }
175 
177  double getBendNormalizationAngle() const { return m_bendNormalizationAngle; }
178 
180  int getNumberOfIterations() const { return m_numberOfIterations; }
181 
183  double getMinimalTemperature() const { return m_minimalTemperature; }
184 
186  double getInitialTemperature() const { return m_initialTemperature; }
187 
189  double getTemperatureDecreaseOffset() const { return m_temperatureDecreaseOffset; }
190 
192  double getGravitation() const { return m_gravitation; }
193 
195  double getOscillationAngle() const { return m_oscillationAngle; }
196 
198  double getDesiredMinEdgeLength() const { return m_desiredMinEdgeLength; }
199 
201  int getInitDummiesPerEdge() const { return m_initDummiesPerEdge; }
202 
204  int getMaxDummiesPerEdge() const { return m_maxDummiesPerEdge; }
205 
207  double getDummyInsertionThreshold() const { return m_dummyInsertionThreshold; }
208 
210  double getMaxDisturbance() const { return m_maxDisturbance; }
211 
213  double getRepulsionDistance() const { return m_repulsionDistance; }
214 
216  double getMinDistCC() const { return m_minDistCC; }
217 
219  double getPageRatio() const { return m_pageRatio; }
220 
222 
223 private:
226 
229 
232 
236 
239 
242 
245 
250 
253 
257 
260 
263 
266 
270 
273 
277 
279  double m_minDistCC;
280 
282  double m_pageRatio;
283 
287 
290 
293 
296 
299 
302 
305 
308 
311 
315 
318 
321 
324 
327 
330 
332  double m_factor;
333 
335  double m_cos;
336 
338 
340  void initData();
341 
343  void freeData();
344 
346  void createBends(const ArrayBuffer<edge> &origEdges, GraphAttributes &attr);
347 
351  void updateNodeLoop(SListPure<node> &nodes);
352 
354  std::pair<double,double> computeImpulse(node v);
355 
358  void updateNode(node v, std::pair<double,double> newImpulse);
359 
361  void addDummies(node v, SListPure<node> &nodes);
362 
365  inline double radius(const GraphAttributes &attr, node v) const {
366  switch (attr.shape(v)) {
367  case Shape::Pentagon:
368  case Shape::Octagon:
369  case Shape::Hexagon:
370  case Shape::Rhomb:
371  case Shape::Ellipse:
372  return std::max(attr.height(v), attr.width(v)) / 2.0;
373 
374  default:
375  // For Rect, RoundedRect, Triangle, Trapeze, Parallelogram, InvTriangle,
376  // InvTrapeze, InvParallelogram, Image and unknown shapes.
377  return std::hypot(attr.height(v), attr.width(v)) / 2.0;
378  }
379  }
380 
385  inline bool haveSameOriginalEdge(node v, node w) const {
386  if (m_copy.isDummy(v) && m_copy.isDummy(w)) {
387  return m_copy.original(v->firstAdj()->theEdge()) ==
388  m_copy.original(w->firstAdj()->theEdge());
389  } else if (m_copy.isDummy(v)) {
390  return m_copy.original(v->firstAdj()->theEdge())->isIncident(w);
391  } else if (m_copy.isDummy(w)) {
392  return m_copy.original(w->firstAdj()->theEdge())->isIncident(v);
393  } else {
394  return false;
395  }
396  }
397 
399  inline double weight(node v) const {
400  return v->degree() / m_degreeSum;
401  }
402 
404 };
405 
406 }
ogdf::ArrayBuffer< edge >
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
ogdf::NodeRespecterLayout::m_impulseY
NodeArray< double > m_impulseY
Y-coordinate of the last impulse of the node.
Definition: NodeRespecterLayout.h:298
ogdf::NodeRespecterLayout::m_localTemperature
NodeArray< double > m_localTemperature
Local temperature of the node.
Definition: NodeRespecterLayout.h:301
ogdf::NodeRespecterLayout::getPageRatio
double getPageRatio() const
Returns m_pageRatio.
Definition: NodeRespecterLayout.h:219
ogdf::NodeRespecterLayout::m_pageRatio
double m_pageRatio
Page ratio used for the layout of connected components.
Definition: NodeRespecterLayout.h:282
ogdf::NodeRespecterLayout::m_initDummiesPerEdge
int m_initDummiesPerEdge
How many dummy nodes should initially be created for one edge.
Definition: NodeRespecterLayout.h:262
ogdf::NodeRespecterLayout::getRepulsionDistance
double getRepulsionDistance() const
Returns m_repulsionDistance.
Definition: NodeRespecterLayout.h:213
ogdf::NodeRespecterLayout
The NodeRespecterLayout layout algorithm.
Definition: NodeRespecterLayout.h:85
ogdf::GraphCopy::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:292
ogdf::NodeRespecterLayout::getMaxDisturbance
double getMaxDisturbance() const
Returns m_maxDisturbance.
Definition: NodeRespecterLayout.h:210
ogdf::NodeRespecterLayout::m_barycenterX
double m_barycenterX
Weighted sum of x-coordinates of all nodes.
Definition: NodeRespecterLayout.h:320
ogdf::NodeRespecterLayout::m_temperatureDecreaseOffset
double m_temperatureDecreaseOffset
Factor for which holds: If only m_numberOfIterations * m_temperatureDecreaseOffset iterations are lef...
Definition: NodeRespecterLayout.h:249
ogdf::NodeRespecterLayout::~NodeRespecterLayout
~NodeRespecterLayout()
Destroys an instance of the NodeRespecterLayout.
Definition: NodeRespecterLayout.h:93
ogdf::NodeRespecterLayout::m_degreeSum
int m_degreeSum
Twice the number of all edges in the original graph.
Definition: NodeRespecterLayout.h:317
ogdf::NodeRespecterLayout::m_randomInitialPlacement
bool m_randomInitialPlacement
Whether nodes should be initialized in random positions.
Definition: NodeRespecterLayout.h:228
ogdf::NodeRespecterLayout::getMinDistCC
double getMinDistCC() const
Returns m_minDistCC.
Definition: NodeRespecterLayout.h:216
ogdf::Shape::Octagon
@ Octagon
octagon
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::NodeRespecterLayout::haveSameOriginalEdge
bool haveSameOriginalEdge(node v, node w) const
Returns whether v and w belong to the same original edge. If only one of the nodes is a dummy node,...
Definition: NodeRespecterLayout.h:385
ogdf::NodeRespecterLayout::m_bendNormalizationAngle
double m_bendNormalizationAngle
Lower bound for the minimum angle between two line segments such that the bend point between them is ...
Definition: NodeRespecterLayout.h:235
LayoutModule.h
Declaration of interface for layout algorithms (class LayoutModule)
ogdf::NodeRespecterLayout::m_repulsionDistance
double m_repulsionDistance
Maximum distance between a dummy and another node such that the former is repulsed by the latter.
Definition: NodeRespecterLayout.h:276
ogdf::NodeRespecterLayout::m_dummyInsertionThreshold
double m_dummyInsertionThreshold
How many times larger than the desired edge length an edge has to be in order for a new dummy node to...
Definition: NodeRespecterLayout.h:269
ogdf::GraphCopy::isDummy
bool isDummy(node v) const
Returns true iff v has no corresponding node in the original graph.
Definition: GraphCopy.h:383
ogdf::Shape::Rhomb
@ Rhomb
rhomb (=diamond)
ogdf::NodeRespecterLayout::m_numberOfIterations
int m_numberOfIterations
Number of times a single node is moved for each connected component.
Definition: NodeRespecterLayout.h:238
ogdf::NodeRespecterLayout::PostProcessingMode
PostProcessingMode
Sets whether unnecessary edge bends should be filtered out in a post-processing step.
Definition: NodeRespecterLayout.h:100
ogdf::NodeRespecterLayout::m_cos
double m_cos
Precomputed cosinus of (m_oscillationAngle / 2).
Definition: NodeRespecterLayout.h:335
ogdf::NodeArray< double >
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::NodeRespecterLayout::getMaxDummiesPerEdge
int getMaxDummiesPerEdge() const
Returns m_maxDummiesPerEdge.
Definition: NodeRespecterLayout.h:204
ogdf::EdgeArray< bool >
ogdf::NodeRespecterLayout::getBendNormalizationAngle
double getBendNormalizationAngle() const
Returns m_bendNormalizationAngle.
Definition: NodeRespecterLayout.h:177
ogdf::NodeRespecterLayout::m_hasParEdges
EdgeArray< bool > m_hasParEdges
Whether the edge has parallel edges.
Definition: NodeRespecterLayout.h:307
ogdf::NodeRespecterLayout::getDesiredMinEdgeLength
double getDesiredMinEdgeLength() const
Returns m_desiredMinEdgeLength.
Definition: NodeRespecterLayout.h:198
ogdf::NodeRespecterLayout::m_desiredMinEdgeLength
double m_desiredMinEdgeLength
Desired minimal node separation/edge length.
Definition: NodeRespecterLayout.h:259
ogdf::NodeRespecterLayout::m_minimalTemperature
double m_minimalTemperature
Minimal temperature, lower bound for the global temperature.
Definition: NodeRespecterLayout.h:241
ogdf::GraphAttributes::shape
Shape shape(node v) const
Returns the shape type of node v.
Definition: GraphAttributes.h:456
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::NodeRespecterLayout::m_maxDisturbance
double m_maxDisturbance
Maximal disturbance, i.e. maximal random node movement.
Definition: NodeRespecterLayout.h:272
ogdf::NodeRespecterLayout::m_gravitation
double m_gravitation
Gravitational constant scaling attractive forces towards the barycenter.
Definition: NodeRespecterLayout.h:252
ogdf::NodeRespecterLayout::weight
double weight(node v) const
Returns the weight of node v according to its degree.
Definition: NodeRespecterLayout.h:399
ogdf::NodeRespecterLayout::getMinimalTemperature
double getMinimalTemperature() const
Returns m_minimalTemperature.
Definition: NodeRespecterLayout.h:183
ogdf::NodeRespecterLayout::m_copy
GraphCopy m_copy
Copy of the given graph which may contain dummy nodes.
Definition: NodeRespecterLayout.h:289
ogdf::NodeRespecterLayout::m_minDistCC
double m_minDistCC
Minimal distance between connected components.
Definition: NodeRespecterLayout.h:279
ogdf::NodeRespecterLayout::m_nodeRadius
NodeArray< double > m_nodeRadius
Radius of the smallest circle encompassing the node.
Definition: NodeRespecterLayout.h:304
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::NodeRespecterLayout::getPostProcessing
PostProcessingMode getPostProcessing() const
Returns m_postProcessing.
Definition: NodeRespecterLayout.h:174
GraphCopy.h
Declaration of graph copy classes.
ogdf::Shape::Pentagon
@ Pentagon
pentagon
ogdf::GraphAttributes::height
double height(node v) const
Returns the height of the bounding box of node v.
Definition: GraphAttributes.h:418
ogdf::NodeRespecterLayout::getGravitation
double getGravitation() const
Returns m_gravitation.
Definition: NodeRespecterLayout.h:192
ogdf::Shape::Ellipse
@ Ellipse
ellipse
ogdf::NodeRespecterLayout::m_desiredDistance
NodeArray< NodeArray< double > > m_desiredDistance
Desired distance between each pair of nodes.
Definition: NodeRespecterLayout.h:310
ogdf::NodeRespecterLayout::getTemperatureDecreaseOffset
double getTemperatureDecreaseOffset() const
Returns m_temperatureDecreaseOffset.
Definition: NodeRespecterLayout.h:189
ogdf::NodeRespecterLayout::getInitDummiesPerEdge
int getInitDummiesPerEdge() const
Returns m_initDummiesPerEdge.
Definition: NodeRespecterLayout.h:201
ogdf::NodeRespecterLayout::m_impulseX
NodeArray< double > m_impulseX
X-coordinate of the last impulse of the node.
Definition: NodeRespecterLayout.h:295
ogdf::NodeRespecterLayout::getDummyInsertionThreshold
double getDummyInsertionThreshold() const
Returns m_dummyInsertionThreshold.
Definition: NodeRespecterLayout.h:207
ogdf::NodeRespecterLayout::getOscillationAngle
double getOscillationAngle() const
Returns m_oscillationAngle.
Definition: NodeRespecterLayout.h:195
ogdf::NodeRespecterLayout::m_iterCounter
int m_iterCounter
Number of iterations for which the algorithm still has to run.
Definition: NodeRespecterLayout.h:326
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::NodeRespecterLayout::radius
double radius(const GraphAttributes &attr, node v) const
Returns the radius of the smallest circle surrounding the shape of v (while still having its center a...
Definition: NodeRespecterLayout.h:365
ogdf::NodeRespecterLayout::m_oscillationAngle
double m_oscillationAngle
Maximum angle between new and previous impulse such that the node movement is counted as an oscillati...
Definition: NodeRespecterLayout.h:256
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::NodeRespecterLayout::m_globalTemperature
double m_globalTemperature
Average of all local node temperatures.
Definition: NodeRespecterLayout.h:329
ogdf::NodeRespecterLayout::m_maxDummiesPerEdge
int m_maxDummiesPerEdge
How many dummy nodes should maximally be created for one edge.
Definition: NodeRespecterLayout.h:265
ogdf::NodeRespecterLayout::m_postProcessing
PostProcessingMode m_postProcessing
Whether unnecessary bends should be filtered out in a post processing step.
Definition: NodeRespecterLayout.h:231
ogdf::NodeRespecterLayout::getInitialTemperature
double getInitialTemperature() const
Returns m_initialTemperature.
Definition: NodeRespecterLayout.h:186
ogdf::NodeRespecterLayout::getNumberOfIterations
int getNumberOfIterations() const
Returns m_numberOfIterations.
Definition: NodeRespecterLayout.h:180
ogdf::Shape::Hexagon
@ Hexagon
hexagon
ogdf::NodeRespecterLayout::m_initialTemperature
double m_initialTemperature
Initial temperature of every node.
Definition: NodeRespecterLayout.h:244
ogdf::IntersectionType::None
@ None
Two geometric objects do not intersect.
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::NodeRespecterLayout::m_copyAttr
GraphAttributes m_copyAttr
GraphAttributes for m_copy.
Definition: NodeRespecterLayout.h:292
ogdf::NodeRespecterLayout::getRandomInitialPlacement
bool getRandomInitialPlacement() const
Returns m_randomInitialPlacement.
Definition: NodeRespecterLayout.h:171
ogdf::NodeRespecterLayout::m_barycenterY
double m_barycenterY
Weighted sum of y-coordinates of all nodes.
Definition: NodeRespecterLayout.h:323
ogdf::NodeRespecterLayout::m_factor
double m_factor
Precomputed constant used to get the max. temperature for each iteration.
Definition: NodeRespecterLayout.h:332
ogdf::LayoutModule
Interface of general layout algorithms.
Definition: LayoutModule.h:44
ogdf::GraphAttributes::width
double width(node v) const
Returns the width of the bounding box of node v.
Definition: GraphAttributes.h:380