A node in a PC-tree that is either a P-node, C-node or leaf. More...

#include <ogdf/basic/pctree/PCNode.h>

Inheritance diagram for ogdf::pc_tree::PCNode:

Classes
struct	TempInfo
	Temporary information used during each step of the PCTree::makeConsecutive() update operation. More...

Public Types
using	LeafUserData = std::array< void , sizeof(TempInfo)/sizeof(void )>

Public Member Functions
Iterator methods
These methods allow easily walking around the PC-tree.
PCNode *	getNextSibling (const PCNode *pred) const
	Given the left or right sibling `pred`, return the adjacent sibling on the other side. More...

PCNode *	getOtherOuterChild (const PCNode *child) const
	Given one outer child, return the outer child on the other side. More...

PCNode *	getNextNeighbor (const PCNode pred, const PCNode curr) const
	Method to walk the cyclic order of all neighbors, i.e., all children plus the parent, where this node's parent is considered to be adjacent to this node's two outer children. More...

void	proceedToNextNeighbor (PCNode &pred, PCNode &curr) const
	Iteration-convenience version of getNextNeighbor() that updates the variables `pred` to `curr` and `curr` to the value returned by getNextNeighbor(pred, curr). More...

PCNode *	getParent () const

PCNodeChildrenIterable	children ()

PCNodeNeighborsIterable	neighbors (PCNode *first=nullptr)

Structure check methods
These methods help with checking the current status of this node w.r.t. its surrounding tree structure.
bool	isDetached () const

bool	isValidNode (const PCTreeForest *ofForest=nullptr) const
	Perform multiple debug checks and return `true` if getForest == `ofForest`. More...

bool	isLeaf () const

bool	isParentOf (const PCNode *other) const

bool	isSiblingOf (const PCNode *other) const

bool	isSiblingAdjacent (const PCNode *sibling) const

bool	areNeighborsAdjacent (const PCNode neigh1, const PCNode neigh2) const

bool	isChildOuter (const PCNode *child) const

bool	isOuterChild () const

Getters
size_t	index () const

PCNodeType	getNodeType () const

size_t	getChildCount () const

size_t	getDegree () const

PCNode *	getChild1 () const

PCNode *	getChild2 () const

PCNode *	getOnlyChild () const
	Check whether this node has only one child and return it. More...

PCNode *	getSibling1 () const

PCNode *	getSibling2 () const

PCTreeForest *	getForest () const

Private Member Functions
	PCNode (PCTreeForest *forest, size_t id, PCNodeType nodeType)

	~PCNode ()

Private Attributes
union {
TempInfo m_temp

LeafUserData m_userData

};

PCNode *	m_child1 = nullptr

PCNode *	m_child2 = nullptr

size_t	m_childCount = 0

PCTreeForest *	m_forest

size_t	m_id

NodeLabel	m_label = NodeLabel::Unknown

UnionFindIndex	m_nodeListIndex = UNIONFINDINDEX_EMPTY

PCNodeType	m_nodeType

UnionFindIndex	m_parentCNodeId = UNIONFINDINDEX_EMPTY

PCNode *	m_parentPNode = nullptr

PCNode *	m_sibling1 = nullptr

PCNode *	m_sibling2 = nullptr

size_t	m_timestamp = 0

Friends
std::ostream &	operator<<) (std::ostream &, const ogdf::pc_tree::PCNode *)

std::ostream &	operator<<) (std::ostream &, const ogdf::pc_tree::PCTree *)

struct	PCNodeChildrenIterable

struct	PCNodeNeighborsIterable

class	PCTree

class	PCTreeForest

Tree structure methods
These methods allow modifying the tree structure or embedding, e.g., when manually constructing a PC-tree.
void	replaceSibling (PCNode oldS, PCNode newS)
	Notify this node that one of its adjacent siblings changed. More...

void	rotateChildOutside (bool child1=true)
	Make this node an outer child of its parent. More...

void	replaceOuterChild (PCNode oldC, PCNode newC)
	Notify this node that one of its outer children was replaced. More...

void	setParent (PCNode *parent)
	Notify this node that it has a new parent. More...

void	forceDetach ()
	detach() without performing checks. More...

void	changeType (PCNodeType newType)
	Overwrite the type of this node without updating any other data structures. More...

void	appendChild (PCNode *child, bool begin=false)
	Append a (detached) child node to the begin or end of this nodes' children. More...

