Auxiliary data structure to represent Cycles in planar graphs. More...

#include <ogdf/graphalg/PlanarSeparatorModule.h>

Classes
class	Iterator
	Special iterator to walk over the inward-pointing edges of the cycle. More...

Public Member Functions
	Cycle (BFSTree *tree, edge startEdge)
	Constructor.

	Cycle (Cycle &&other)

Cycle	expandCycle ()
	Expands the cycle, as described by Lipton and Tarjan 1979, by examining the triangle adjacent to the current expand edge on the inside of the cycle and integrating it into the cycle.

void	fillLists (List< node > &separator, List< node > &first, List< node > &second, bool useRoot=false)
	Fills the lists of nodes, by putting all nodes on this cycle into the list of separator nodes and putting the nodes on the sides of the cycle into first and second, respectively.

bool	getClockwise () const
	Checks if the cycle is clockwise, i.e.

const List< adjEntry > &	getEdges () const
	Gets the adjEntries on the cycle.

int	getInsideCost () const
	Gets the cost on the inside of the cycle.

const List< node > &	getNodes () const
	Gets the nodes on the cycle.

int	getOutsideCost () const
	Gets the cost on the outside of the cycle.

const node &	getRoot () const
	Gives access to the root node of the cycle.

int	getSize () const
	Returns the size of the cycle = the number of nodes on the cycle.

Cycle &	operator= (Cycle &&other)

void	print () const
	Utility method for printing the cycle to the console.

Private Member Functions
	Cycle (BFSTree *tree, bool clockwise)
	Constructor.

	Cycle (BFSTree *tree, List< node > &nodeList, List< adjEntry > &edgeList, node root, bool clockwise)
	Constructor.

Iterator	begin () const
	Iterators for clockwise iteration over edges on the "inside", starting and ending at currentExpandEdge.

void	collectChildrenOfNode (const node no, NodeArray< bool > &marked, List< node > &list, bool useRoot=false) const
	Recursively creates a list containing all descendants of a node.

void	computeCosts ()
	Computes the costs on both sides of the cycle.

Iterator	end () const

Cycle	expandWithoutTreeEdges (node y, const node v, const node w, const adjEntry vy, const adjEntry yw)
	Expand the cycle if none of the inner edges of the triangle is a tree edge.

void	expandWithTreeEdge (node y, node v, node w, adjEntry vy, adjEntry yw)
	Expand the Cycle when one of the inner edges of the triangle is a tree edge.

bool	findAlphaCycle (Cycle &cyc, const List< node > &pathNodes, const List< adjEntry > &pathAdjEntries, const node z, const node propRoot, const adjEntry yw, List< node > &oldNodes, List< adjEntry > &oldEdges) const
	Used during expansion without tree edges.

void	findBetaCycle (Cycle &cyc, const List< node > &pathNodes, const List< adjEntry > &pathAdjEntries, const node z, const node propRoot, const adjEntry vy, List< node > &oldNodes, List< adjEntry > &oldEdges, bool foundRootOnAlpha) const
	Used during expansion without tree edges.

std::pair< node, node >	findPathToCycle (node &y, List< node > &pathNodes, List< adjEntry > &pathAdjEntries) const
	Used during expansion without tree edges.

adjEntry	getCurrentExpandEdge () const
	Gets the current non-tree edge on the cycle, which is the one that will be used to expand the cycle further.

void	increaseCost (adjEntry adj, bool clockwise)
	Increases the cost on the inside of this cycle by following the given adjEntry and adding the cost of the node on the other end of the adjEntry.

void	init (List< node > &nodeList, List< adjEntry > &edgeList, node root)
	Initializes the cycle (used by constructors).

void	popBackEdge ()

void	popBackNode ()
	Access methods for adding and removing nodes from the cycle.

void	popFrontEdge ()

void	popFrontNode ()

void	pushFrontEdge (adjEntry adj)

Private Attributes
int	costClock {0}

int	costCounter {0}

node	cycleRoot

List< adjEntry >	edges

bool	isClockwise

EdgeArray< bool >	isEdgeOnCycle

NodeArray< bool >	isOnCycle

List< node >	nodes

BFSTree *	tree

Detailed Description

Auxiliary data structure to represent Cycles in planar graphs.

Definition at line 526 of file PlanarSeparatorModule.h.

Constructor & Destructor Documentation

◆ Cycle() [1/4]

