BFS tree used by both classical algorithms (LT and Dual). More...

#include <ogdf/graphalg/PlanarSeparatorModule.h>

Inheritance diagram for ogdf::planar_separators::BFSTreeClassical:

Public Member Functions
	BFSTreeClassical (GraphCopy &G, node rootNode, unsigned int heightMaxIterations, bool findLevelsSimple=false)
	Constructor.

	~BFSTreeClassical ()

void	construct (node rootNode, unsigned int numIterations)
	Constructs the tree.

void	createNewRoot (bool useTriBFS=false)
	Creates a new root node for the graph, replacing all levels below t0.

int	get_t0 () const

int	get_t1 () const

int	get_t2 () const

List< node >	getLevel (int level) const
	Returns a level of the tree.

List< node >	getNodesFrom (int start) const
	Returns all nodes from a given level onwards.

List< node >	getNodesFromTo (int start, int end) const
	Returns all nodes between two levels.

int	getSeparatorLevel () const

int	getSizeOfLevel (int level) const
	Gets the size of a specific level.

bool	isVisited (node n) const
	Checks whether a node is visited by BFS.

void	reconstruct ()
	Reconstructs the tree using triangulating bfs.

void	removeSeparatorLevels (List< node > &separator, List< node > &second)
	Removes the two separator levels t0 and t2 from the tree.

void	restructure (List< node > &separator, List< node > &second, bool useTriBFS=false)
	Restructures the tree by adding a new root and deleting all nodes below t0 and above t2, adding all nodes that are removed to the second component and keeping levels t0 and t2 in the separator.

Public Member Functions inherited from ogdf::planar_separators::ArrayBFSTree
	ArrayBFSTree (GraphCopy &G, node rootNode)
	Constructor.

adjEntry	getAdjToParent (node n) const override
	Returns the adjEntry that leads up to the parent of `n`.

List< node >	getChildrenOfNode (node n) const override
	Returns all (immediate) children of a node.

int	getDescendantsOfNode (node n) const override
	Returns the total number of children, grandchildren etc.

GraphCopy *	getGraph () const override
	Allows access to a copy of the graph.

int	getGraphSize () const override
	Gets the number of nodes of the graph.

int	getLevelOfNode (node n) const override
	Returns the level (=depth in the tree) for a node.

node	getParentOfNode (node n) const override
	Returns the node that is the parent of `n` in the tree.

node	getRoot () const override
	Gets the current root node of the tree.

void	init ()
	Initializes all internal arrays.

bool	isInTree (edge e) const override
	Checks if an edge is a tree-edge.

Public Member Functions inherited from ogdf::planar_separators::BFSTree
virtual	~BFSTree ()=default

Protected Member Functions
void	findLevels ()
	Finds the levels t0 and t2 of the tree that might serve as separators.

void	findLevelsSimple ()
	Simplified version of findLevels that simply finds a level smaller than sqrt(n).

Private Member Functions
void	visit (node v, node parent, adjEntry adj, SListPure< node > &bfs)

Private Attributes
bool	belowMiddle = true

int	currentLevel = 0

unsigned int	heightMaxIterations

int	k

List< List< node > >	levels

double	m_ratio

bool	simple

int	t0

int	t1

int	t2

Additional Inherited Members
Protected Attributes inherited from ogdf::planar_separators::ArrayBFSTree
NodeArray< List< node > >	childrenOfNode

NodeArray< int >	descendantsOfNode

NodeArray< adjEntry >	edgeToParent

EdgeArray< bool >	inTree

NodeArray< int >	levelOfNode

NodeArray< bool >	mark

NodeArray< node >	parentOfNode

GraphCopy *	pGraph

node	root

Detailed Description

BFS tree used by both classical algorithms (LT and Dual).

Definition at line 224 of file PlanarSeparatorModule.h.

Constructor & Destructor Documentation

◆ BFSTreeClassical()

ogdf::planar_separators::BFSTreeClassical::BFSTreeClassical	(	GraphCopy &	G,
		node	rootNode,
		unsigned int	heightMaxIterations,
		bool	findLevelsSimple = `false`
	)

Constructor.

Parameters

G	the graph
rootNode	node at which tree should be rooted
heightMaxIterations	how many iterations of tree height maximization to run
findLevelsSimple	whether the levels should be found using the simple method or not

◆ ~BFSTreeClassical()

ogdf::planar_separators::BFSTreeClassical::~BFSTreeClassical ( )

inline

Definition at line 237 of file PlanarSeparatorModule.h.

Member Function Documentation

◆ construct()

void ogdf::planar_separators::BFSTreeClassical::construct	(	node	rootNode,
		unsigned int	numIterations
	)

Constructs the tree.

Parameters

rootNode	the root node at which construction starts in this iteration
numIterations	how many iterations of tree height maximization to run

◆ createNewRoot()

void ogdf::planar_separators::BFSTreeClassical::createNewRoot ( bool useTriBFS = false )

Creates a new root node for the graph, replacing all levels below t0.

Parameters

useTriBFS whether to use triangulating BFS or not

◆ findLevels()

void ogdf::planar_separators::BFSTreeClassical::findLevels ( )

protected

Finds the levels t0 and t2 of the tree that might serve as separators.

This is the original version described by Lipton & Tarjan.

◆ findLevelsSimple()

void ogdf::planar_separators::BFSTreeClassical::findLevelsSimple ( )

protected

Simplified version of findLevels that simply finds a level smaller than sqrt(n).

◆ get_t0()

