The algorithm for biconnectivity augmentation with fixed combinatorial embedding. More...

#include <ogdf/augmentation/PlanarAugmentationFix.h>

Inheritance diagram for ogdf::PlanarAugmentationFix:

Public Member Functions
	PlanarAugmentationFix ()
	Creates an instance of planar augmentation with fixed embedding. More...

	~PlanarAugmentationFix ()
	Destruction. More...

Public Member Functions inherited from ogdf::AugmentationModule
	AugmentationModule ()
	Initializes an augmentation module. More...

virtual	~AugmentationModule ()

void	call (Graph &G)
	Calls the augmentation module for graph `G`. More...

void	call (Graph &G, List< edge > &L)
	Calls the augmentation module for graph `G`. More...

int	numberOfAddedEdges () const
	Returns the number of added edges. More...

void	operator() (Graph &G)
	Calls the augmentation module for graph `G`. More...

void	operator() (Graph &G, List< edge > &L)
	Calls the augmentation module for graph `G`. More...

Protected Member Functions
virtual void	doCall (Graph &g, List< edge > &list) override
	The implementation of the algorithm call. More...

Private Member Functions
void	addPendant (node pendant, pa_label &label)
	Adds `pendant` to `label`. More...

void	augment (adjEntry adjOuterFace)
	The main function for planar augmentation. More...

void	changeBCRoot (node oldRoot, node newRoot)
	Exchanges `oldRoot` by `newRoot` and updates data structurs in the bc-tree. More...

void	connectPendants (node pendant1, node pendant2, adjEntry adjV1, adjEntry adjV2)
	Connects the two pendants. More...

void	connectSingleLabel ()
	Connects the remaining label. More...

void	deleteLabel (pa_label &label)
	Deletes the given label. More...

void	deletePendant (node pendant)
	Deletes the given pendant. More...

bool	findMatching (node &pendant1, node &pendant2, adjEntry &v1, adjEntry &v2)
	Finds the next matching pendants. More...

void	findMatchingRev (node &pendant1, node &pendant2, adjEntry &v1, adjEntry &v2)
	Called by findMatching, if a dominating tree was detected. More...

PALabel::StopCause	followPath (node v, node &last)
	Traverses upwards in the bc-tree, starting at the pendant node `v`. More...

ListIterator< pa_label >	insertLabel (pa_label label)
	Inserts `label` into the list of labels maintaining decreasing order. More...

void	modifyBCRoot (node oldRoot, node newRoot)
	Modifies the root of the bc-tree. More...

pa_label	newLabel (node cutvertex, node parent, node pendant, PALabel::StopCause whyStop)
	Creates a new label. More...

void	reduceChain (node pendant)
	Adds `pendant` to a label or creates one. More...

void	removeLabel (pa_label &label)
	Removes the given label from the list of labels. More...

Private Attributes
node	m_actBCRoot
	The actual root of the bc-tree. More...

NodeArray< pa_label >	m_belongsTo
	Array that contains the label a node belongs to. More...

NodeArray< ListIterator< node > >	m_belongsToIt
	Array that contains the iterator of the label a node belongs to. More...

EdgeArray< edge >	m_eCopy
	Edge-array required for construction of the graph copy. More...

GraphCopy	m_graphCopy
	The actual partial graph. More...

NodeArray< ListIterator< pa_label > >	m_isLabel
	Array that contains iterators to the list of labels if a node is a parent of a label. More...

List< pa_label >	m_labels
	The list of all labels. More...

CombinatorialEmbedding *	m_pActEmbedding = nullptr
	The embedding of m_graphCopy. More...

DynamicBCTree *	m_pBCTree = nullptr
	The actual dynamic bc-tree. More...

CombinatorialEmbedding *	m_pEmbedding = nullptr
	The embedding of m_pGraph. More...

Graph *	m_pGraph = nullptr
	The working graph. More...

List< edge > *	m_pResult = nullptr
	The inserted edges by the algorithm. More...

Detailed Description

The algorithm for biconnectivity augmentation with fixed combinatorial embedding.

Definition at line 50 of file PlanarAugmentationFix.h.

Constructor & Destructor Documentation

◆ PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::PlanarAugmentationFix ( )

inline

Creates an instance of planar augmentation with fixed embedding.

Definition at line 53 of file PlanarAugmentationFix.h.

◆ ~PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::~PlanarAugmentationFix ( )

inline

Destruction.

Definition at line 56 of file PlanarAugmentationFix.h.

Member Function Documentation

◆ addPendant()

void ogdf::PlanarAugmentationFix::addPendant	(	node	pendant,
		pa_label &	label
	)

private

Adds pendant to label.

◆ augment()

void ogdf::PlanarAugmentationFix::augment ( adjEntry adjOuterFace )

private

The main function for planar augmentation.

◆ changeBCRoot()

void ogdf::PlanarAugmentationFix::changeBCRoot	(	node	oldRoot,
		node	newRoot
	)

private

Exchanges oldRoot by newRoot and updates data structurs in the bc-tree.

◆ connectPendants()

void ogdf::PlanarAugmentationFix::connectPendants	(	node	pendant1,
		node	pendant2,
		adjEntry	adjV1,
		adjEntry	adjV2
	)

private

Connects the two pendants.

◆ connectSingleLabel()

void ogdf::PlanarAugmentationFix::connectSingleLabel ( )

private

Connects the remaining label.

◆ deleteLabel()

void ogdf::PlanarAugmentationFix::deleteLabel ( pa_label & label )

private

Deletes the given label.