void	insertBetween (PCNode sib1, PCNode sib2)
	Insert a (detached) child node directly between two adjacent children of this node. More...

void	detach ()
	Detach this node from its parent. More...

void	replaceWith (PCNode *repl)
	Swaps this node inplace with a (detached) other one. More...

void	mergeIntoParent ()
	Merges this C-node into its C-node parent. More...

void	flip ()
	Reverse the stored order of children. More...

makeConsecutive-related temporary information
These methods provide access to temporary information used during a PCTree::makeConsecutive() call.
NodeLabel	getLabelUnchecked () const

void	setLabelUnchecked (NodeLabel l)

void	checkTimestamp () const

TempInfo &	tempInfo ()

size_t	addFullNeighbor (PCNode *fullNeigh)

PCNode *&	getFullNeighInsertionPoint (PCNode *nonFullNeigh)

const TempInfo &	constTempInfo () const

bool	isFull () const

NodeLabel	getLabel () const

void	setLabel (NodeLabel l)

LeafUserData &	leafUserData ()

const LeafUserData &	leafUserData () const

Detailed Description

A node in a PC-tree that is either a P-node, C-node or leaf.

See https://doi.org/10.15475/cpatp.2024 Figure 8.3 for a visualization of the doubly-linked tree structure stored in each node and more details on the changes made and temporary information stored by PCTree::makeConsecutive(). Important terminology:

child: direct descendant of this node in the tree
outer child: first or last child
sibling: other node with the same direct parent
adjacent sibling: predecessor or successor in parent's list of children
neighbors: all children and the parent

Definition at line 62 of file PCNode.h.

Member Typedef Documentation

◆ LeafUserData

using ogdf::pc_tree::PCNode::LeafUserData = std::array<void*, sizeof(TempInfo) / sizeof(void*)>

Definition at line 117 of file PCNode.h.

Constructor & Destructor Documentation

◆ PCNode()

ogdf::pc_tree::PCNode::PCNode	(	PCTreeForest *	forest,
		size_t	id,
		PCNodeType	nodeType
	)

inlineprivate

Definition at line 145 of file PCNode.h.

◆ ~PCNode()

ogdf::pc_tree::PCNode::~PCNode ( )

inlineprivate

Definition at line 154 of file PCNode.h.

Member Function Documentation

◆ addFullNeighbor()

size_t ogdf::pc_tree::PCNode::addFullNeighbor ( PCNode * fullNeigh )

inlineprivate

Definition at line 423 of file PCNode.h.

◆ appendChild()

void ogdf::pc_tree::PCNode::appendChild	(	PCNode *	child,
		bool	begin = `false`
	)

Append a (detached) child node to the begin or end of this nodes' children.

◆ areNeighborsAdjacent()

bool ogdf::pc_tree::PCNode::areNeighborsAdjacent	(	const PCNode *	neigh1,
		const PCNode *	neigh2
	)		const

Returns: true if neigh1 and neigh2 are children of this node and isSiblingAdjacent(neigh1, neigh2) is true, or if one of the passed nodes is the parent of this node and the other one is an outer child of this node

◆ changeType()

void ogdf::pc_tree::PCNode::changeType ( PCNodeType newType )

inlineprivate

Overwrite the type of this node without updating any other data structures.

Definition at line 228 of file PCNode.h.

◆ checkTimestamp()

void ogdf::pc_tree::PCNode::checkTimestamp ( ) const

private

◆ children()

PCNodeChildrenIterable ogdf::pc_tree::PCNode::children ( )

Returns: iterable for all children

◆ constTempInfo()

const TempInfo& ogdf::pc_tree::PCNode::constTempInfo ( ) const

inline

Definition at line 367 of file PCNode.h.

◆ detach()

void ogdf::pc_tree::PCNode::detach ( )

Detach this node from its parent.

Invalidates but does not change the PC-forest of the node, so don't forget to re-attach it somewhere else in a PC-tree of the same forest to make it valid again.

◆ flip()

void ogdf::pc_tree::PCNode::flip ( )

inline

Reverse the stored order of children.

Definition at line 197 of file PCNode.h.

◆ forceDetach()

void ogdf::pc_tree::PCNode::forceDetach ( )

private

detach() without performing checks.

◆ getChild1()

PCNode* ogdf::pc_tree::PCNode::getChild1 ( ) const

inline

Definition at line 460 of file PCNode.h.

◆ getChild2()

