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.
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!
bool	start ()
	Starts the embedding algorithm.

Protected Member Functions
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.
adjEntry	beforeShortCircuitEdge (node v, int direction)
	Returns underlying former adjEntry, if a short circuit edge in direction of v exists.
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.
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.
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.
bool	embed ()
	Starts the embedding phase, which embeds m_g node by node in descending DFI-order.
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.
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.
bool	internallyActive (node w, int v)
	Checks whether real node w is internally active while embedding node with DFI 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	mergeUnprocessedNodes ()
	Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.
bool	pertinent (node w)
	Checks whether node w is pertinent. w has to be non-virtual.
void	postProcessEmbedding ()
	Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.
void	printNodeInfo (node v)
	Prints informations about node 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.
int	walkdown (const int i, const node v, FindKuratowskis *findKuratowskis)
	Walkdown: Embeds all backedges with DFI i as targetnode to node v.
node	walkup (const node v, const node w, const int marker, const edge back)
	Walkup: Builds the pertinent subgraph for the backedge back.
bool	wNodesExist (node root, node stopx, node stopy)
	Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.

Protected Attributes
NodeArray< adjEntry >	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex.
const bool	m_avoidE2Minors
NodeArray< SListPure< adjEntry > >	m_backedgeFlags
	Holds information, if node is the source of a backedge.
NodeArray< adjEntry >	m_beforeSCE [2]
	Links for short circuit edges.
const bool	m_bundles
	Some parameters... see BoyerMyrvold for further options.
NodeArray< int >	m_dfi
	The one and only DFI-NodeArray.
EdgeArray< int >	m_edgeType
	Contains the type of each edge.
const int	m_embeddingGrade
NodeArray< bool >	m_flipped
	Iff true, the node is the root of a bicomp which has to be flipped.
int	m_flippedNodes
	The whole number of bicomps, which have to be flipped.
Graph &	m_g
	Input graph, which can be altered.
NodeArray< int >	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root.
NodeArray< int >	m_leastAncestor
	The DFI of the least ancestor node over all backedges.
const bool	m_limitStructures
NodeArray< adjEntry >	m_link [2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order.
NodeArray< int >	m_lowPoint
	The lowpoint of each node.
Array< node >	m_nodeFromDFI
	Returns appropriate node from given DFI.
SListPure< KuratowskiStructure > &	m_output
	Data structure for the kuratowski subdivisions, which will be returned.
NodeArray< SListPure< node > >	m_pertinentRoots
	List of virtual bicomp roots, that are pertinent to the current embedded node.
NodeArray< ListIterator< node > >	m_pNodeInParent
	Pointer to node contained in the DFSChildList of his parent, if exists.
EdgeArray< node >	m_pointsToRoot
	Identifies the rootnode of the child bicomp the given backedge points to.
const bool	m_randomDFSTree
NodeArray< node >	m_realVertex
	Link to non-virtual vertex of a virtual Vertex.
NodeArray< ListPure< node > >	m_separatedDFSChildList
	A list to all separated DFS-children of node.
NodeArray< int >	m_visited
	This Array keeps track of all vertices that are visited by current walkup.
NodeArray< int >	m_visitedWithBackedge
	Keeps track of all vertices that are visited by the walkup through a specific backedge.

Friends
class	BoyerMyrvold
class	BoyerMyrvoldInit
class	ExtractKuratowskis
class	FindKuratowskis

Detailed Description

This class implements the extended BoyerMyrvold planarity embedding algorithm.

Definition at line 88 of file BoyerMyrvoldPlanar.h.

Member Enumeration Documentation

enum ogdf::BoyerMyrvoldPlanar::enumEmbeddingGrade

Denotes the different embedding options.

Enumerator:

doNotEmbed
doNotFind
doFindUnlimited
doFindZero

Definition at line 113 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 107 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
	)

inlineprotected

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 255 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor	(	node	w,
		int	direction,
		int	v,
		int &	info
	)

inlineprotected

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 268 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorOnExternalFace	(	node	v,
		int	direction
	)

inlineprotected

Returns the successornode on the external face in given direction.

direction is not changed.

Definition at line 236 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::constSuccessorWithoutShortCircuit	(	node	v,
		int	direction
	)

inlineprotected

Walks upon external face in direction avoiding short circuit edges.

direction is not changed.

Definition at line 245 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
	)

inlineprotected

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

Definition at line 156 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
	)

inlineprotected

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

Definition at line 165 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::infoAboutNode	(	node	w,
		int	v
	)

inlineprotected

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

Returns:

This method returns the following values:

0 = inactive
1 = internallyActive
2 = pertinent and externallyActive
3 = externallyActive and not pertinent

Definition at line 182 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::internallyActive	(	node	w,
		int	v
	)

