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.

	~PlanarAugmentationFix ()
	Destruction.

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

virtual	~AugmentationModule ()

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

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

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

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

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

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

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

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

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

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

void	connectSingleLabel ()
	Connects the remaining label.

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

void	deletePendant (node pendant)
	Deletes the given pendant.

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

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

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

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

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

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

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

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

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

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

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

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

GraphCopy	m_graphCopy
	The actual partial graph.

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

List< pa_label >	m_labels
	The list of all labels.

CombinatorialEmbedding *	m_pActEmbedding = nullptr
	The embedding of m_graphCopy.

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

CombinatorialEmbedding *	m_pEmbedding = nullptr
	The embedding of m_pGraph.

Graph *	m_pGraph = nullptr
	The working graph.

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

Detailed Description

The algorithm for biconnectivity augmentation with fixed combinatorial embedding.

Definition at line 46 of file PlanarAugmentationFix.h.

Constructor & Destructor Documentation

◆ PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::PlanarAugmentationFix ( )

inline

Creates an instance of planar augmentation with fixed embedding.

Definition at line 49 of file PlanarAugmentationFix.h.

◆ ~PlanarAugmentationFix()

ogdf::PlanarAugmentationFix::~PlanarAugmentationFix ( )

inline

Destruction.

Definition at line 52 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 98 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 92 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 95 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 83 of file PlanarAugmentationFix.h.

◆ m_graphCopy

GraphCopy ogdf::PlanarAugmentationFix::m_graphCopy

private

The actual partial graph.

Definition at line 80 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 89 of file PlanarAugmentationFix.h.

◆ m_labels

List<pa_label> ogdf::PlanarAugmentationFix::m_labels

private

The list of all labels.

Definition at line 86 of file PlanarAugmentationFix.h.

◆ m_pActEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pActEmbedding = nullptr

private

The embedding of m_graphCopy.

Definition at line 68 of file PlanarAugmentationFix.h.

◆ m_pBCTree

DynamicBCTree* ogdf::PlanarAugmentationFix::m_pBCTree = nullptr

private

The actual dynamic bc-tree.

Definition at line 77 of file PlanarAugmentationFix.h.

◆ m_pEmbedding

CombinatorialEmbedding* ogdf::PlanarAugmentationFix::m_pEmbedding = nullptr

private

The embedding of m_pGraph.

Definition at line 65 of file PlanarAugmentationFix.h.

◆ m_pGraph

Graph* ogdf::PlanarAugmentationFix::m_pGraph = nullptr

private

The working graph.

Definition at line 71 of file PlanarAugmentationFix.h.

◆ m_pResult

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

private

The inserted edges by the algorithm.

Definition at line 74 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