ogdf::planar_separators::Cycle::Cycle	(	BFSTree *	tree,
		edge	startEdge
	)

Constructor.

Cycles are created from a tree and a non-tree edge.

Parameters

tree	the tree
startEdge	the non-tree start edge

◆ Cycle() [2/4]

ogdf::planar_separators::Cycle::Cycle ( Cycle && other )

inline

Definition at line 553 of file PlanarSeparatorModule.h.

◆ Cycle() [3/4]

ogdf::planar_separators::Cycle::Cycle	(	BFSTree *	tree,
		List< node > &	nodeList,
		List< adjEntry > &	edgeList,
		node	root,
		bool	clockwise
	)

private

Constructor.

Creates a Cycle from a complete description (used by the expansion procedure)

Parameters

tree	the tree to create this cycle from
nodeList	list of nodes that should be on the cycle
edgeList	list of adjEntries that should be on the cycle
root	the root node of the cycle (= node with lowest level)
clockwise	whether the cycle is clockwise or not

◆ Cycle() [4/4]

ogdf::planar_separators::Cycle::Cycle	(	BFSTree *	tree,
		bool	clockwise
	)

private

Constructor.

Creates an empty cycle (used only during the expansion procedure).

Parameters

tree	the tree
clockwise	whether the cycle is clockwise

Member Function Documentation

◆ begin()

Iterator ogdf::planar_separators::Cycle::begin ( ) const

inlineprivate

Iterators for clockwise iteration over edges on the "inside", starting and ending at currentExpandEdge.

Definition at line 780 of file PlanarSeparatorModule.h.

◆ collectChildrenOfNode()

void ogdf::planar_separators::Cycle::collectChildrenOfNode	(	const node	no,
		NodeArray< bool > &	marked,
		List< node > &	list,
		bool	useRoot = `false`
	)		const

private

Recursively creates a list containing all descendants of a node.

Collects the nodes in the original graph, not those in the copy.

Parameters

no	the node whose children should be collected
marked	holds which nodes were visited already
list	the list containing all children
useRoot	whether to treat the root as a normal node or not

◆ computeCosts()

void ogdf::planar_separators::Cycle::computeCosts ( )

private

Computes the costs on both sides of the cycle.

Costs are stored in the respective variables.

◆ end()

Iterator ogdf::planar_separators::Cycle::end ( ) const

inlineprivate

Definition at line 782 of file PlanarSeparatorModule.h.

◆ expandCycle()

Cycle ogdf::planar_separators::Cycle::expandCycle ( )

Expands the cycle, as described by Lipton and Tarjan 1979, by examining the triangle adjacent to the current expand edge on the inside of the cycle and integrating it into the cycle.

Returns: the new, expanded cycle

◆ expandWithoutTreeEdges()

Cycle ogdf::planar_separators::Cycle::expandWithoutTreeEdges	(	node	y,
		const node	v,
		const node	w,
		const adjEntry	vy,
		const adjEntry	yw
	)

private

Expand the cycle if none of the inner edges of the triangle is a tree edge.

This method does not change this cycle, but creates a new one (because during the process, two candidates are created and one of them is selected).

Parameters

y	the tip of the triangle, inside of the cycle
v	the starting point of the triangle-edge
w	the end point of the triangle-edge
vy	the edge that leads to the tip
yw	the edge that leads away from the tip

Returns: the next cycle

◆ expandWithTreeEdge()

void ogdf::planar_separators::Cycle::expandWithTreeEdge	(	node	y,
		node	v,
		node	w,
		adjEntry	vy,
		adjEntry	yw
	)

private

Expand the Cycle when one of the inner edges of the triangle is a tree edge.

This method changes this cycle to expand it.

Parameters

y	the tip of the triangle, inside of the cycle
v	the starting point of the triangle-edge
w	the end point of the triangle-edge
vy	the edge that leads to the tip
yw	the edge that leads away from the tip

◆ fillLists()

void ogdf::planar_separators::Cycle::fillLists	(	List< node > &	separator,
		List< node > &	first,
		List< node > &	second,
		bool	useRoot = `false`
	)

Fills the lists of nodes, by putting all nodes on this cycle into the list of separator nodes and putting the nodes on the sides of the cycle into first and second, respectively.

(Of course only once a suitable cycle is found).

Parameters

separator	the separator nodes
first	the first component
second	the second component
useRoot	whether to add the root node as well - sometimes, the root node is artificial and should be ignored instead of being added

◆ findAlphaCycle()

