This class implements the extended BoyerMyrvold planarity embedding algorithm. More...

#include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>

Public Types
enum	enumEmbeddingGrade { doNotEmbed = -3, doNotFind = -2, doFindUnlimited = -1, doFindZero = 0 }
	Denotes the different embedding options. More...
Public Member Functions
	BoyerMyrvoldPlanar (Graph &g, bool bundles, int m_embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, bool randomDFSTree, bool avoidE2Minors)
	Constructor, for parameters see BoyerMyrvold.
	~BoyerMyrvoldPlanar ()
	Destructor.
bool	start ()
	Starts the embedding algorithm.
void	flipBicomp (int c, int marker, NodeArray< int > &visited, bool wholeGraph, bool deleteFlipFlags)
	Flips all nodes of the bicomp with unique, real, rootchild c as necessary.
BoyerMyrvoldPlanar &	operator= (const BoyerMyrvoldPlanar &)
	Assignment operator is undefined!
Protected Member Functions
bool	pertinent (node w)
	Checks whether node w is pertinent. w has to be non-virtual.
bool	internallyActive (node w, int v)
	Checks whether real node w is internally active while embedding node with DFI v.
bool	externallyActive (node w, int v)
	Checks whether real node w is externally active while embedding node with DFI v.
bool	inactive (node w, int v)
	Checks whether real node w is inactive while embedding node with DFI v.
int	infoAboutNode (node w, int v)
	Checks all dynamic information about a node w while embedding node with DFI v.
node	successorOnExternalFace (node w, int &direction)
	Walks upon external face in the given direction starting at w.
node	successorWithoutShortCircuit (node w, int &direction)
	Walks upon external face in given direction avoiding short circuit edges.
node	constSuccessorOnExternalFace (node v, int direction)
	Returns the successornode on the external face in given direction.
node	constSuccessorWithoutShortCircuit (node v, int direction)
	Walks upon external face in direction avoiding short circuit edges.
adjEntry	beforeShortCircuitEdge (node v, int direction)
	Returns underlying former adjEntry, if a short circuit edge in direction of v exists.
node	activeSuccessor (node w, int &direction, int v, int &info)
	Walks upon external face in the given direction starting at w until an active vertex is reached.
node	constActiveSuccessor (node w, int direction, int v, int &info)
	Walks upon external face in the given direction (without changing it) until an active vertex is reached.
bool	wNodesExist (node root, node stopx, node stopy)
	Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.
void	printNodeInfo (node v)
	Prints informations about node v.
void	mergeBiconnectedComponent (StackPure< int > &stack, const int j)
	Merges the last two biconnected components saved in stack while embedding them.
void	mergeBiconnectedComponentOnlyPlanar (StackPure< int > &stack, const int j)
	Merges the last two biconnected components saved in stack without embedding them.
void	embedBackedges (const node v, const int v_dir, const node w, const int w_dir, const int i)
	Embeds backedges from node v with direction v_dir to node w with direction w_dir.
void	embedBackedgesOnlyPlanar (const node v, const int v_dir, const node w, const int w_dir, const int i)
	Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir.
void	createShortCircuitEdge (const node v, const int v_dir, const node w, const int w_dir)
	Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.
node	walkup (const node v, const node w, const int marker, const edge back)
	Walkup: Builds the pertinent subgraph for the backedge back.
int	walkdown (const int i, const node v, FindKuratowskis *findKuratowskis)
	Walkdown: Embeds all backedges with DFI i as targetnode to node v.
void	mergeUnprocessedNodes ()
	Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.
void	postProcessEmbedding ()
	Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.
bool	embed ()
	Starts the embedding phase, which embeds m_g node by node in descending DFI-order.
Protected Attributes
Graph &	m_g
	Input graph, which can be altered.
const bool	m_bundles
	Some parameters... see BoyerMyrvold for further options.
const int	m_embeddingGrade
const bool	m_limitStructures
const bool	m_randomDFSTree
const bool	m_avoidE2Minors
int	m_flippedNodes
	The whole number of bicomps, which have to be flipped.
