Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::BlockOrder Class Reference

Hierarchical graph representation used by GlobalSifting and GridSifting algorithms. More...

#include <ogdf/layered/BlockOrder.h>

+ Inheritance diagram for ogdf::BlockOrder:

Public Member Functions

 BlockOrder (Hierarchy &hierarchy, bool longEdgesOnly=true)
 
 ~BlockOrder ()
 
int blocksCount ()
 Returns the number of blocks. More...
 
void globalSifting (int rho=1, int nRepeats=10, int *pNumCrossings=nullptr)
 Calls the global sifting algorithm on graph (its hierarchy). More...
 
HierarchyLevelsBase members
const ArrayLeveloperator[] (int i) const override
 Returns the i-th level. More...
 
int pos (node v) const override
 Returns the position of node v on its level. More...
 
int size () const override
 Returns the number of levels. More...
 
const Hierarchyhierarchy () const override
 
const Array< node > & adjNodes (node v, TraversingDir dir) const override
 Returns the adjacent nodes of v. More...
 
- Public Member Functions inherited from ogdf::HierarchyLevelsBase
 HierarchyLevelsBase ()=default
 
 HierarchyLevelsBase (const HierarchyLevelsBase &)=default
 
virtual ~HierarchyLevelsBase ()
 
int calculateCrossings () const
 Computes the total number of crossings. More...
 
int calculateCrossings (int i) const
 Computes the number of crossings between level i and i+1. More...
 
virtual int high () const
 Returns the maximal array index of a level (= size()-1). More...
 
HierarchyLevelsBaseoperator= (const HierarchyLevelsBase &)=default
 

Private Types

enum  Direction { Direction::Plus, Direction::Minus }
 

Private Member Functions

void buildAdjNodes ()
 Builds lists of adjacent nodes (needed by HierarchyLevelsBase). More...
 
void buildDummyNodesLists ()
 Builds list of dummy nodes laying inside edge blocks. More...
 
void buildHierarchy ()
 Builds arrays that allow using BlockOrder as HierarchyLevelsBase implementation. More...
 
void buildLevels ()
 Builds levels of vertices from original graph. More...
 
void deconstruct ()
 Deletes levels and blocks owned by this instance of BlockOrder. More...
 
void doInit (bool longEdgesOnly=true)
 Does some initialization. More...
 
int siftingStep (Block *blockOfA)
 Performs sifting for a single block. More...
 
int siftingSwap (Block *blockOfA, Block *blockOfB)
 Swaps two consecutive blocks. More...
 
void sortAdjacencies ()
 Creates sorted lists of neighbours for all blocks. More...
 
void updateAdjacencies (Block *blockOfA, Block *blockOfB, Direction d)
 Updates adjacencies lists before swaping two blocks. More...
 
int uswap (Block *blockOfA, Block *blockOfB, Direction d, int level)
 Calculates change of crossings made by a single swap. More...
 

Private Attributes

int m_activeBlocksCount
 
int m_bestCrossings
 The lowest number of crossing found in the sifting step. More...
 
Array< int > m_bestPerm
 The best found permutation in the sifting step. More...
 
Array< Block * > m_Blocks
 The array of all blocks. More...
 
Array< int > m_currentPerm
 The permutation modified in the sifting step. More...
 
Array< int > m_currentPermInv
 Inversion of m_currenPerm. More...
 
EdgeArray< Block * > m_EdgeBlocks
 The array of all edge blocks. More...
 
GraphCopy m_GC
 The graph copy representing the topology of the proper hierarchy. More...
 
Hierarchym_hierarchy
 The hierarchy on grid- and globalsifting operates. More...
 
EdgeArray< bool > m_isActiveEdge
 Stores information about active edge blocks. More...
 
Array< ArrayLevel * > m_levels
 The array of all levels. More...
 
NodeArray< Array< node > > m_lowerAdjNodes
 (Sorted) adjacent nodes on lower level. More...
 
NodeArray< Block * > m_NodeBlocks
 The array of all vertex blocks. More...
 
NodeArray< int > m_nSet
 (Only used by buildAdjNodes().) More...
 
NodeArray< int > m_pos
 The position of a node on its level. More...
 
NodeArray< int > m_ranks
 The rank (level) of a node. More...
 
int m_storedCrossings
 Numebr of crossings stored in the sifting step. More...
 
Array< int > m_storedPerm
 The permutation from which the sifting step starts. More...
 
NodeArray< Array< node > > m_upperAdjNodes
 (Sorted) adjacent nodes on upper level. More...
 

GridSifting

Array< int > m_nNodesOnLvls
 
int m_verticalStepsBound
 
int verticalSwap (Block *b, int level)
 Moves block to next level. More...
 
int localCountCrossings (const Array< int > &levels)
 Only used in verticalSwap(). More...
 
void verticalStep (Block *b)
 Performs vertical step for block b. More...
 