PCNode* ogdf::pc_tree::PCNode::getChild2 ( ) const

inline

Definition at line 462 of file PCNode.h.

◆ getChildCount()

size_t ogdf::pc_tree::PCNode::getChildCount ( ) const

inline

Definition at line 456 of file PCNode.h.

◆ getDegree()

size_t ogdf::pc_tree::PCNode::getDegree ( ) const

inline

Definition at line 458 of file PCNode.h.

◆ getForest()

PCTreeForest* ogdf::pc_tree::PCNode::getForest ( ) const

inline

Definition at line 476 of file PCNode.h.

◆ getFullNeighInsertionPoint()

PCNode*& ogdf::pc_tree::PCNode::getFullNeighInsertionPoint ( PCNode * nonFullNeigh )

inlineprivate

Definition at line 431 of file PCNode.h.

◆ getLabel()

NodeLabel ogdf::pc_tree::PCNode::getLabel ( ) const

inline

Definition at line 375 of file PCNode.h.

◆ getLabelUnchecked()

NodeLabel ogdf::pc_tree::PCNode::getLabelUnchecked ( ) const

inlineprivate

Definition at line 387 of file PCNode.h.

◆ getNextNeighbor()

PCNode* ogdf::pc_tree::PCNode::getNextNeighbor	(	const PCNode *	pred,
		const PCNode *	curr
	)		const

Method to walk the cyclic order of all neighbors, i.e., all children plus the parent, where this node's parent is considered to be adjacent to this node's two outer children.

The returned node is the one of the two nodes adjacent to curr in this cyclic order that is not pred, or an arbitrary one of the two if pred is null.

◆ getNextSibling()

PCNode* ogdf::pc_tree::PCNode::getNextSibling ( const PCNode * pred ) const

Given the left or right sibling pred, return the adjacent sibling on the other side.

◆ getNodeType()

PCNodeType ogdf::pc_tree::PCNode::getNodeType ( ) const

inline

Definition at line 454 of file PCNode.h.

◆ getOnlyChild()

PCNode* ogdf::pc_tree::PCNode::getOnlyChild ( ) const

inline

Check whether this node has only one child and return it.

Definition at line 467 of file PCNode.h.

◆ getOtherOuterChild()

PCNode* ogdf::pc_tree::PCNode::getOtherOuterChild ( const PCNode * child ) const

Given one outer child, return the outer child on the other side.

◆ getParent()

PCNode* ogdf::pc_tree::PCNode::getParent ( ) const

Returns: the parent node of this node, or null if this node is the root or currently detached. If the parent is a C-node, this requires a look-up in the union-find data structure.

◆ getSibling1()

PCNode* ogdf::pc_tree::PCNode::getSibling1 ( ) const

inline

Definition at line 472 of file PCNode.h.

◆ getSibling2()

PCNode* ogdf::pc_tree::PCNode::getSibling2 ( ) const

inline

Definition at line 474 of file PCNode.h.

◆ index()

size_t ogdf::pc_tree::PCNode::index ( ) const

inline

Definition at line 452 of file PCNode.h.

◆ insertBetween()

void ogdf::pc_tree::PCNode::insertBetween	(	PCNode *	sib1,
		PCNode *	sib2
	)

Insert a (detached) child node directly between two adjacent children of this node.

◆ isChildOuter()

bool ogdf::pc_tree::PCNode::isChildOuter ( const PCNode * child ) const

inline

Returns: true, if child is an outer child of this node, i.e., if this->getChild1() == child or this->getChild2() == child

Definition at line 348 of file PCNode.h.

◆ isDetached()

bool ogdf::pc_tree::PCNode::isDetached ( ) const

inline

Returns: true if this node has no parent, i.e., it is the root of its PC-tree or needs to be attached to some node first before the tree can become valid again.

Definition at line 296 of file PCNode.h.

◆ isFull()

bool ogdf::pc_tree::PCNode::isFull ( ) const

inline

Definition at line 373 of file PCNode.h.

◆ isLeaf()

bool ogdf::pc_tree::PCNode::isLeaf ( ) const

inline

Definition at line 310 of file PCNode.h.

◆ isOuterChild()

bool ogdf::pc_tree::PCNode::isOuterChild ( ) const

inline

Returns: true, if this node is an outer child of its parent, i.e., if this->getSibling1() == nullptr or this->getSibling2() == child

Definition at line 356 of file PCNode.h.

◆ isParentOf()

bool ogdf::pc_tree::PCNode::isParentOf ( const PCNode * other ) const

inline

Returns: true, if other->getParent() == this

Definition at line 315 of file PCNode.h.

◆ isSiblingAdjacent()

bool ogdf::pc_tree::PCNode::isSiblingAdjacent ( const PCNode * sibling ) const

inline

Returns: true, if this->getSibling1() == sibling or this->getSibling2() == sibling

Definition at line 333 of file PCNode.h.

◆ isSiblingOf()

bool ogdf::pc_tree::PCNode::isSiblingOf ( const PCNode * other ) const

inline

Returns: true, if this->getParent() == other->getParent()

Definition at line 324 of file PCNode.h.

◆ isValidNode()

bool ogdf::pc_tree::PCNode::isValidNode ( const PCTreeForest * ofForest = nullptr ) const

Perform multiple debug checks and return true if getForest == ofForest.

◆ leafUserData() [1/2]

LeafUserData& ogdf::pc_tree::PCNode::leafUserData ( )

inline

Returns: the user data that can be stored in leaves

Definition at line 401 of file PCNode.h.

◆ leafUserData() [2/2]

const LeafUserData& ogdf::pc_tree::PCNode::leafUserData ( ) const

inline

Returns: the user data that can be stored in leaves

Definition at line 409 of file PCNode.h.

◆ mergeIntoParent()

void ogdf::pc_tree::PCNode::mergeIntoParent ( )

Merges this C-node into its C-node parent.

◆ neighbors()

PCNodeNeighborsIterable ogdf::pc_tree::PCNode::neighbors ( PCNode * first = nullptr )

Returns: iterable for all children plus the parent, optionally selecting a starting node in this cyclic order

◆ proceedToNextNeighbor()

void ogdf::pc_tree::PCNode::proceedToNextNeighbor	(	PCNode *&	pred,
		PCNode *&	curr
	)		const

Iteration-convenience version of getNextNeighbor() that updates the variables pred to curr and curr to the value returned by getNextNeighbor(pred, curr).

◆ replaceOuterChild()

void ogdf::pc_tree::PCNode::replaceOuterChild	(	PCNode *	oldC,
		PCNode *	newC
	)

private

Notify this node that one of its outer children was replaced.

◆ replaceSibling()

void ogdf::pc_tree::PCNode::replaceSibling	(	PCNode *	oldS,
		PCNode *	newS
	)

private

Notify this node that one of its adjacent siblings changed.

◆ replaceWith()

void ogdf::pc_tree::PCNode::replaceWith ( PCNode * repl )

Swaps this node inplace with a (detached) other one.

Afterwards, this node will be detached.

◆ rotateChildOutside()

void ogdf::pc_tree::PCNode::rotateChildOutside ( bool child1 = true )

private

Make this node an outer child of its parent.

Only works for children of the root node.

◆ setLabel()

void ogdf::pc_tree::PCNode::setLabel ( NodeLabel l )

inline

Definition at line 380 of file PCNode.h.

◆ setLabelUnchecked()

void ogdf::pc_tree::PCNode::setLabelUnchecked ( NodeLabel l )

inlineprivate

Definition at line 392 of file PCNode.h.

◆ setParent()

void ogdf::pc_tree::PCNode::setParent ( PCNode * parent )

private

Notify this node that it has a new parent.

◆ tempInfo()

TempInfo& ogdf::pc_tree::PCNode::tempInfo ( )

inlineprivate

Definition at line 417 of file PCNode.h.

Friends And Related Function Documentation

◆ operator<<) [1/2]

std::ostream& operator<<)	(	std::ostream &	,
		const ogdf::pc_tree::PCNode *
	)

friend

◆ operator<<) [2/2]

std::ostream& operator<<)	(	std::ostream &	,
		const ogdf::pc_tree::PCTree *
	)

friend

◆ PCNodeChildrenIterable

friend struct PCNodeChildrenIterable

friend

Definition at line 68 of file PCNode.h.

◆ PCNodeNeighborsIterable

friend struct PCNodeNeighborsIterable

friend

Definition at line 69 of file PCNode.h.

◆ PCTree

friend class PCTree

friend

Definition at line 66 of file PCNode.h.

◆ PCTreeForest

friend class PCTreeForest

friend

Definition at line 67 of file PCNode.h.

Member Data Documentation

◆ @3

union { ... }

◆ m_child1