int ogdf::planar_separators::BFSTreeClassical::get_t0 ( ) const

inline

Definition at line 320 of file PlanarSeparatorModule.h.

◆ get_t1()

int ogdf::planar_separators::BFSTreeClassical::get_t1 ( ) const

inline

Definition at line 322 of file PlanarSeparatorModule.h.

◆ get_t2()

int ogdf::planar_separators::BFSTreeClassical::get_t2 ( ) const

inline

Definition at line 324 of file PlanarSeparatorModule.h.

◆ getLevel()

List< node > ogdf::planar_separators::BFSTreeClassical::getLevel ( int level ) const

Returns a level of the tree.

Parameters

level index of the desired level

Returns: List of nodes in that level

◆ getNodesFrom()

List< node > ogdf::planar_separators::BFSTreeClassical::getNodesFrom ( int start ) const

Returns all nodes from a given level onwards.

Parameters

start index of the start level

Returns: all nodes from this level on

◆ getNodesFromTo()

List< node > ogdf::planar_separators::BFSTreeClassical::getNodesFromTo	(	int	start,
		int	end
	)		const

Returns all nodes between two levels.

Parameters

start	index of the start level
end	index of the end level

Returns: a list containing all nodes between levels start and end

◆ getSeparatorLevel()

int ogdf::planar_separators::BFSTreeClassical::getSeparatorLevel ( ) const

inline

Definition at line 318 of file PlanarSeparatorModule.h.

◆ getSizeOfLevel()

int ogdf::planar_separators::BFSTreeClassical::getSizeOfLevel ( int level ) const

Gets the size of a specific level.

Parameters

level index of the desired level

Returns: the number of nodes in that level

◆ isVisited()

bool ogdf::planar_separators::BFSTreeClassical::isVisited ( node n ) const

inline

Checks whether a node is visited by BFS.

Parameters

n the node

Returns: true if this node was visited

Definition at line 316 of file PlanarSeparatorModule.h.

◆ reconstruct()

void ogdf::planar_separators::BFSTreeClassical::reconstruct ( )

Reconstructs the tree using triangulating bfs.

◆ removeSeparatorLevels()

void ogdf::planar_separators::BFSTreeClassical::removeSeparatorLevels	(	List< node > &	separator,
		List< node > &	second
	)

Removes the two separator levels t0 and t2 from the tree.

Parameters

separator	the list of separator nodes
second	the second component

◆ restructure()

void ogdf::planar_separators::BFSTreeClassical::restructure	(	List< node > &	separator,
		List< node > &	second,
		bool	useTriBFS = `false`
	)

Restructures the tree by adding a new root and deleting all nodes below t0 and above t2, adding all nodes that are removed to the second component and keeping levels t0 and t2 in the separator.

Parameters

separator	the list of separator nodes
second	the second component of the separation
useTriBFS	whether to use triangulating BFS

◆ visit()

void ogdf::planar_separators::BFSTreeClassical::visit	(	node	v,
		node	parent,
		adjEntry	adj,
		SListPure< node > &	bfs
	)

private

Member Data Documentation

◆ belowMiddle

bool ogdf::planar_separators::BFSTreeClassical::belowMiddle = true

private

Definition at line 347 of file PlanarSeparatorModule.h.

◆ currentLevel

int ogdf::planar_separators::BFSTreeClassical::currentLevel = 0

private

Definition at line 346 of file PlanarSeparatorModule.h.

◆ heightMaxIterations

unsigned int ogdf::planar_separators::BFSTreeClassical::heightMaxIterations

private

Definition at line 342 of file PlanarSeparatorModule.h.

◆ k

int ogdf::planar_separators::BFSTreeClassical::k

private

Definition at line 354 of file PlanarSeparatorModule.h.

◆ levels

List<List<node> > ogdf::planar_separators::BFSTreeClassical::levels

private

Definition at line 340 of file PlanarSeparatorModule.h.

◆ m_ratio

double ogdf::planar_separators::BFSTreeClassical::m_ratio

private

Definition at line 348 of file PlanarSeparatorModule.h.

◆ simple

bool ogdf::planar_separators::BFSTreeClassical::simple

private

Definition at line 343 of file PlanarSeparatorModule.h.

◆ t0

int ogdf::planar_separators::BFSTreeClassical::t0

private

Definition at line 351 of file PlanarSeparatorModule.h.

◆ t1

int ogdf::planar_separators::BFSTreeClassical::t1

private

Definition at line 352 of file PlanarSeparatorModule.h.

◆ t2

int ogdf::planar_separators::BFSTreeClassical::t2

private

Definition at line 353 of file PlanarSeparatorModule.h.

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

include/ogdf/graphalg/PlanarSeparatorModule.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BFSTreeClassical()

◆ ~BFSTreeClassical()

Member Function Documentation

◆ construct()

◆ createNewRoot()

◆ findLevels()

◆ findLevelsSimple()

◆ get_t0()

◆ get_t1()

◆ get_t2()

◆ getLevel()

◆ getNodesFrom()

◆ getNodesFromTo()

◆ getSeparatorLevel()

◆ getSizeOfLevel()

◆ isVisited()

◆ reconstruct()

◆ removeSeparatorLevels()

◆ restructure()

◆ visit()

Member Data Documentation

◆ belowMiddle

◆ currentLevel

◆ heightMaxIterations

◆ k

◆ levels

◆ m_ratio

◆ simple

◆ t0

◆ t1

◆ t2

Open
Graph Drawing
Framework