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 ()
Protected Member Functions
void	doCall (Graph &G, List< edge > &L)
	The implementation of the algorithm call.
Private Member Functions
void	augment ()
	The main function for planar augmentation.
void	makeConnectedByPendants ()
	Makes the graph connected by new edges between pendants of the connected components.
void	reduceChain (node p, label labelOld=0)
	Is called for every pendant-node. It traverses to the root and creates a label or updates one.
paStopCause	followPath (node v, node &last)
	Is called in reduceChain. It traverses to the root and checks several stop conditions.
bool	planarityCheck (node v1, node v2)
	Checks planarity for a new edge (v1,v2) in the original graph.
node	adjToCutvertex (node v, node cutvertex=0)
	Returns a node that belongs to bc-node v and is adjacent to the cutvertex.
node	findLastBefore (node pendant, node ancestor)
	Traverses from pendant to ancestor and returns the last node before ancestor on the path.
void	deletePendant (node p, bool removeFromLabel=true)
	Deletes the pendant p, removes it from the corresponding label and updates the label-order.
void	addPendant (node p, label &l)
	Adds a pendant p to the label l and updates the label-order.
edge	connectPendants (node pendant1, node pendant2)
	Connects two pendants.
void	removeAllPendants (label &l)
	Removes all pendants of a label.
void	joinPendants (label &l)
	Connects all pendants of label l with new edges.
void	connectInsideLabel (label &l)
	Connects the only pendant of l with a computed ancestor.
ListIterator< label >	insertLabel (label l)
	Inserts label l into m_labels by decreasing order.
void	deleteLabel (label &l, bool removePendants=true)
	deletes label l.
void	connectLabels (label first, label second)
	Inserts edges between pendants of label first and second. first.size() is gerater than second.size() or equal.
label	newLabel (node cutvertex, node p, paStopCause whyStop)
	Creates a new label and inserts it into m_labels.
bool	findMatching (label &first, label &second)
	Finds two matching labels, so all pendants can be connected without losing planarity.
bool	connectCondition (label a, label b)
	Checks if the pendants of label a and label b can be connected without creating a new pendant.
void	updateAdjNonChildren (node newBlock, SList< node > &path)
	Updates the adjNonChildren-data.
void	modifyBCRoot (node oldRoot, node newRoot)
	Modifies the root of the BC-Tree that newRoot replaces oldRoot.
void	updateNewEdges (const SList< edge > &newEdges)
	Major updates caused by the new edges.
void	terminate ()
	Cleanup.
Private Attributes
int	m_nPlanarityTests
	Counts the number of planarity tests.
Graph *	m_pGraph
	The working graph.
DynamicBCTree *	m_pBCTree
	The corresponding BC-Tree.
List< edge > *	m_pResult
	The inserted edges by the algorithm.
List< label >	m_labels
	The list of all labels, sorted by size (decreasing).
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.
NodeArray< label >	m_belongsTo
	The label a BC-Node belongs to.
NodeArray< ListIterator< label > >	m_isLabel
	The list iterator in m_labels if the node in the BC-Tree is a label.
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.

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

Constructor & Destructor Documentation

ogdf::PlanarAugmentation::PlanarAugmentation ( ) [inline]

Creates an instance of the planar augmentation algorithm.

Definition at line 213 of file PlanarAugmentation.h.

ogdf::PlanarAugmentation::~PlanarAugmentation ( ) [inline]

Definition at line 215 of file PlanarAugmentation.h.

Member Function Documentation

void ogdf::PlanarAugmentation::addPendant	(	node	p,
		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	(	label	a,
		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 ( label & l ) [private]

Connects the only pendant of l with a computed ancestor.

void ogdf::PlanarAugmentation::connectLabels	(	label	first,
		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	(	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
	)			`[protected, virtual]`

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	(	label &	first,
		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<label> ogdf::PlanarAugmentation::insertLabel ( label l ) [private]

Inserts label l into m_labels by decreasing order.

Returns:: the corresponding list iterator.

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

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,\

v2 are nodes of the original graph.

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

void ogdf::PlanarAugmentation::reduceChain	(	node	p,
		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 ( 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 dependancies between bc-nodes. The adjacencies in the bc-tree won't be updated.

Definition at line 277 of file PlanarAugmentation.h.

NodeArray<label> ogdf::PlanarAugmentation::m_belongsTo [private]

The label a BC-Node belongs to.

Definition at line 264 of file PlanarAugmentation.h.

NodeArray< ListIterator<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 268 of file PlanarAugmentation.h.

List<label> ogdf::PlanarAugmentation::m_labels [private]

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

Definition at line 250 of file PlanarAugmentation.h.

int ogdf::PlanarAugmentation::m_nPlanarityTests [private]

Counts the number of planarity tests.