Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

Private Types

enum class  Direction { Plus , Minus }
 

Private Member Functions

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

Private Attributes

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

GridSifting

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

Additional Inherited Members

- Public Types inherited from ogdf::HierarchyLevelsBase
enum class  TraversingDir { downward , 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 122 of file BlockOrder.h.

Member Enumeration Documentation

◆ Direction

Enumerator
Plus 
Minus 

Definition at line 124 of file BlockOrder.h.

Constructor & Destructor Documentation

◆ ~BlockOrder()

ogdf::BlockOrder::~BlockOrder ( )
inline

Definition at line 197 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 186 of file BlockOrder.h.

◆ blocksCount()

int ogdf::BlockOrder::blocksCount ( )
inline

Returns the number of blocks.

Definition at line 200 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 276 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 183 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 175 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 178 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 181 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 155 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 139 of file BlockOrder.h.

◆ m_bestPerm

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

The best found permutation in the sifting step.

Definition at line 133 of file BlockOrder.h.

◆ m_Blocks

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

The array of all blocks.

Definition at line 146 of file BlockOrder.h.

◆ m_currentPerm

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

The permutation modified in the sifting step.

Definition at line 132 of file BlockOrder.h.

◆ m_currentPermInv

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

Inversion of m_currenPerm.

Definition at line 136 of file BlockOrder.h.

◆ m_EdgeBlocks

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

The array of all edge blocks.

Definition at line 148 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 126 of file BlockOrder.h.

◆ m_hierarchy

Hierarchy& ogdf::BlockOrder::m_hierarchy
private

The hierarchy on grid- and globalsifting operates.

Definition at line 157 of file BlockOrder.h.

◆ m_isActiveEdge

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

Stores information about active edge blocks.

Definition at line 150 of file BlockOrder.h.

◆ m_levels

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

The array of all levels.

Definition at line 163 of file BlockOrder.h.

◆ m_lowerAdjNodes

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

(Sorted) adjacent nodes on lower level.

Definition at line 165 of file BlockOrder.h.

◆ m_nNodesOnLvls

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

Definition at line 301 of file BlockOrder.h.

◆ m_NodeBlocks

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

The array of all vertex blocks.

Definition at line 147 of file BlockOrder.h.

◆ m_nSet

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

(Only used by buildAdjNodes().)

Definition at line 168 of file BlockOrder.h.

◆ m_pos

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

The position of a node on its level.

Definition at line 161 of file BlockOrder.h.

◆ m_ranks

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

The rank (level) of a node.

Definition at line 128 of file BlockOrder.h.

◆ m_storedCrossings

int ogdf::BlockOrder::m_storedCrossings
private

Numebr of crossings stored in the sifting step.

Definition at line 138 of file BlockOrder.h.

◆ m_storedPerm

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

The permutation from which the sifting step starts.

Definition at line 131 of file BlockOrder.h.

◆ m_upperAdjNodes

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

(Sorted) adjacent nodes on upper level.

Definition at line 166 of file BlockOrder.h.

◆ m_verticalStepsBound

int ogdf::BlockOrder::m_verticalStepsBound

Definition at line 304 of file BlockOrder.h.


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