bool ogdf::planar_separators::Cycle::findAlphaCycle	(	Cycle &	cyc,
		const List< node > &	pathNodes,
		const List< adjEntry > &	pathAdjEntries,
		const node	z,
		const node	propRoot,
		const adjEntry	yw,
		List< node > &	oldNodes,
		List< adjEntry > &	oldEdges
	)		const

private

Used during expansion without tree edges.

Finds the first cycle bounded by the path from y to z and the cycle itself.

Parameters

cyc	the original cycle
pathNodes	the nodes on the path from y to z
pathAdjEntries	the adjEntries on the path from y to z
z	the node z where the path meets the cycle
propRoot	the proposed root node = the root node of the old cycle, which may be improved on
yw	the side of the triangle
oldNodes	nodes on old cycle
oldEdges	edges on old cycle

Returns: whether we found the root node of the original cycle on our way from w to z

◆ findBetaCycle()

void ogdf::planar_separators::Cycle::findBetaCycle	(	Cycle &	cyc,
		const List< node > &	pathNodes,
		const List< adjEntry > &	pathAdjEntries,
		const node	z,
		const node	propRoot,
		const adjEntry	vy,
		List< node > &	oldNodes,
		List< adjEntry > &	oldEdges,
		bool	foundRootOnAlpha
	)		const

private

Used during expansion without tree edges.

Finds the second cycle bounded by the path from y to z and the cycle itself.

Parameters

cyc	the original cycle
pathNodes	the nodes on the path from y to z
pathAdjEntries	the adjEntries on the path from y to z
z	the node z where the path meets the cycle
propRoot	the proposed root node = the root node of the old cycle, which may be improved on
vy	the side of the triangle
oldNodes	nodes on old cycle
oldEdges	edges on old cycle
foundRootOnAlpha	whether the alpha cycle found the old root node

◆ findPathToCycle()

std::pair< node, node > ogdf::planar_separators::Cycle::findPathToCycle	(	node &	y,
		List< node > &	pathNodes,
		List< adjEntry > &	pathAdjEntries
	)		const

private

Used during expansion without tree edges.

Finds a path from y back to the cycle by following parent pointers. Returns a pair of nodes (z, r) where z = the node on the cycle in which the path beginning at y enters the cycle, and r = the node on the cycle with the shortest distance to overall root

Parameters

y	the tip of the triangle
pathNodes	the nodes on the path
pathAdjEntries	the adjEntries on the path

Returns: nodes (z, r)

◆ getClockwise()

bool ogdf::planar_separators::Cycle::getClockwise ( ) const

inline

Checks if the cycle is clockwise, i.e.

you get the inward-pointing edges of each node on the cycle by rotating clockwise from cycle-edge to cycle-edge.

Returns: true if the cycle is clockwise

Definition at line 580 of file PlanarSeparatorModule.h.

◆ getCurrentExpandEdge()

adjEntry ogdf::planar_separators::Cycle::getCurrentExpandEdge ( ) const

private

Gets the current non-tree edge on the cycle, which is the one that will be used to expand the cycle further.

Returns: the current non-tree edge

◆ getEdges()

const List< adjEntry > & ogdf::planar_separators::Cycle::getEdges ( ) const

inline

Gets the adjEntries on the cycle.

Returns: read-only list of adjEntries

Definition at line 594 of file PlanarSeparatorModule.h.

◆ getInsideCost()

int ogdf::planar_separators::Cycle::getInsideCost ( ) const

Gets the cost on the inside of the cycle.

(=the number of nodes on the inside of the cycle, where the inside is defined as the larger side.)

Returns: the inside cost

◆ getNodes()

const List< node > & ogdf::planar_separators::Cycle::getNodes ( ) const

inline

Gets the nodes on the cycle.

Returns: read-only list of nodes

Definition at line 587 of file PlanarSeparatorModule.h.

◆ getOutsideCost()

int ogdf::planar_separators::Cycle::getOutsideCost ( ) const

Gets the cost on the outside of the cycle.

(=the number of nodes on the outside of the cycle, where the inside is defined as the larger side.)

Returns: the inside cost

◆ getRoot()

const node & ogdf::planar_separators::Cycle::getRoot ( ) const

inline

Gives access to the root node of the cycle.

Returns: read-only access to the root node

Definition at line 601 of file PlanarSeparatorModule.h.

◆ getSize()

int ogdf::planar_separators::Cycle::getSize ( ) const