NodeArray< node >	m_realVertex
	Link to non-virtual vertex of a virtual Vertex.
NodeArray< int >	m_dfi
	The one and only DFI-NodeArray.
Array< node >	m_nodeFromDFI
	Returns appropriate node from given DFI.
NodeArray< adjEntry >	m_link [2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order.
NodeArray< adjEntry >	m_beforeSCE [2]
	Links for short circuit edges.
NodeArray< adjEntry >	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex.
NodeArray< int >	m_leastAncestor
	The DFI of the least ancestor node over all backedges.
EdgeArray< int >	m_edgeType
	Contains the type of each edge.
NodeArray< int >	m_lowPoint
	The lowpoint of each node.
NodeArray< int >	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root.
NodeArray< ListPure< node > >	m_separatedDFSChildList
	A list to all separated DFS-children of node.
NodeArray< ListIterator< node > >	m_pNodeInParent
	Pointer to node contained in the DFSChildList of his parent, if exists.
NodeArray< int >	m_visited
	This Array keeps track of all vertices that are visited by current walkup.
EdgeArray< node >	m_pointsToRoot
	Identifies the rootnode of the child bicomp the given backedge points to.
NodeArray< int >	m_visitedWithBackedge
	Keeps track of all vertices that are visited by the walkup through a specific backedge.
NodeArray< bool >	m_flipped
	Iff true, the node is the root of a bicomp which has to be flipped.
NodeArray< SListPure< adjEntry > >	m_backedgeFlags
	Holds information, if node is the source of a backedge.
NodeArray< SListPure< node > >	m_pertinentRoots
	List of virtual bicomp roots, that are pertinent to the current embedded node.
SListPure< KuratowskiStructure > &	m_output
	Data structure for the kuratowski subdivisions, which will be returned.
Friends
class	BoyerMyrvold
class	BoyerMyrvoldInit
class	FindKuratowskis
class	ExtractKuratowskis

Detailed Description

This class implements the extended BoyerMyrvold planarity embedding algorithm.

Definition at line 97 of file BoyerMyrvoldPlanar.h.

Member Enumeration Documentation

enum ogdf::BoyerMyrvoldPlanar::enumEmbeddingGrade

Denotes the different embedding options.

Enumerator:

doNotEmbed
doNotFind
doFindUnlimited
doFindZero

Definition at line 122 of file BoyerMyrvoldPlanar.h.

Constructor & Destructor Documentation

ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar	(	Graph &	g,
		bool	bundles,
		int	m_embeddingGrade,
		bool	limitStructures,
		SListPure< KuratowskiStructure > &	output,
		bool	randomDFSTree,
		bool	avoidE2Minors
	)

Constructor, for parameters see BoyerMyrvold.

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

Destructor.

Definition at line 116 of file BoyerMyrvoldPlanar.h.

Member Function Documentation

node ogdf::BoyerMyrvoldPlanar::activeSuccessor	(	node	w,
		int &	direction,
		int	v,
		int &	info
	)			`[protected]`

Walks upon external face in the given direction starting at w until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex.

adjEntry ogdf::BoyerMyrvoldPlanar::beforeShortCircuitEdge	(	node	v,
		int	direction
	)			`[inline, protected]`

Returns underlying former adjEntry, if a short circuit edge in direction of v exists.

Otherwise the common edge is returned. In every case the returned adjEntry points to the targetnode.

Definition at line 262 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor	(	node	w,
		int	direction,
		int	v,
		int &	info
	)			`[inline, protected]`

Walks upon external face in the given direction (without changing it) until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex. But does not change the direction.

Definition at line 275 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorOnExternalFace	(	node	v,
		int	direction
	)			`[inline, protected]`

Returns the successornode on the external face in given direction.

direction is not changed.

Definition at line 243 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorWithoutShortCircuit	(	node	v,
		int	direction
	)			`[inline, protected]`

Walks upon external face in direction avoiding short circuit edges.

direction is not changed.

Definition at line 252 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::createShortCircuitEdge	(	const node	v,
		const int	v_dir,
		const node	w,
		const int	w_dir
	)			`[protected]`

Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.

bool ogdf::BoyerMyrvoldPlanar::embed ( ) [protected]

Starts the embedding phase, which embeds m_g node by node in descending DFI-order.

Returns true, if graph is planar, false otherwise.

void ogdf::BoyerMyrvoldPlanar::embedBackedges	(	const node	v,
		const int	v_dir,
		const node	w,
		const int	w_dir,
		const int	i
	)			`[protected]`

Embeds backedges from node v with direction v_dir to node w with direction w_dir.

i is the DFI of current embedded node.

void ogdf::BoyerMyrvoldPlanar::embedBackedgesOnlyPlanar	(	const node	v,
		const int	v_dir,
		const node	w,
		const int	w_dir,
		const int	i
	)			`[protected]`

Links (not embed) backedges from node v with direction v_dir to node w with direction w_dir.

i is the DFI of current embedded node.

bool ogdf::BoyerMyrvoldPlanar::externallyActive	(	node	w,
		int	v
	)			`[inline, protected]`

Checks whether real node w is externally active while embedding node with DFI v.

Definition at line 165 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::flipBicomp	(	int	c,
		int	marker,
		NodeArray< int > &	visited,
		bool	wholeGraph,
		bool	deleteFlipFlags
	)

Flips all nodes of the bicomp with unique, real, rootchild c as necessary.

Parameters:

	c	is the unique rootchild of the bicomp
	marker	is the value which marks nodes as visited
	visited	is the array containing visiting information
	wholeGraph	Iff true, all bicomps of all connected components will be traversed
	deleteFlipFlags	Iff true, the flipping flags will be deleted after flipping

bool ogdf::BoyerMyrvoldPlanar::inactive	(	node	w,
		int	v
	)			`[inline, protected]`

Checks whether real node w is inactive while embedding node with DFI v.

Definition at line 174 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::infoAboutNode	(	node	w,
		int	v
	)			`[inline, protected]`

Checks all dynamic information about a node w while embedding node with DFI v.

Parameters:

`[out]`	0	= inactive
`[out]`	1	= internallyActive
`[out]`	2	= pertinent and externallyActive
`[out]`	3	= externallyActive and not pertinent

Definition at line 189 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::internallyActive	(	node	w,
		int	v
	)			`[inline, protected]`

Checks whether real node w is internally active while embedding node with DFI v.

Definition at line 158 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponent	(	StackPure< int > &	stack,
		const int	j
	)			`[protected]`

Merges the last two biconnected components saved in stack while embedding them.

j is the outgoing traversal direction of the current node to embed

void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponentOnlyPlanar	(	StackPure< int > &	stack,
		const int	j
	)			`[protected]`

Merges the last two biconnected components saved in stack without embedding them.

j is the outgoing traversal direction of the current node to embed

void ogdf::BoyerMyrvoldPlanar::mergeUnprocessedNodes ( ) [protected]

Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.

BoyerMyrvoldPlanar& ogdf::BoyerMyrvoldPlanar::operator= ( const BoyerMyrvoldPlanar & )

Assignment operator is undefined!

bool ogdf::BoyerMyrvoldPlanar::pertinent ( node w ) [inline, protected]

Checks whether node w is pertinent. w has to be non-virtual.

Definition at line 151 of file BoyerMyrvoldPlanar.h.

void ogdf::BoyerMyrvoldPlanar::postProcessEmbedding ( ) [protected]

Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.

In addition, embedding steps for parallel edges and self-loops are implemented.

void ogdf::BoyerMyrvoldPlanar::printNodeInfo ( node v ) [inline, protected]

Prints informations about node v.

Definition at line 302 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::start ( )

Starts the embedding algorithm.

node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace	(	node	w,
		int &	direction
	)			`[inline, protected]`

Walks upon external face in the given direction starting at w.

If none of the bicomps has been flipped then CW = clockwise and CCW = counterclockwise holds. In general, the traversaldirection could have been changed due to flipped components. If this occurs, the traversaldirection is flipped.

Definition at line 213 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::successorWithoutShortCircuit	(	node	w,
		int &	direction
	)			`[inline, protected]`

Walks upon external face in given direction avoiding short circuit edges.

Definition at line 227 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::walkdown	(	const int	i,
		const node	v,
		FindKuratowskis *	findKuratowskis
	)			`[protected]`

Walkdown: Embeds all backedges with DFI i as targetnode to node v.

Parameters:

	i	is the DFI of the current vertex to embed
	v	is the virtual node being the root of the bicomp attached to i
	findKuratowskis	collects information in order to extract Kuratowski Subdivisions later
`[out]`	1,iff	the embedding process found a stopping configuration

node ogdf::BoyerMyrvoldPlanar::walkup	(	const node	v,
		const node	w,
		const int	marker,
		const edge	back
	)			`[protected]`

Walkup: Builds the pertinent subgraph for the backedge back.

back is the backedge between nodes v and w. v is the current node to embed. All visited nodes are marked with value marker. The Function returns the last traversed node.

bool ogdf::BoyerMyrvoldPlanar::wNodesExist	(	node	root,
		node	stopx,
		node	stopy
	)			`[inline, protected]`

Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.

The node root is root of the bicomp containing the stopping vertices

Definition at line 282 of file BoyerMyrvoldPlanar.h.

Friends And Related Function Documentation

friend class BoyerMyrvold [friend]

Definition at line 99 of file BoyerMyrvoldPlanar.h.

friend class BoyerMyrvoldInit [friend]

Definition at line 100 of file BoyerMyrvoldPlanar.h.

friend class ExtractKuratowskis [friend]

Definition at line 102 of file BoyerMyrvoldPlanar.h.

friend class FindKuratowskis [friend]

Definition at line 101 of file BoyerMyrvoldPlanar.h.

Member Data Documentation

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_adjParent [protected]

The adjEntry which goes from DFS-parent to current vertex.

Definition at line 408 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors [protected]

Definition at line 378 of file BoyerMyrvoldPlanar.h.

NodeArray<SListPure<adjEntry> > ogdf::BoyerMyrvoldPlanar::m_backedgeFlags [protected]

Holds information, if node is the source of a backedge.

This information refers to the adjEntries on the targetnode and is used during the walkdown

Definition at line 464 of file BoyerMyrvoldPlanar.h.

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_beforeSCE[2] [protected]

Links for short circuit edges.

If short circuit edges are introduced, the former adjEntries to the neighbors have to be saved here for embedding and merging purposes. If there is no short circuit edge, this adjEntry is NULL.

Definition at line 405 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_bundles [protected]

Some parameters... see BoyerMyrvold for further options.

Definition at line 374 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_dfi [protected]

The one and only DFI-NodeArray.

Definition at line 390 of file BoyerMyrvoldPlanar.h.

EdgeArray<int> ogdf::BoyerMyrvoldPlanar::m_edgeType [protected]

Contains the type of each edge.

Parameters:

	0	= EDGE_UNDEFINED
	1	= EDGE_SELFLOOP
	2	= EDGE_BACK
	3	= EDGE_DFS
	4	= EDGE_DFS_PARALLEL
	5	= EDGE_BACK_DELETED

Definition at line 423 of file BoyerMyrvoldPlanar.h.

const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade [protected]

Definition at line 375 of file BoyerMyrvoldPlanar.h.

NodeArray<bool> ogdf::BoyerMyrvoldPlanar::m_flipped [protected]

Iff true, the node is the root of a bicomp which has to be flipped.

The DFS-child of every bicomp root vertex is unique. if a bicomp is flipped, this DFS-child is marked to check whether the bicomp has to be flipped or not.

Definition at line 458 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::m_flippedNodes [protected]

The whole number of bicomps, which have to be flipped.

Definition at line 381 of file BoyerMyrvoldPlanar.h.

Graph& ogdf::BoyerMyrvoldPlanar::m_g [protected]

Input graph, which can be altered.

Definition at line 371 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI [protected]

The highest DFI in a subtree with node as root.

Definition at line 429 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_leastAncestor [protected]

The DFI of the least ancestor node over all backedges.