PCNode* ogdf::pc_tree::PCNode::m_child1 = nullptr

private

Definition at line 133 of file PCNode.h.

◆ m_child2

PCNode* ogdf::pc_tree::PCNode::m_child2 = nullptr

private

Definition at line 134 of file PCNode.h.

◆ m_childCount

size_t ogdf::pc_tree::PCNode::m_childCount = 0

private

Definition at line 135 of file PCNode.h.

◆ m_forest

PCTreeForest* ogdf::pc_tree::PCNode::m_forest

private

Definition at line 124 of file PCNode.h.

◆ m_id

size_t ogdf::pc_tree::PCNode::m_id

private

Definition at line 121 of file PCNode.h.

◆ m_label

NodeLabel ogdf::pc_tree::PCNode::m_label = NodeLabel::Unknown

mutableprivate

Definition at line 136 of file PCNode.h.

◆ m_nodeListIndex

UnionFindIndex ogdf::pc_tree::PCNode::m_nodeListIndex = UNIONFINDINDEX_EMPTY

private

Definition at line 127 of file PCNode.h.

◆ m_nodeType

PCNodeType ogdf::pc_tree::PCNode::m_nodeType

private

Definition at line 128 of file PCNode.h.

◆ m_parentCNodeId

UnionFindIndex ogdf::pc_tree::PCNode::m_parentCNodeId = UNIONFINDINDEX_EMPTY

mutableprivate

Definition at line 130 of file PCNode.h.

◆ m_parentPNode

PCNode* ogdf::pc_tree::PCNode::m_parentPNode = nullptr

private

Definition at line 129 of file PCNode.h.

◆ m_sibling1

PCNode* ogdf::pc_tree::PCNode::m_sibling1 = nullptr

private

Definition at line 131 of file PCNode.h.

◆ m_sibling2

PCNode* ogdf::pc_tree::PCNode::m_sibling2 = nullptr

private

Definition at line 132 of file PCNode.h.

◆ m_temp

TempInfo ogdf::pc_tree::PCNode::m_temp

mutable

Definition at line 141 of file PCNode.h.

◆ m_timestamp

size_t ogdf::pc_tree::PCNode::m_timestamp = 0

mutableprivate

Definition at line 137 of file PCNode.h.

◆ m_userData

LeafUserData ogdf::pc_tree::PCNode::m_userData

Definition at line 142 of file PCNode.h.

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

include/ogdf/basic/pctree/PCNode.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Tree structure methods

makeConsecutive-related temporary information

Detailed Description

Member Typedef Documentation

◆ LeafUserData

Constructor & Destructor Documentation

◆ PCNode()

◆ ~PCNode()

Member Function Documentation

◆ addFullNeighbor()

◆ appendChild()

◆ areNeighborsAdjacent()

◆ changeType()

◆ checkTimestamp()

◆ children()

◆ constTempInfo()

◆ detach()

◆ flip()

◆ forceDetach()

◆ getChild1()

◆ getChild2()

◆ getChildCount()

◆ getDegree()

◆ getForest()

◆ getFullNeighInsertionPoint()

◆ getLabel()

◆ getLabelUnchecked()

◆ getNextNeighbor()

◆ getNextSibling()

◆ getNodeType()

◆ getOnlyChild()

◆ getOtherOuterChild()

◆ getParent()

◆ getSibling1()

◆ getSibling2()

◆ index()

◆ insertBetween()

◆ isChildOuter()

◆ isDetached()

◆ isFull()

◆ isLeaf()

◆ isOuterChild()

◆ isParentOf()

◆ isSiblingAdjacent()

◆ isSiblingOf()

◆ isValidNode()

◆ leafUserData() [1/2]

◆ leafUserData() [2/2]

◆ mergeIntoParent()

◆ neighbors()

◆ proceedToNextNeighbor()

◆ replaceOuterChild()

◆ replaceSibling()

◆ replaceWith()

◆ rotateChildOutside()

◆ setLabel()

◆ setLabelUnchecked()

◆ setParent()

◆ tempInfo()

Friends And Related Function Documentation

◆ operator<<) [1/2]

◆ operator<<) [2/2]

◆ PCNodeChildrenIterable

◆ PCNodeNeighborsIterable

◆ PCTree

◆ PCTreeForest

Member Data Documentation

◆ @3

◆ m_child1

◆ m_child2

◆ m_childCount

◆ m_forest

◆ m_id

Open
Graph Drawing
Framework