inlineprotected

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

Definition at line 149 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 )

inlineprotected

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

Definition at line 142 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 )

inlineprotected

Prints informations about node v.

Definition at line 295 of file BoyerMyrvoldPlanar.h.

bool ogdf::BoyerMyrvoldPlanar::start ( )

Starts the embedding algorithm.

node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace	(	node	w,
		int &	direction
	)

inlineprotected

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 206 of file BoyerMyrvoldPlanar.h.

node ogdf::BoyerMyrvoldPlanar::successorWithoutShortCircuit	(	node	w,
		int &	direction
	)

inlineprotected

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

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

Returns:: 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
	)

inlineprotected

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 275 of file BoyerMyrvoldPlanar.h.

Friends And Related Function Documentation

friend class BoyerMyrvold

friend

Definition at line 90 of file BoyerMyrvoldPlanar.h.

friend class BoyerMyrvoldInit

friend

Definition at line 91 of file BoyerMyrvoldPlanar.h.

friend class ExtractKuratowskis

friend

Definition at line 93 of file BoyerMyrvoldPlanar.h.

friend class FindKuratowskis

friend

Definition at line 92 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 402 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors

protected

Definition at line 372 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 458 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 399 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_bundles

protected

Some parameters... see BoyerMyrvold for further options.

Definition at line 368 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_dfi

protected

The one and only DFI-NodeArray.

Definition at line 384 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 417 of file BoyerMyrvoldPlanar.h.

const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade

protected

Definition at line 369 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 452 of file BoyerMyrvoldPlanar.h.

int ogdf::BoyerMyrvoldPlanar::m_flippedNodes

protected

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

Definition at line 375 of file BoyerMyrvoldPlanar.h.

Graph& ogdf::BoyerMyrvoldPlanar::m_g

protected

Input graph, which can be altered.

Definition at line 365 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI

protected

The highest DFI in a subtree with node as root.

Definition at line 423 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_leastAncestor

protected

The DFI of the least ancestor node over all backedges.

If no backedge exists, the least ancestor is the DFI of that node itself

Definition at line 407 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures

protected

Definition at line 370 of file BoyerMyrvoldPlanar.h.

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_link[2]

protected

Links to opposite adjacency entries on external face in clockwise resp. ccw order.

m_link[0]=CCW, m_link[1]=CW

Definition at line 392 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_lowPoint

protected

The lowpoint of each node.

Definition at line 420 of file BoyerMyrvoldPlanar.h.

Array<node> ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI

protected

Returns appropriate node from given DFI.

Definition at line 387 of file BoyerMyrvoldPlanar.h.

SListPure<KuratowskiStructure>& ogdf::BoyerMyrvoldPlanar::m_output

protected

Data structure for the kuratowski subdivisions, which will be returned.

Definition at line 464 of file BoyerMyrvoldPlanar.h.

NodeArray<SListPure<node> > ogdf::BoyerMyrvoldPlanar::m_pertinentRoots

protected

List of virtual bicomp roots, that are pertinent to the current embedded node.

Definition at line 461 of file BoyerMyrvoldPlanar.h.

NodeArray<ListIterator<node> > ogdf::BoyerMyrvoldPlanar::m_pNodeInParent

protected

Pointer to node contained in the DFSChildList of his parent, if exists.

If node isn't in list or list doesn't exist, the pointer is set to NULL.

Definition at line 433 of file BoyerMyrvoldPlanar.h.

EdgeArray<node> ogdf::BoyerMyrvoldPlanar::m_pointsToRoot

protected

Identifies the rootnode of the child bicomp the given backedge points to.

Definition at line 440 of file BoyerMyrvoldPlanar.h.

const bool ogdf::BoyerMyrvoldPlanar::m_randomDFSTree

protected

Definition at line 371 of file BoyerMyrvoldPlanar.h.

NodeArray<node> ogdf::BoyerMyrvoldPlanar::m_realVertex

protected

Link to non-virtual vertex of a virtual Vertex.

A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex

Definition at line 381 of file BoyerMyrvoldPlanar.h.

NodeArray<ListPure<node> > ogdf::BoyerMyrvoldPlanar::m_separatedDFSChildList

protected

A list to all separated DFS-children of node.

The list is sorted by lowpoint values (in linear time)

Definition at line 428 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visited

protected

This Array keeps track of all vertices that are visited by current walkup.

Definition at line 437 of file BoyerMyrvoldPlanar.h.

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visitedWithBackedge

protected

Keeps track of all vertices that are visited by the walkup through a specific backedge.

This is done in order to refer to the unique child-bicomp of v.

Definition at line 445 of file BoyerMyrvoldPlanar.h.

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

ogdf/internal/planarity/BoyerMyrvoldPlanar.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework