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 ArrayLevel &	operator[] (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 Hierarchy &	hierarchy () 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).

HierarchyLevelsBase &	operator= (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< int >	m_bestPerm
	The best found permutation in the sifting step.

Array< Block * >	m_Blocks
	The array of all blocks.

Array< int >	m_currentPerm
	The permutation modified in the sifting step.

Array< int >	m_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.

Hierarchy &	m_hierarchy
	The hierarchy on grid- and globalsifting operates.

EdgeArray< bool >	m_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< int >	m_nSet
	(Only used by buildAdjNodes().)

NodeArray< int >	m_pos
	The position of a node on its level.

NodeArray< int >	m_ranks
	The rank (level) of a node.

int	m_storedCrossings
	Numebr of crossings stored in the sifting step.

Array< int >	m_storedPerm
	The permutation from which the sifting step starts.

NodeArray< Array< node > >	m_upperAdjNodes
	(Sorted) adjacent nodes on upper level.

GridSifting
Array< int >	m_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

enum class ogdf::BlockOrder::Direction

strongprivate

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:

include/ogdf/layered/BlockOrder.h

OpenGraph DrawingFramework

Public Member Functions

Private Types

Private Member Functions

Private Attributes

GridSifting

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ Direction

Constructor & Destructor Documentation

◆ ~BlockOrder()

◆ BlockOrder()

Member Function Documentation

◆ adjNodes()

◆ blocksCount()

◆ buildAdjNodes()

◆ buildDummyNodesLists()

◆ buildHierarchy()

◆ buildLevels()

◆ deconstruct()

◆ doInit()

◆ globalSifting()

◆ gridSifting()

◆ hierarchy()

◆ localCountCrossings()

◆ operator[]()

◆ pos()

◆ siftingStep()

◆ siftingSwap()

◆ size()

◆ sortAdjacencies()

◆ updateAdjacencies()

◆ uswap()

◆ verticalStep()

◆ verticalSwap()

Member Data Documentation

◆ m_activeBlocksCount

◆ m_bestCrossings

◆ m_bestPerm

◆ m_Blocks

◆ m_currentPerm

◆ m_currentPermInv

◆ m_EdgeBlocks

◆ m_GC

◆ m_hierarchy

◆ m_isActiveEdge

◆ m_levels

◆ m_lowerAdjNodes

◆ m_nNodesOnLvls

◆ m_NodeBlocks

◆ m_nSet

◆ m_pos

◆ m_ranks

◆ m_storedCrossings

◆ m_storedPerm

◆ m_upperAdjNodes

◆ m_verticalStepsBound

Open
Graph Drawing
Framework