Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

BlockOrder.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/EdgeArray.h>
35 #include <ogdf/basic/NodeArray.h>
36 #include <ogdf/basic/Graph.h>
37 #include <ogdf/basic/GraphCopy.h>
39 
40 namespace ogdf {
41 
43 class ArrayLevel : public LevelBase {
44 
45 private:
47 public:
48 
49  explicit ArrayLevel(unsigned int size) : m_nodes(size) { }
50 
51  explicit ArrayLevel(const Array<node> &nodes) : m_nodes(nodes) { }
52 
53  const node &operator[](int i) const override { return m_nodes[i]; }
54 
55  node &operator[](int i) override { return m_nodes[i]; }
56 
57  int size() const override { return m_nodes.size(); }
58 
59  int high() const override { return m_nodes.high(); }
60 
61 };
62 
63 
64 class BlockOrder;
65 
73 
74  friend class BlockOrder;
75 private:
76  int m_index = 0;
77 
78  int m_upper = 0;
79 
80  int m_lower = 0;
81 
83 
85 
87 
89 
91 
92  // exactly one of those below is non null!
93  node m_Node = nullptr;
94  edge m_Edge = nullptr;
95 
98 
99 public:
100  ~Block() { }
101 
102  bool isEdgeBlock() { return m_isEdgeBlock; }
103 
104  bool isVertexBlock() { return m_isNodeBlock; }
105 
107  explicit Block(node v);
108 
110  explicit Block(edge e);
111 
112 };
113 
126 
127 private:
128  enum class Direction { Plus, Minus };
129 
131 
133 
134  // Block X -> pi(X)
138 
139  // int i -> Block X s.t. pi(X) = i
141 
144 
145 #if 0
146  unsigned int m_storedCrossings;
147  unsigned int m_currentCrossings;
148 #endif
149 
153 
155 
156 #if 0
157  unsigned int m_blocksCount;
158 #endif
160 
162 
163  void deconstruct();
164 
166 
168 
171 
173 
174 public:
175 
178 
180  const ArrayLevel &operator[](int i) const override {
181  return *(m_levels[i]);
182  }
184  int pos(node v) const override {
185  return m_pos[v];
186  }
188  int size() const override {
189  return m_levels.size();
190  }
191 
192  const Hierarchy &hierarchy() const override {
193  return m_hierarchy;
194  }
195 
197  const Array<node> &adjNodes(node v, TraversingDir dir) const override {
198  if ( dir == TraversingDir::upward ) {
199  return m_upperAdjNodes[v];
200  } else {
201  return m_lowerAdjNodes[v];
202  }
203  }
204 
206 
207  // destruction
208  ~BlockOrder() { deconstruct(); }
209 
211  int blocksCount() { return m_Blocks.size(); }
212 
213 #if 0
214  BlockOrder(const Graph &G, const NodeArray<int> &rank);
215 #endif
216 
217  explicit BlockOrder(Hierarchy& hierarchy, bool longEdgesOnly = true);
218 
220  void globalSifting( int rho = 1, int nRepeats = 10, int *pNumCrossings = nullptr );
221 
222 private:
224  void doInit( bool longEdgesOnly = true);
225 #if 0
226  void doInit( bool longEdgesOnly = true, const NodeArray<int> &ranks);
227 #endif
228 
234  void sortAdjacencies();
235 
244  void updateAdjacencies(Block *blockOfA, Block *blockOfB, Direction d);
245 
253  int uswap(Block *blockOfA, Block *blockOfB, Direction d, int level);
254 
260  int siftingSwap(Block *blockOfA, Block *blockOfB);
261 
267  int siftingStep( Block *blockOfA );
268 
272  void buildLevels();
273 
277  void buildDummyNodesLists();
278 
282  void buildAdjNodes();
283 
288  {
289  buildDummyNodesLists();
290  buildLevels();
291  buildAdjNodes();
292  m_storedCrossings = calculateCrossings();
293  }
294 
295 
298 
302  int verticalSwap( Block *b, int level );
303 
305  int localCountCrossings( const Array<int> &levels );
306 
312  void verticalStep( Block *b );
313 
315 public:
317 
321  void gridSifting( int nRepeats = 10 );
322 
324 };
325 
326 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::BlockOrder::m_hierarchy
Hierarchy & m_hierarchy
The hierarchy on grid- and globalsifting operates.
Definition: BlockOrder.h:161
ogdf::Block::~Block
~Block()
Definition: BlockOrder.h:100
ogdf::BlockOrder::m_GC
GraphCopy m_GC
The graph copy representing the topology of the proper hierarchy.
Definition: BlockOrder.h:130
ogdf::Direction
Direction
Definition: basic.h:134
Graph.h
Includes declaration of graph class.
ogdf::Block::m_isNodeBlock
bool m_isNodeBlock
Definition: BlockOrder.h:97
ogdf::BlockOrder::m_storedCrossings
int m_storedCrossings
Numebr of crossings stored in the sifting step.
Definition: BlockOrder.h:142
ogdf::BlockOrder::hierarchy
const Hierarchy & hierarchy() const override
Definition: BlockOrder.h:192
ogdf::Array::high
INDEX high() const
Returns the maximal array index.
Definition: Array.h:283
ogdf::Block
Class representing idea of Blocks used in GlobalSifting and GridSifting algorithms.
Definition: BlockOrder.h:72
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::Hierarchy
Representation of proper hierarchies used by Sugiyama-layout.
Definition: Hierarchy.h:44
ogdf::BlockOrder::m_lowerAdjNodes
NodeArray< Array< node > > m_lowerAdjNodes
(Sorted) adjacent nodes on lower level.
Definition: BlockOrder.h:169
ogdf::HierarchyLevelsBase
Definition: CrossingMinInterfaces.h:65
ogdf::BlockOrder::m_bestCrossings
int m_bestCrossings
The lowest number of crossing found in the sifting step.
Definition: BlockOrder.h:143
ogdf::ArrayLevel::operator[]
node & operator[](int i) override
Returns the node at position i.
Definition: BlockOrder.h:55
ogdf::NodeArray< int >
ogdf::Block::m_NeighboursOutgoing
Array< int > m_NeighboursOutgoing
Indices of neighbouring outgoing blocks.
Definition: BlockOrder.h:88
ogdf::BlockOrder::m_nSet
NodeArray< int > m_nSet
(Only used by buildAdjNodes().)
Definition: BlockOrder.h:172
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::BlockOrder::blocksCount
int blocksCount()
Returns the number of blocks.
Definition: BlockOrder.h:211
ogdf::BlockOrder::m_currentPerm
Array< int > m_currentPerm
The permutation modified in the sifting step.
Definition: BlockOrder.h:136
ogdf::BlockOrder::m_upperAdjNodes
NodeArray< Array< node > > m_upperAdjNodes
(Sorted) adjacent nodes on upper level.
Definition: BlockOrder.h:170
ogdf::Block::m_nodes
Array< node > m_nodes
Vertices from the proper hierarchy corresponding to this block.
Definition: BlockOrder.h:82
ogdf::HierarchyLevelsBase::TraversingDir
TraversingDir
Definition: CrossingMinInterfaces.h:76
ogdf::BlockOrder::m_bestPerm
Array< int > m_bestPerm
The best found permutation in the sifting step.
Definition: BlockOrder.h:137
ogdf::Block::m_InvertedIncoming
Array< int > m_InvertedIncoming
Positions of this block in m_NeighboursOutgoing of neighbours.
Definition: BlockOrder.h:86
ogdf::Block::isEdgeBlock
bool isEdgeBlock()
Definition: BlockOrder.h:102
ogdf::Array< node >
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::ArrayLevel
The simple implementation of LevelBase interface.
Definition: BlockOrder.h:43
ogdf::ArrayLevel::ArrayLevel
ArrayLevel(unsigned int size)
Definition: BlockOrder.h:49
GraphCopy.h
Declaration of graph copy classes.
ogdf::BlockOrder::m_currentPermInv
Array< int > m_currentPermInv
Inversion of m_currenPerm.
Definition: BlockOrder.h:140
ogdf::BlockOrder::adjNodes
const Array< node > & adjNodes(node v, TraversingDir dir) const override
Returns the adjacent nodes of v.
Definition: BlockOrder.h:197
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::Block::m_isEdgeBlock
bool m_isEdgeBlock
Definition: BlockOrder.h:96
CrossingMinInterfaces.h
Declaration of interfaces used in Sugiyama framework.
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::Block::m_InvertedOutgoing
Array< int > m_InvertedOutgoing
Positions of this block in m_NeighboursIncoming of neighbours.
Definition: BlockOrder.h:90
ogdf::BlockOrder::m_levels
Array< ArrayLevel * > m_levels
The array of all levels.
Definition: BlockOrder.h:167
ogdf::BlockOrder::m_storedPerm
Array< int > m_storedPerm
The permutation from which the sifting step starts.
Definition: BlockOrder.h:135
ogdf::BlockOrder::size
int size() const override
Returns the number of levels.
Definition: BlockOrder.h:188
ogdf::BlockOrder::m_Blocks
Array< Block * > m_Blocks
The array of all blocks.
Definition: BlockOrder.h:150
ogdf::BlockOrder::pos
int pos(node v) const override
Returns the position of node v on its level.
Definition: BlockOrder.h:184
ogdf::BlockOrder::m_verticalStepsBound
int m_verticalStepsBound
Definition: BlockOrder.h:316
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::ArrayLevel::m_nodes
Array< node > m_nodes
Definition: BlockOrder.h:46
ogdf::BlockOrder::Direction
Direction
Definition: BlockOrder.h:128
ogdf::ArrayLevel::operator[]
const node & operator[](int i) const override
Returns the node at position i.
Definition: BlockOrder.h:53
ogdf::BlockOrder::m_pos
NodeArray< int > m_pos
The position of a node on its level.
Definition: BlockOrder.h:165
ogdf::ArrayLevel::ArrayLevel
ArrayLevel(const Array< node > &nodes)
Definition: BlockOrder.h:51
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::BlockOrder::~BlockOrder
~BlockOrder()
Definition: BlockOrder.h:208
ogdf::Block::isVertexBlock
bool isVertexBlock()
Definition: BlockOrder.h:104
ogdf::BlockOrder
Hierarchical graph representation used by GlobalSifting and GridSifting algorithms.
Definition: BlockOrder.h:125
ogdf::Array::size
INDEX size() const
Returns the size (number of elements) of the array.
Definition: Array.h:286
ogdf::BlockOrder::operator[]
const ArrayLevel & operator[](int i) const override
Returns the i-th level.
Definition: BlockOrder.h:180
ogdf::BlockOrder::m_activeBlocksCount
int m_activeBlocksCount
Definition: BlockOrder.h:159
ogdf::BlockOrder::m_EdgeBlocks
EdgeArray< Block * > m_EdgeBlocks
The array of all edge blocks.
Definition: BlockOrder.h:152
ogdf::BlockOrder::m_isActiveEdge
EdgeArray< bool > m_isActiveEdge
Stores information about active edge blocks.
Definition: BlockOrder.h:154
ogdf::LevelBase
Representation of levels in hierarchies.
Definition: CrossingMinInterfaces.h:44
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::BlockOrder::m_ranks
NodeArray< int > m_ranks
The rank (level) of a node.
Definition: BlockOrder.h:132
ogdf::BlockOrder::m_NodeBlocks
NodeArray< Block * > m_NodeBlocks
The array of all vertex blocks.
Definition: BlockOrder.h:151
ogdf::BlockOrder::m_nNodesOnLvls
Array< int > m_nNodesOnLvls
Definition: BlockOrder.h:314
ogdf::Block::m_NeighboursIncoming
Array< int > m_NeighboursIncoming
Indices of neighbouring incoming blocks.
Definition: BlockOrder.h:84
ogdf::ArrayLevel::high
int high() const override
Returns the maximal array index (= size()-1).
Definition: BlockOrder.h:59
ogdf::ArrayLevel::size
int size() const override
Returns the number of nodes on this level.
Definition: BlockOrder.h:57
ogdf::BlockOrder::buildHierarchy
void buildHierarchy()
Builds arrays that allow using BlockOrder as HierarchyLevelsBase implementation.
Definition: BlockOrder.h:287