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 ()
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
void	doCall (Graph &G, List< edge > &L)
	The implementation of the algorithm call.

Private Member Functions
void	addPendant (node p, pa_label &l)
	Adds a pendant p to the label l and updates the label-order.
node	adjToCutvertex (node v, node cutvertex=0)
	Returns a node that belongs to bc-node v and is adjacent to the 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 &l)
	Connects the only pendant of l with a computed ancestor.
void	connectLabels (pa_label first, pa_label second)
	Inserts edges between pendants of label first and second. first.size() is gerater than second.size() or equal.
edge	connectPendants (node pendant1, node pendant2)
	Connects two pendants.
void	deleteLabel (pa_label &l, bool removePendants=true)
	deletes label l.
void	deletePendant (node p, bool removeFromLabel=true)
	Deletes the pendant p, 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.
paStopCause	followPath (node v, node &last)
	Is called in reduceChain. It traverses to the root and checks several stop conditions.
ListIterator< pa_label >	insertLabel (pa_label l)
	Inserts label l into m_labels by decreasing order.
void	joinPendants (pa_label &l)
	Connects all pendants of label l 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 p, paStopCause 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 p, pa_label labelOld=0)
	Is called for every pendant-node. It traverses to the root and creates a label or updates one.
void	removeAllPendants (pa_label &l)
	Removes all pendants of a label.
void	terminate ()
	Cleanup.
void	updateAdjNonChildren (node newBlock, SList< node > &path)
	Updates the adjNonChildren-data.
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
	Counts the number of planarity tests.
DynamicBCTree *	m_pBCTree
	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
	The working graph.
List< edge > *	m_pResult
	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 76 of file PlanarAugmentation.h.

Constructor & Destructor Documentation

ogdf::PlanarAugmentation::PlanarAugmentation ( )

inline

Creates an instance of the planar augmentation algorithm.

Definition at line 80 of file PlanarAugmentation.h.

ogdf::PlanarAugmentation::~PlanarAugmentation ( )

inline

Definition at line 82 of file PlanarAugmentation.h.

Member Function Documentation

void ogdf::PlanarAugmentation::addPendant	(	node	p,
		pa_label &	l
	)

private

Adds a pendant p to the label l and updates the label-order.

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

private

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

Parameters:

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

Returns:: a node of the original graph.

void ogdf::PlanarAugmentation::augment ( )

private

The main function for planar augmentation.

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.

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

private

Connects the only pendant of l with a computed ancestor.

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

private

Inserts edges between pendants of label first and second. first.size() is gerater than second.size() or equal.

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

private

Connects two pendants.

Returns:: the new edge in the original graph.

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

private

deletes label l.

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

private

Deletes the pendant p, removes it from the corresponding label and updates the label-order.

void ogdf::PlanarAugmentation::doCall	(	Graph &	G,
		List< edge > &	L
	)

protectedvirtual

The implementation of the algorithm call.

Parameters:

G	is the working graph.
L	is the list of all new edges.

Implements ogdf::AugmentationModule.

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

private

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

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.

paStopCause ogdf::PlanarAugmentation::followPath	(	node	v,
		node &	last
	)

private

Is called in reduceChain. It traverses to the root and checks several stop conditions.

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.

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

private

Inserts label l into m_labels by decreasing order.

Returns:: the corresponding list iterator.

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

private

Connects all pendants of label l with new edges.

void ogdf::PlanarAugmentation::makeConnectedByPendants ( )

private

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

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

private

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

pa_label ogdf::PlanarAugmentation::newLabel	(	node	cutvertex,
		node	p,
		paStopCause	whyStop
	)

private

Creates a new label and inserts it into m_labels.

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.

void ogdf::PlanarAugmentation::reduceChain	(	node	p,
		pa_label	labelOld = `0`
	)

private

Is called for every pendant-node. It traverses to the root and creates a label or updates one.

Parameters:

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

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

private

Removes all pendants of a label.

void ogdf::PlanarAugmentation::terminate ( )

private

Cleanup.

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

private

Updates the adjNonChildren-data.

Parameters:

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

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

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 144 of file PlanarAugmentation.h.

NodeArray<pa_label> ogdf::PlanarAugmentation::m_belongsTo

private

The label a BC-Node belongs to.

Definition at line 131 of file PlanarAugmentation.h.

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 135 of file PlanarAugmentation.h.

List<pa_label> ogdf::PlanarAugmentation::m_labels

private

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

Definition at line 117 of file PlanarAugmentation.h.

int ogdf::PlanarAugmentation::m_nPlanarityTests

private

Counts the number of planarity tests.

Definition at line 98 of file PlanarAugmentation.h.

DynamicBCTree* ogdf::PlanarAugmentation::m_pBCTree

private

The corresponding BC-Tree.

Definition at line 107 of file PlanarAugmentation.h.

List<node> ogdf::PlanarAugmentation::m_pendants

private

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

Definition at line 121 of file PlanarAugmentation.h.

List<node> ogdf::PlanarAugmentation::m_pendantsToDel

private

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

Definition at line 126 of file PlanarAugmentation.h.

Graph* ogdf::PlanarAugmentation::m_pGraph

private

The working graph.

Definition at line 103 of file PlanarAugmentation.h.

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

private

The inserted edges by the algorithm.

Definition at line 112 of file PlanarAugmentation.h.

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

ogdf/augmentation/PlanarAugmentation.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework