The algorithm for planar biconnectivity augmentation (Mutzel, Fialko). More...

#include <ogdf/augmentation/PlanarAugmentation.h>

Inheritance diagram for ogdf::PlanarAugmentation:

Public Member Functions
	PlanarAugmentation ()
	Creates an instance of the planar augmentation algorithm.

	~PlanarAugmentation ()
	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` and updates the label-order.

node	adjToCutvertex (node v, node cutvertex=nullptr)
	Returns a node that belongs to bc-node `v` and is adjacent to `cutvertex`.

void	augment ()
	The main function for planar augmentation.

bool	connectCondition (pa_label a, pa_label b)
	Checks if the pendants of label `a` and label `b` can be connected without creating a new pendant.

void	connectInsideLabel (pa_label &label)
	Connects the only pendant of `label` with a computed ancestor.

void	connectLabels (pa_label first, pa_label second)
	Inserts edges between pendants of label `first` and `second`.

edge	connectPendants (node pendant1, node pendant2)
	Connects two pendants.

void	deleteLabel (pa_label &label, bool removePendants=true)
	Deletes `label`.

void	deletePendant (node pendant, bool removeFromLabel=true)
	Deletes the pendant `pendant`, and, if `removeFromLabel` is true, removes it from the corresponding label and updates the label-order.

node	findLastBefore (node pendant, node ancestor)
	Traverses from `pendant` to `ancestor` and returns the last node before ancestor on the path.

bool	findMatching (pa_label &first, pa_label &second)
	Finds two matching labels, so all pendants can be connected without losing planarity.

PALabel::StopCause	followPath (node v, node &last)
	Traverses to the root and checks several stop conditions.

ListIterator< pa_label >	insertLabel (pa_label label)
	Inserts `label` into m_labels by decreasing order.

void	joinPendants (pa_label &label)
	Connects all pendants of `label` with new edges.

void	makeConnectedByPendants ()
	Makes the graph connected by new edges between pendants of the connected components.

void	modifyBCRoot (node oldRoot, node newRoot)
	Modifies the root of the BC-Tree that `newRoot` replaces `oldRoot`.

pa_label	newLabel (node cutvertex, node pendant, PALabel::StopCause whyStop)
	Creates a new label and inserts it into m_labels.

bool	planarityCheck (node v1, node v2)
	Checks planarity for a new edge (`v1`, `v2`) in the original graph.

void	reduceChain (node pendant, pa_label labelOld=nullptr)
	Traverses to the root and creates a label or updates one.

void	removeAllPendants (pa_label &label)
	Removes all pendants of `label`.

void	terminate ()
	Cleanup.

void	updateAdjNonChildren (node newBlock, SList< node > &path)
	Updates m_adjNonChildren.

void	updateNewEdges (const SList< edge > &newEdges)
	Major updates caused by the new edges.

Private Attributes
NodeArray< SList< adjEntry > >	m_adjNonChildren
	Stores for each node of the bc-tree the children that have an adjacent bc-node that doesn't belong to the same parent-node.

NodeArray< pa_label >	m_belongsTo
	The label a BC-Node belongs to.

NodeArray< ListIterator< pa_label > >	m_isLabel
	The list iterator in m_labels if the node in the BC-Tree is a label.

List< pa_label >	m_labels
	The list of all labels, sorted by size (decreasing).

int	m_nPlanarityTests = 0
	The number of planarity tests.

DynamicBCTree *	m_pBCTree = nullptr
	The corresponding BC-Tree.

List< node >	m_pendants
	The list of all pendants (leaves in the BC-Tree).

List< node >	m_pendantsToDel
	The list of pendants that has to be deleted after each reduceChain.

Graph *	m_pGraph = nullptr
	The working graph.

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

Detailed Description

The algorithm for planar biconnectivity augmentation (Mutzel, Fialko).

The class PlanarAugmentation implements an augmentation algorithm that augments a graph to a biconnected graph. In addition, if the graph was planar before augmentation, the resulting graph will be biconnected and planar. The algorithm uses (dynamic) BC-trees and achieves biconnectivity by inserting edges between nodes of pendants (that are leaves in the bc-tree). The guaranteed approximation-quality is 5/3.

The implementation is based on the following publication:

Sergej Fialko, Petra Mutzel: A New Approximation Algorithm for the Planar Augmentation Problem. Proc. SODA 1998, pp. 260-269.

Definition at line 62 of file PlanarAugmentation.h.

Constructor & Destructor Documentation

◆ PlanarAugmentation()

ogdf::PlanarAugmentation::PlanarAugmentation ( )

inline

Creates an instance of the planar augmentation algorithm.

Definition at line 65 of file PlanarAugmentation.h.

◆ ~PlanarAugmentation()

ogdf::PlanarAugmentation::~PlanarAugmentation ( )

inline

Destruction.

Definition at line 68 of file PlanarAugmentation.h.

Member Function Documentation

◆ addPendant()

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

private

Adds pendant to label and updates the label-order.

◆ adjToCutvertex()

node ogdf::PlanarAugmentation::adjToCutvertex	(	node	v,
		node	cutvertex = `nullptr`
	)

private

Returns a node that belongs to bc-node v and is adjacent to cutvertex.

Parameters

v	is a node in the BC-Tree.
cutvertex	is the last cut-vertex found.

Returns: a node of the original graph.

◆ augment()

void ogdf::PlanarAugmentation::augment ( )

private

The main function for planar augmentation.

◆ connectCondition()

bool ogdf::PlanarAugmentation::connectCondition	(	pa_label	a,
		pa_label	b
	)

private

Checks if the pendants of label a and label b can be connected without creating a new pendant.

◆ connectInsideLabel()

void ogdf::PlanarAugmentation::connectInsideLabel ( pa_label & label )

private

Connects the only pendant of label with a computed ancestor.

◆ connectLabels()

void ogdf::PlanarAugmentation::connectLabels	(	pa_label	first,
		pa_label	second
	)

private

Inserts edges between pendants of label first and second.

Precondition: first.size() is greater than second.size() or equal.

◆ connectPendants()

edge ogdf::PlanarAugmentation::connectPendants	(	node	pendant1,
		node	pendant2
	)

private

Connects two pendants.

Returns: the new edge in the original graph.

◆ deleteLabel()

void ogdf::PlanarAugmentation::deleteLabel	(	pa_label &	label,
		bool	removePendants = `true`
	)

private

Deletes label.

◆ deletePendant()

void ogdf::PlanarAugmentation::deletePendant	(	node	pendant,
		bool	removeFromLabel = `true`
	)

private

Deletes the pendant pendant, and, if removeFromLabel is true, removes it from the corresponding label and updates the label-order.

◆ doCall()

virtual void ogdf::PlanarAugmentation::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.

◆ findLastBefore()

node ogdf::PlanarAugmentation::findLastBefore	(	node	pendant,
		node	ancestor
	)

private

Traverses from pendant to ancestor and returns the last node before ancestor on the path.

◆ findMatching()

bool ogdf::PlanarAugmentation::findMatching	(	pa_label &	first,
		pa_label &	second
	)

private

Finds two matching labels, so all pendants can be connected without losing planarity.

Parameters

first	is the label with maximum size, modified by the function.
second	is the matching label, modified by the function: 0 if no matching is found.

Returns: true iff a matching label is found.

◆ followPath()

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

private

Traverses to the root and checks several stop conditions.

Is called by reduceChain.

Parameters

v	is a node of the BC-Tree.
last	is the last found C-vertex in the BC-Tree, is modified by the method.

Returns: the stop-cause.

◆ insertLabel()

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

private

Inserts label into m_labels by decreasing order.

Returns: the corresponding list iterator.

◆ joinPendants()

void ogdf::PlanarAugmentation::joinPendants ( pa_label & label )

private

Connects all pendants of label with new edges.

◆ makeConnectedByPendants()

void ogdf::PlanarAugmentation::makeConnectedByPendants ( )

private

Makes the graph connected by new edges between pendants of the connected components.

◆ modifyBCRoot()

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

private

Modifies the root of the BC-Tree that newRoot replaces oldRoot.

◆ newLabel()

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

private

Creates a new label and inserts it into m_labels.

◆ planarityCheck()

bool ogdf::PlanarAugmentation::planarityCheck	(	node	v1,
		node	v2
	)

private

Checks planarity for a new edge (v1, v2) in the original graph.

Parameters

v1	is a node in the original graph.
v2	is a node in the original graph.

Returns: true iff the graph (including the new edge) is planar.

◆ reduceChain()

void ogdf::PlanarAugmentation::reduceChain	(	node	pendant,
		pa_label	labelOld = `nullptr`
	)

private

Traverses to the root and creates a label or updates one.

Is called for every pendant node.

Parameters

pendant	is a pendant in the BC-Tree.
labelOld	is the old label of `pendant`.

◆ removeAllPendants()

void ogdf::PlanarAugmentation::removeAllPendants ( pa_label & label )

private

Removes all pendants of label.

◆ terminate()

void ogdf::PlanarAugmentation::terminate ( )

private

Cleanup.

◆ updateAdjNonChildren()

void ogdf::PlanarAugmentation::updateAdjNonChildren	(	node	newBlock,
		SList< node > &	path
	)

private

Updates m_adjNonChildren.

Parameters

newBlock	is a new created block of the BC-Tree.
path	is the path in the BC-Tree between the two connected nodes.

◆ updateNewEdges()

void ogdf::PlanarAugmentation::updateNewEdges ( const SList< edge > & newEdges )

private

Major updates caused by the new edges.

Parameters

newEdges is a list of all new edges.

Member Data Documentation

◆ m_adjNonChildren

NodeArray<SList<adjEntry> > ogdf::PlanarAugmentation::m_adjNonChildren

private

Stores for each node of the bc-tree the children that have an adjacent bc-node that doesn't belong to the same parent-node.

This is necessary because the bc-tree uses an union-find-data-structure to store dependencies between bc-nodes. The adjacencies in the bc-tree won't be updated.

Definition at line 115 of file PlanarAugmentation.h.

◆ m_belongsTo

NodeArray<pa_label> ogdf::PlanarAugmentation::m_belongsTo

private

The label a BC-Node belongs to.

Definition at line 103 of file PlanarAugmentation.h.

◆ m_isLabel

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

private

The list iterator in m_labels if the node in the BC-Tree is a label.

Definition at line 106 of file PlanarAugmentation.h.

◆ m_labels

List<pa_label> ogdf::PlanarAugmentation::m_labels

private

The list of all labels, sorted by size (decreasing).

Definition at line 94 of file PlanarAugmentation.h.

◆ m_nPlanarityTests

int ogdf::PlanarAugmentation::m_nPlanarityTests = 0

private

The number of planarity tests.

Definition at line 82 of file PlanarAugmentation.h.

◆ m_pBCTree

DynamicBCTree* ogdf::PlanarAugmentation::m_pBCTree = nullptr

private

The corresponding BC-Tree.

Definition at line 88 of file PlanarAugmentation.h.

◆ m_pendants

List<node> ogdf::PlanarAugmentation::m_pendants

private

The list of all pendants (leaves in the BC-Tree).

Definition at line 97 of file PlanarAugmentation.h.

◆ m_pendantsToDel

List<node> ogdf::PlanarAugmentation::m_pendantsToDel

private

The list of pendants that has to be deleted after each reduceChain.

Definition at line 100 of file PlanarAugmentation.h.

◆ m_pGraph

Graph* ogdf::PlanarAugmentation::m_pGraph = nullptr

private

The working graph.

Definition at line 85 of file PlanarAugmentation.h.

◆ m_pResult

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

private

The inserted edges by the algorithm.

Definition at line 91 of file PlanarAugmentation.h.

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

include/ogdf/augmentation/PlanarAugmentation.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PlanarAugmentation()

◆ ~PlanarAugmentation()

Member Function Documentation

◆ addPendant()

◆ adjToCutvertex()

◆ augment()

◆ connectCondition()

◆ connectInsideLabel()

◆ connectLabels()

◆ connectPendants()

◆ deleteLabel()

◆ deletePendant()

◆ doCall()

◆ findLastBefore()

◆ findMatching()

◆ followPath()

◆ insertLabel()

◆ joinPendants()

◆ makeConnectedByPendants()

◆ modifyBCRoot()

◆ newLabel()

◆ planarityCheck()

◆ reduceChain()

◆ removeAllPendants()

◆ terminate()

◆ updateAdjNonChildren()

◆ updateNewEdges()

Member Data Documentation

◆ m_adjNonChildren

◆ m_belongsTo

◆ m_isLabel

◆ m_labels

◆ m_nPlanarityTests

◆ m_pBCTree

◆ m_pendants

◆ m_pendantsToDel

◆ m_pGraph

◆ m_pResult

Open
Graph Drawing
Framework