Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

LayerBasedUPRLayout.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <memory>
43 
44 namespace ogdf {
45 
47 {
48 public:
49  OrderComparer(const UpwardPlanRep &_UPR, Hierarchy &_H);
50 
56  bool less(node vH1, node vH2) const;
57 
58 private:
62 #if 0
63  EdgeArray<int> outEdgeOrder;
64 #endif
66 
68  void dfs_LR(edge e,
69  NodeArray<bool> &visited,
70  NodeArray<int> &dfsNum,
71  int &num);
72 
74  bool left(node vUPR1,
75  const List<edge> &chain1,
76  node vUPR2,
77  const List<edge> &chain2
78  ) const;
79 
86  bool left(edge e1UPR, edge e2UPR) const;
87 
95  bool left(List<edge> &chain1, List<edge> &chain2, int level) const;
96 
98  bool checkUp(node vUPR, int level) const;
99 };
100 
101 
106 {
107 public:
108 
109  // constructor: sets options to default values
111  {
112  // set default value
114  fhl->nodeDistance(40.0);
115  fhl->layerDistance(40.0);
116  fhl->fixedLayerDistance(true);
117  m_layout.reset(fhl);
118  OptimalRanking *opRank = new OptimalRanking();
119  opRank->separateMultiEdges(false);
120  m_ranking.reset(opRank);
121  m_numLevels = 0;
122  m_maxLevelSize = 0;
123  }
124 
125  // destructor
127 
128  // returns the number of crossings in the layout after the algorithm
129  // has been applied
130  int numberOfCrossings() const { return m_crossings; }
131 
132  // module option for the computation of the final layout
134  m_layout.reset(pLayout);
135  }
136 
137 
138  void setRanking(RankingModule *pRanking) {
139  m_ranking.reset(pRanking);
140  }
141 
143  void UPRLayoutSimple(const UpwardPlanRep &UPR, GraphAttributes &AG);
144 
146  int numberOfLayers() { return m_numLevels; }
147 
149  int maxLayerSize() { return m_maxLevelSize; }
150 
151 protected :
152 
153  /*
154  * @param UPR is the upward planarized representation of the input graph.
155  * @param AG has to be assigned the hierarchy layout.
156  */
157  virtual void doCall(const UpwardPlanRep &UPR, GraphAttributes &AG) override;
158 
160 
161  std::unique_ptr<RankingModule> m_ranking;
162 
163  std::unique_ptr<HierarchyLayoutModule> m_layout;
164 
165 private:
166 
167  // compute a ranking of the nodes of UPR.
168  // Precond. a ranking module muss be set
169  void computeRanking(const UpwardPlanRep &UPR, NodeArray<int> &rank);
170 
171 
173  void postProcessing_sourceReorder(HierarchyLevels &levels, List<node> &sources);
174 
175 
177  void postProcessing_reduceLED(Hierarchy &H, HierarchyLevels &levels, const List<node> &sources) {
178  for(node s : sources)
179  postProcessing_reduceLED(H, levels, s);
180  }
181 
182  void postProcessing_reduceLED(Hierarchy &H, HierarchyLevels &levels, node vH);
183 
184  void post_processing_reduce(Hierarchy &H, HierarchyLevels &levels, int &i, node s, int minIdx, int maxIdx, NodeArray<bool> &markedNodes);
185 
187  void postProcessing_markUp(HierarchyLevels &levels, node sH, NodeArray<bool> &markedNodes);
188 
189 
191  void post_processing_deleteLvl(Hierarchy &H, HierarchyLevels &levels, int i);
192 
194  void post_processing_deleteInterval(Hierarchy &H, HierarchyLevels &levels, int beginIdx, int endIdx, int &j);
195 
197  void post_processing_CopyInterval(Hierarchy &H, HierarchyLevels &levels, int i, int beginIdx, int endIdx, int pos);
198 
202 
203 
206 
207  void callSimple(GraphAttributes &AG, adjEntry adj //left most edge of the source
208  );
209 
210  // needed for UPRLayoutSimple
211  void dfsSortLevels(
212  adjEntry adj1,
213  const NodeArray<int> &rank,
214  Array<SListPure<node> > &nodes);
215 
216  // needed for UPRLayoutSimple
217  void longestPathRanking(const Graph &G, NodeArray<int> &rank);
218 
220 };
221 
222 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
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::FastHierarchyLayout::nodeDistance
double nodeDistance() const
Returns the option node distance.
Definition: FastHierarchyLayout.h:97
ogdf::OptimalRanking::separateMultiEdges
bool separateMultiEdges() const
Returns the current setting of option separateMultiEdges.
Definition: OptimalRanking.h:125
RankingModule.h
Declaration of interface for ranking algorithms.
ogdf::OptimalRanking
The optimal ranking algorithm.
Definition: OptimalRanking.h:74
ogdf::LayerBasedUPRLayout::setRanking
void setRanking(RankingModule *pRanking)
Definition: LayerBasedUPRLayout.h:138
ogdf::OrderComparer
Definition: LayerBasedUPRLayout.h:46
ogdf::OrderComparer::left
bool left(node vUPR1, const List< edge > &chain1, node vUPR2, const List< edge > &chain2) const
Returns true if vUPR1 is on the left-hand side of vUPR2 according to m_UPR.
ogdf::HierarchyLayoutModule
Interface of hierarchy layout algorithms.
Definition: HierarchyLayoutModule.h:47
ogdf::LayerBasedUPRLayout::m_ranking
std::unique_ptr< RankingModule > m_ranking
Definition: LayerBasedUPRLayout.h:161
ogdf::LayerBasedUPRLayout::m_crossings
int m_crossings
Definition: LayerBasedUPRLayout.h:159
ogdf::FastHierarchyLayout::fixedLayerDistance
bool fixedLayerDistance() const
Returns the option fixed layer distance.
Definition: FastHierarchyLayout.h:117
UpwardPlanRep.h
Declaration of a base class for planar representations of graphs and cluster graphs.
HierarchyLevels.h
Declaration of HierarchyLevels class.
ogdf::Hierarchy
Representation of proper hierarchies used by Sugiyama-layout.
Definition: Hierarchy.h:44
ogdf::UPRLayoutModule
Interface of hierarchy layout algorithms.
Definition: UPRLayoutModule.h:46
ogdf::RankingModule
Interface of algorithms for computing a node ranking.
Definition: RankingModule.h:45
ogdf::LayerBasedUPRLayout::m_layout
std::unique_ptr< HierarchyLayoutModule > m_layout
Definition: LayerBasedUPRLayout.h:163
ogdf::OrderComparer::less
bool less(node vH1, node vH2) const
Returns true iff vH1 and vH2 are placed on the same layer and node vH1 has to drawn on the left-hand ...
ogdf::NodeArray< int >
ogdf::EdgeArray< int >
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::OrderComparer::m_UPR
const UpwardPlanRep & m_UPR
Definition: LayerBasedUPRLayout.h:59
ogdf::LayerBasedUPRLayout::m_numLevels
int m_numLevels
Definition: LayerBasedUPRLayout.h:199
ogdf::LayerBasedUPRLayout::setLayout
void setLayout(HierarchyLayoutModule *pLayout)
Definition: LayerBasedUPRLayout.h:133
OptimalRanking.h
Declaration of optimal ranking algorithm for Sugiyama algorithm.
FastHierarchyLayout.h
declaration and implementation of the third phase of sugiyama
ogdf::OrderComparer::H
Hierarchy & H
Definition: LayerBasedUPRLayout.h:60
ogdf::LayerBasedUPRLayout
Definition: LayerBasedUPRLayout.h:105
ogdf::OrderComparer::checkUp
bool checkUp(node vUPR, int level) const
Returns true iff there is a node above vUPR with rank level or lower.
ogdf::LayerBasedUPRLayout::m_maxLevelSize
int m_maxLevelSize
Definition: LayerBasedUPRLayout.h:200
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::FastHierarchyLayout::layerDistance
double layerDistance() const
Returns the option layer distance.
Definition: FastHierarchyLayout.h:107
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::OrderComparer::crossed
NodeArray< bool > crossed
Definition: LayerBasedUPRLayout.h:65
ogdf::List< edge >
ogdf::OrderComparer::OrderComparer
OrderComparer(const UpwardPlanRep &_UPR, Hierarchy &_H)
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::OrderComparer::m_dfsNum
NodeArray< int > m_dfsNum
Definition: LayerBasedUPRLayout.h:61
ogdf::LayerBasedUPRLayout::numberOfLayers
int numberOfLayers()
Return the number of layers/levels. Not implemented if use methode callSimple(..).
Definition: LayerBasedUPRLayout.h:146
ogdf::OrderComparer::dfs_LR
void dfs_LR(edge e, NodeArray< bool > &visited, NodeArray< int > &dfsNum, int &num)
Traverses with dfs using edge order from left to right and compute the dfs number.
ogdf::LayerBasedUPRLayout::~LayerBasedUPRLayout
~LayerBasedUPRLayout()
Definition: LayerBasedUPRLayout.h:126
ogdf::LayerBasedUPRLayout::m_dummies
ArrayBuffer< node > m_dummies
Definition: LayerBasedUPRLayout.h:201
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
UPRLayoutModule.h
Declaration of interface for layout algorithms for a UpwardPlanRep.
HierarchyLayoutModule.h
Declaration of interface hierarchy layout algorithms (3. phase of Sugiyama).
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
OptimalHierarchyLayout.h
Declaration and implementation of the optimal third phase of the Sugiyama algorithm.
ogdf::FastHierarchyLayout
Coordinate assignment phase for the Sugiyama algorithm by Buchheim et al.
Definition: FastHierarchyLayout.h:76
ogdf::UpwardPlanRep
Upward planarized representations (of a connected component) of a graph.
Definition: UpwardPlanRep.h:51
ogdf::LayerBasedUPRLayout::numberOfCrossings
int numberOfCrossings() const
Definition: LayerBasedUPRLayout.h:130
ogdf::LayerBasedUPRLayout::LayerBasedUPRLayout
LayerBasedUPRLayout()
Definition: LayerBasedUPRLayout.h:110
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::LayerBasedUPRLayout::postProcessing_reduceLED
void postProcessing_reduceLED(Hierarchy &H, HierarchyLevels &levels, const List< node > &sources)
reduce the long edge dummies (LED)
Definition: LayerBasedUPRLayout.h:177
ogdf::HierarchyLevels
Representation of proper hierarchies used by Sugiyama-layout.
Definition: HierarchyLevels.h:46
ogdf::LayerBasedUPRLayout::maxLayerSize
int maxLayerSize()
Return the max. number of elements on a layer. Not implemented if use methode callSimple(....
Definition: LayerBasedUPRLayout.h:149