inline

Returns the size of the cycle = the number of nodes on the cycle.

Returns: the size

Definition at line 572 of file PlanarSeparatorModule.h.

◆ increaseCost()

void ogdf::planar_separators::Cycle::increaseCost	(	adjEntry	adj,
		bool	clockwise
	)

private

Increases the cost on the inside of this cycle by following the given adjEntry and adding the cost of the node on the other end of the adjEntry.

Parameters

adj	the adjEntry whose cost should be added
clockwise	whether the cost should be added to the clockwise cost

◆ init()

void ogdf::planar_separators::Cycle::init	(	List< node > &	nodeList,
		List< adjEntry > &	edgeList,
		node	root
	)

private

Initializes the cycle (used by constructors).

Parameters

nodeList	the list of nodes on the cycle
edgeList	the list of adjEntries on the cycle
root	the root node of the cycle

◆ operator=()

Cycle & ogdf::planar_separators::Cycle::operator= ( Cycle && other )

inline

Definition at line 536 of file PlanarSeparatorModule.h.

◆ popBackEdge()

void ogdf::planar_separators::Cycle::popBackEdge ( )

private

◆ popBackNode()

void ogdf::planar_separators::Cycle::popBackNode ( )

private

Access methods for adding and removing nodes from the cycle.

◆ popFrontEdge()

void ogdf::planar_separators::Cycle::popFrontEdge ( )

private

◆ popFrontNode()

void ogdf::planar_separators::Cycle::popFrontNode ( )

private

◆ print()

void ogdf::planar_separators::Cycle::print ( ) const

Utility method for printing the cycle to the console.

For debugging only.

◆ pushFrontEdge()

void ogdf::planar_separators::Cycle::pushFrontEdge ( adjEntry adj )

private

Member Data Documentation

◆ costClock

int ogdf::planar_separators::Cycle::costClock {0}

private

Definition at line 747 of file PlanarSeparatorModule.h.

◆ costCounter

int ogdf::planar_separators::Cycle::costCounter {0}

private

Definition at line 748 of file PlanarSeparatorModule.h.

◆ cycleRoot

node ogdf::planar_separators::Cycle::cycleRoot

private

Definition at line 745 of file PlanarSeparatorModule.h.

◆ edges

List<adjEntry> ogdf::planar_separators::Cycle::edges

private

Definition at line 741 of file PlanarSeparatorModule.h.

◆ isClockwise

bool ogdf::planar_separators::Cycle::isClockwise

private

Definition at line 749 of file PlanarSeparatorModule.h.

◆ isEdgeOnCycle

EdgeArray<bool> ogdf::planar_separators::Cycle::isEdgeOnCycle

private

Definition at line 743 of file PlanarSeparatorModule.h.

◆ isOnCycle

NodeArray<bool> ogdf::planar_separators::Cycle::isOnCycle

private

Definition at line 742 of file PlanarSeparatorModule.h.

◆ nodes

List<node> ogdf::planar_separators::Cycle::nodes

private

Definition at line 740 of file PlanarSeparatorModule.h.

◆ tree

BFSTree* ogdf::planar_separators::Cycle::tree

private

Definition at line 738 of file PlanarSeparatorModule.h.

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

include/ogdf/graphalg/PlanarSeparatorModule.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Cycle() [1/4]

◆ Cycle() [2/4]

◆ Cycle() [3/4]

◆ Cycle() [4/4]

Member Function Documentation

◆ begin()

◆ collectChildrenOfNode()

◆ computeCosts()

◆ end()

◆ expandCycle()

◆ expandWithoutTreeEdges()

◆ expandWithTreeEdge()

◆ fillLists()

◆ findAlphaCycle()

◆ findBetaCycle()

◆ findPathToCycle()

◆ getClockwise()

◆ getCurrentExpandEdge()

◆ getEdges()

◆ getInsideCost()

◆ getNodes()

◆ getOutsideCost()

◆ getRoot()

◆ getSize()

◆ increaseCost()

◆ init()

◆ operator=()

◆ popBackEdge()

◆ popBackNode()

◆ popFrontEdge()

◆ popFrontNode()

◆ print()

◆ pushFrontEdge()

Member Data Documentation

◆ costClock

◆ costCounter

◆ cycleRoot

◆ edges

◆ isClockwise

◆ isEdgeOnCycle

◆ isOnCycle

◆ nodes

◆ tree

Open
Graph Drawing
Framework