◆ deletePendant()

void ogdf::PlanarAugmentationFix::deletePendant ( node pendant )

private

Deletes the given pendant.

◆ doCall()

virtual void ogdf::PlanarAugmentationFix::doCall	(	Graph &	g,
		List< edge > &	list
	)

overrideprotectedvirtual

The implementation of the algorithm call.

Parameters

g	is the working graph.
list	is the list of all new edges.

Implements ogdf::AugmentationModule.

◆ findMatching()

bool ogdf::PlanarAugmentationFix::findMatching	(	node &	pendant1,
		node &	pendant2,
		adjEntry &	v1,
		adjEntry &	v2
	)

private

Finds the next matching pendants.

◆ findMatchingRev()

void ogdf::PlanarAugmentationFix::findMatchingRev	(	node &	pendant1,
		node &	pendant2,
		adjEntry &	v1,
		adjEntry &	v2
	)

private

Called by findMatching, if a dominating tree was detected.

◆ followPath()

PALabel::StopCause ogdf::PlanarAugmentationFix::followPath	(	node	v,
		node &	last
	)

private

Traverses upwards in the bc-tree, starting at the pendant node v.

◆ insertLabel()

ListIterator<pa_label> ogdf::PlanarAugmentationFix::insertLabel ( pa_label label )

private

Inserts label into the list of labels maintaining decreasing order.

◆ modifyBCRoot()

void ogdf::PlanarAugmentationFix::modifyBCRoot	(	node	oldRoot,
		node	newRoot
	)

private

Modifies the root of the bc-tree.

◆ newLabel()

pa_label ogdf::PlanarAugmentationFix::newLabel	(	node	cutvertex,
		node	parent,
		node	pendant,
		PALabel::StopCause	whyStop
	)

private

Creates a new label.

◆ reduceChain()

void ogdf::PlanarAugmentationFix::reduceChain ( node pendant )

private

Adds pendant to a label or creates one.

◆ removeLabel()

void ogdf::PlanarAugmentationFix::removeLabel ( pa_label & label )

private

Removes the given label from the list of labels.

Member Data Documentation

◆ m_actBCRoot

node ogdf::PlanarAugmentationFix::m_actBCRoot

private

The actual root of the bc-tree.

Definition at line 102 of file PlanarAugmentationFix.h.

◆ m_belongsTo

NodeArray<pa_label> ogdf::PlanarAugmentationFix::m_belongsTo

private

Array that contains the label a node belongs to.

Definition at line 96 of file PlanarAugmentationFix.h.

◆ m_belongsToIt

NodeArray<ListIterator<node> > ogdf::PlanarAugmentationFix::m_belongsToIt

private

Array that contains the iterator of the label a node belongs to.

Definition at line 99 of file PlanarAugmentationFix.h.

◆ m_eCopy

EdgeArray<edge> ogdf::PlanarAugmentationFix::m_eCopy

private

Edge-array required for construction of the graph copy.

Definition at line 87 of file PlanarAugmentationFix.h.

◆ m_graphCopy

GraphCopy ogdf::PlanarAugmentationFix::m_graphCopy

private

The actual partial graph.

Definition at line 84 of file PlanarAugmentationFix.h.

◆ m_isLabel

NodeArray<ListIterator<pa_label> > ogdf::PlanarAugmentationFix::m_isLabel

private

Array that contains iterators to the list of labels if a node is a parent of a label.

Definition at line 93 of file PlanarAugmentationFix.h.

◆ m_labels

List<pa_label> ogdf::PlanarAugmentationFix::m_labels

private

The list of all labels.

Definition at line 90 of file PlanarAugmentationFix.h.

◆ m_pActEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pActEmbedding = nullptr

private

The embedding of m_graphCopy.

Definition at line 72 of file PlanarAugmentationFix.h.

◆ m_pBCTree

DynamicBCTree* ogdf::PlanarAugmentationFix::m_pBCTree = nullptr

private

The actual dynamic bc-tree.

Definition at line 81 of file PlanarAugmentationFix.h.

◆ m_pEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pEmbedding = nullptr

private

The embedding of m_pGraph.

Definition at line 69 of file PlanarAugmentationFix.h.

◆ m_pGraph

Graph* ogdf::PlanarAugmentationFix::m_pGraph = nullptr

private

The working graph.

Definition at line 75 of file PlanarAugmentationFix.h.

◆ m_pResult

List<edge>* ogdf::PlanarAugmentationFix::m_pResult = nullptr

private

The inserted edges by the algorithm.

Definition at line 78 of file PlanarAugmentationFix.h.

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

include/ogdf/augmentation/PlanarAugmentationFix.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PlanarAugmentationFix()

◆ ~PlanarAugmentationFix()

Member Function Documentation

◆ addPendant()

◆ augment()

◆ changeBCRoot()

◆ connectPendants()

◆ connectSingleLabel()

◆ deleteLabel()

◆ deletePendant()

◆ doCall()

◆ findMatching()

◆ findMatchingRev()

◆ followPath()

◆ insertLabel()

◆ modifyBCRoot()

◆ newLabel()

◆ reduceChain()

◆ removeLabel()

Member Data Documentation

◆ m_actBCRoot

◆ m_belongsTo

◆ m_belongsToIt

◆ m_eCopy

◆ m_graphCopy

◆ m_isLabel

◆ m_labels

◆ m_pActEmbedding

◆ m_pBCTree

◆ m_pEmbedding

◆ m_pGraph

◆ m_pResult

Open
Graph Drawing
Framework