void gridSifting (int nRepeats=10)
 Calls the grid sifting algorithm on a graph (its hierarchy). More...
 

Additional Inherited Members

- Public Types inherited from ogdf::HierarchyLevelsBase
enum  TraversingDir { TraversingDir::downward, TraversingDir::upward }
 

Detailed Description

Hierarchical graph representation used by GlobalSifting and GridSifting algorithms.

This representation is based on blocks. Each block is a single vertex from the original graph or edge that consists of some dummy vertices in hierarchical embedding of this graph.

BlockOrder stores permutation of blocks (their x-coordinates) and uses this information in translation to Hierarchy and HierarchyLevelsBase.

Definition at line 125 of file BlockOrder.h.

Member Enumeration Documentation

◆ Direction

enum ogdf::BlockOrder::Direction
strongprivate
Enumerator
Plus 
Minus 

Definition at line 128 of file BlockOrder.h.

Constructor & Destructor Documentation

◆ ~BlockOrder()

ogdf::BlockOrder::~BlockOrder ( )
inline

Definition at line 208 of file BlockOrder.h.

◆ BlockOrder()

ogdf::BlockOrder::BlockOrder ( Hierarchy hierarchy,
bool  longEdgesOnly = true 
)
explicit

Member Function Documentation

◆ adjNodes()

const Array<node>& ogdf::BlockOrder::adjNodes ( node  v,
TraversingDir  dir 
) const
inlineoverridevirtual

Returns the adjacent nodes of v.

Implements ogdf::HierarchyLevelsBase.

Definition at line 197 of file BlockOrder.h.

◆ blocksCount()

int ogdf::BlockOrder::blocksCount ( )
inline

Returns the number of blocks.

Definition at line 211 of file BlockOrder.h.

◆ buildAdjNodes()

void ogdf::BlockOrder::buildAdjNodes ( )
private

Builds lists of adjacent nodes (needed by HierarchyLevelsBase).

◆ buildDummyNodesLists()

void ogdf::BlockOrder::buildDummyNodesLists ( )
private

Builds list of dummy nodes laying inside edge blocks.

◆ buildHierarchy()

void ogdf::BlockOrder::buildHierarchy ( )
inlineprivate

Builds arrays that allow using BlockOrder as HierarchyLevelsBase implementation.

Definition at line 287 of file BlockOrder.h.

◆ buildLevels()

void ogdf::BlockOrder::buildLevels ( )
private

Builds levels of vertices from original graph.

◆ deconstruct()

void ogdf::BlockOrder::deconstruct ( )
private

Deletes levels and blocks owned by this instance of BlockOrder.

◆ doInit()

void ogdf::BlockOrder::doInit ( bool  longEdgesOnly = true)
private

Does some initialization.

◆ globalSifting()

void ogdf::BlockOrder::globalSifting ( int  rho = 1,
int  nRepeats = 10,
int *  pNumCrossings = nullptr 
)

Calls the global sifting algorithm on graph (its hierarchy).

◆ gridSifting()

void ogdf::BlockOrder::gridSifting ( int  nRepeats = 10)

Calls the grid sifting algorithm on a graph (its hierarchy).

◆ hierarchy()

const Hierarchy& ogdf::BlockOrder::hierarchy ( ) const
inlineoverridevirtual

Implements ogdf::HierarchyLevelsBase.

Definition at line 192 of file BlockOrder.h.

◆ localCountCrossings()

int ogdf::BlockOrder::localCountCrossings ( const Array< int > &  levels)
private

Only used in verticalSwap().

◆ operator[]()

const ArrayLevel& ogdf::BlockOrder::operator[] ( int  i) const
inlineoverridevirtual

Returns the i-th level.

Implements ogdf::HierarchyLevelsBase.

Definition at line 180 of file BlockOrder.h.

◆ pos()

int ogdf::BlockOrder::pos ( node  v) const
inlineoverridevirtual

Returns the position of node v on its level.

Implements ogdf::HierarchyLevelsBase.

Definition at line 184 of file BlockOrder.h.

◆ siftingStep()

int ogdf::BlockOrder::siftingStep ( Block blockOfA)
private

Performs sifting for a single block.

See SIFTING-STEP in papers.

◆ siftingSwap()

int ogdf::BlockOrder::siftingSwap ( Block blockOfA,
Block blockOfB 
)
private

Swaps two consecutive blocks.

See SIFTING-STEP in papers.

◆ size()

int ogdf::BlockOrder::size ( ) const
inlineoverridevirtual

Returns the number of levels.

Implements ogdf::HierarchyLevelsBase.

Definition at line 188 of file BlockOrder.h.

◆ sortAdjacencies()

void ogdf::BlockOrder::sortAdjacencies ( )
private

Creates sorted lists of neighbours for all blocks.

See function SORT-ADJACENCIES in paper.

◆ updateAdjacencies()

void ogdf::BlockOrder::updateAdjacencies ( Block blockOfA,
Block blockOfB,
Direction  d 
)
private

Updates adjacencies lists before swaping two blocks.

Updates adjacencies lists of two blocks and their neighbours in direction d. This function is called before blocks are swapped. See UPDATE-ADJACENCIES in papers.

◆ uswap()

int ogdf::BlockOrder::uswap ( Block blockOfA,
Block blockOfB,
Direction  d,
int  level 
)
private

Calculates change of crossings made by a single swap.

Calculates change in number of crossing after swapping two consecutive blocks in current permutation. See USWAP in papers.

◆ verticalStep()

void ogdf::BlockOrder::verticalStep ( Block b)
private

Performs vertical step for block b.

See VERTICAL-STEP in papers.

◆ verticalSwap()

int ogdf::BlockOrder::verticalSwap ( Block b,
int  level 
)
private

Moves block to next level.

Member Data Documentation

◆ m_activeBlocksCount

int ogdf::BlockOrder::m_activeBlocksCount
private

Definition at line 159 of file BlockOrder.h.

◆ m_bestCrossings

int ogdf::BlockOrder::m_bestCrossings
private

The lowest number of crossing found in the sifting step.

Definition at line 143 of file BlockOrder.h.

◆ m_bestPerm

Array<int> ogdf::BlockOrder::m_bestPerm
private

The best found permutation in the sifting step.

Definition at line 137 of file BlockOrder.h.

◆ m_Blocks

Array<Block *> ogdf::BlockOrder::m_Blocks
private

The array of all blocks.

Definition at line 150 of file BlockOrder.h.

◆ m_currentPerm

Array<int> ogdf::BlockOrder::m_currentPerm
private

The permutation modified in the sifting step.

Definition at line 136 of file BlockOrder.h.

◆ m_currentPermInv

Array<int> ogdf::BlockOrder::m_currentPermInv
private

Inversion of m_currenPerm.

Definition at line 140 of file BlockOrder.h.

◆ m_EdgeBlocks

EdgeArray<Block *> ogdf::BlockOrder::m_EdgeBlocks
private

The array of all edge blocks.

Definition at line 152 of file BlockOrder.h.

◆ m_GC

GraphCopy ogdf::BlockOrder::m_GC
private

The graph copy representing the topology of the proper hierarchy.

Definition at line 130 of file BlockOrder.h.

◆ m_hierarchy

Hierarchy& ogdf::BlockOrder::m_hierarchy
private

The hierarchy on grid- and globalsifting operates.

Definition at line 161 of file BlockOrder.h.

◆ m_isActiveEdge

EdgeArray<bool> ogdf::BlockOrder::m_isActiveEdge
private

Stores information about active edge blocks.

Definition at line 154 of file BlockOrder.h.

◆ m_levels

Array<ArrayLevel *> ogdf::BlockOrder::m_levels
private

The array of all levels.

Definition at line 167 of file BlockOrder.h.

◆ m_lowerAdjNodes

NodeArray<Array<node> > ogdf::BlockOrder::m_lowerAdjNodes
private

(Sorted) adjacent nodes on lower level.

Definition at line 169 of file BlockOrder.h.

◆ m_nNodesOnLvls

Array<int> ogdf::BlockOrder::m_nNodesOnLvls
private

Definition at line 314 of file BlockOrder.h.

◆ m_NodeBlocks

NodeArray<Block *> ogdf::BlockOrder::m_NodeBlocks
private

The array of all vertex blocks.

Definition at line 151 of file BlockOrder.h.

◆ m_nSet

NodeArray<int> ogdf::BlockOrder::m_nSet
private

(Only used by buildAdjNodes().)

Definition at line 172 of file BlockOrder.h.

◆ m_pos

NodeArray<int> ogdf::BlockOrder::m_pos
private

The position of a node on its level.

Definition at line 165 of file BlockOrder.h.

◆ m_ranks

NodeArray<int> ogdf::BlockOrder::m_ranks
private

The rank (level) of a node.

Definition at line 132 of file BlockOrder.h.

◆ m_storedCrossings

int ogdf::BlockOrder::m_storedCrossings
private

Numebr of crossings stored in the sifting step.

Definition at line 142 of file BlockOrder.h.

◆ m_storedPerm

Array<int> ogdf::BlockOrder::m_storedPerm
private

The permutation from which the sifting step starts.

Definition at line 135 of file BlockOrder.h.

◆ m_upperAdjNodes

NodeArray<Array<node> > ogdf::BlockOrder::m_upperAdjNodes
private

(Sorted) adjacent nodes on upper level.

Definition at line 170 of file BlockOrder.h.

◆ m_verticalStepsBound

int ogdf::BlockOrder::m_verticalStepsBound

Definition at line 316 of file BlockOrder.h.


The documentation for this class was generated from the following file: