Combinatorial embeddings of planar graphs. More...

#include <ogdf/basic/CombinatorialEmbedding.h>

Inheritance diagram for ogdf::ConstCombinatorialEmbedding:

Public Member Functions

	ConstCombinatorialEmbedding ()
	Creates a combinatorial embedding associated with no graph.
	ConstCombinatorialEmbedding (const Graph &G)
	Creates a combinatorial embedding of graph G.
	ConstCombinatorialEmbedding (const ConstCombinatorialEmbedding &C)
	Copy constructor.
ConstCombinatorialEmbedding &	operator= (const ConstCombinatorialEmbedding &C)
	Assignment operator.

const Graph &	getGraph () const
	Returns the associated graph of the combinatorial embedding.
	operator const Graph & () const
	Returns associated graph.

face	firstFace () const
	Returns the first face in the list of all faces.
face	lastFace () const
	Returns the last face in the list of all faces.
int	numberOfFaces () const
	Returns the number of faces.

face	rightFace (adjEntry adj) const
	Returns the face to the right of adj, i.e., the face containing adj.
face	leftFace (adjEntry adj) const
	Returns the face to the left of adj, i.e., the face containing the twin of adj.

int	maxFaceIndex () const
	Returns the largest used face index.
int	faceArrayTableSize () const
	Returns the table size of face arrays associated with this embedding.

face	chooseFace () const
	Returns a random face.
face	maximalFace () const
	Returns a face of maximal size.

face	externalFace () const
	Returns the external face.
void	setExternalFace (face f)
	Sets the external face to f.
bool	isBridge (edge e) const

void	init (const Graph &G)
	Initializes the embedding for graph G.
void	init ()
void	computeFaces ()
	Computes the list of faces.

bool	consistencyCheck ()
	Checks the consistency of the data structure.

ListIterator< FaceArrayBase * >	registerArray (FaceArrayBase *pFaceArray) const
	Registers the face array pFaceArray.
void	unregisterArray (ListIterator< FaceArrayBase * > it) const
	Unregisters the face array identified by it.

Protected Member Functions
face	createFaceElement (adjEntry adjFirst)
	Create a new face.
void	reinitArrays ()
	Reinitialize associated face arrays.

Protected Attributes
const Graph *	m_cpGraph
	The associated graph.
face	m_externalFace
int	m_faceArrayTableSize
	The current table size of face arrays.
int	m_faceIdCount
	The index assigned to the next created face.
GraphList< FaceElement >	m_faces
	The list of all faces.
int	m_nFaces
	The number of faces.
ListPure< FaceArrayBase * >	m_regFaceArrays
	The external face.
AdjEntryArray< face >	m_rightFace
	The face to which an adjacency entry belongs.

Detailed Description

Combinatorial embeddings of planar graphs.

Maintains a combinatorial embedding of an embedded graph, i.e., the set of faces. A combinatorial embedding is defined by the (cyclic) order of the adjacency entries around a vertex; more precisely, the adjacency list gives the cyclic order of the adjacency entries in clockwise order. Each adjacency entry adj is contained in exactly one face, the face to the right of adj. The list of adjacency entries defining a face is given in clockwise order for internal faces, and in counter-clockwise order for the external face.

See also:: CombinatorialEmbedding provides additional functionality for modifying the embedding.

Definition at line 140 of file CombinatorialEmbedding.h.

Constructor & Destructor Documentation

ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding ( )

Creates a combinatorial embedding associated with no graph.

ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding ( const Graph & G )

explicit

Creates a combinatorial embedding of graph G.

Precondition:: Graph G must be embedded, i.e., the adjacency lists of its nodes must define an embedding.

ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding ( const ConstCombinatorialEmbedding & C )

Copy constructor.

Member Function Documentation

face ogdf::ConstCombinatorialEmbedding::chooseFace ( ) const

Returns a random face.

void ogdf::ConstCombinatorialEmbedding::computeFaces ( )

Computes the list of faces.

bool ogdf::ConstCombinatorialEmbedding::consistencyCheck ( )

Checks the consistency of the data structure.

face ogdf::ConstCombinatorialEmbedding::createFaceElement ( adjEntry adjFirst )

protected

Create a new face.

face ogdf::ConstCombinatorialEmbedding::externalFace ( ) const

inline

Returns the external face.

Definition at line 226 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::faceArrayTableSize ( ) const

inline

Returns the table size of face arrays associated with this embedding.

Definition at line 213 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::firstFace ( ) const

inline

Returns the first face in the list of all faces.

Definition at line 187 of file CombinatorialEmbedding.h.

const Graph& ogdf::ConstCombinatorialEmbedding::getGraph ( ) const

inline

Returns the associated graph of the combinatorial embedding.

Reimplemented in ogdf::CombinatorialEmbedding.

Definition at line 179 of file CombinatorialEmbedding.h.

void ogdf::ConstCombinatorialEmbedding::init ( const Graph & G )

Initializes the embedding for graph G.

Precondition:: Graph G must be embedded, i.e., the adjacency lists of its nodes must define an embedding.

void ogdf::ConstCombinatorialEmbedding::init ( )

bool ogdf::ConstCombinatorialEmbedding::isBridge ( edge e ) const

inline

Definition at line 239 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::lastFace ( ) const

inline

Returns the last face in the list of all faces.

Definition at line 190 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::leftFace ( adjEntry adj ) const

inline

Returns the face to the left of adj, i.e., the face containing the twin of adj.

Parameters:

adj	is an adjacency element in the associated graph.

Definition at line 205 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::maxFaceIndex ( ) const

inline

Returns the largest used face index.

Definition at line 210 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::maximalFace ( ) const

Returns a face of maximal size.

int ogdf::ConstCombinatorialEmbedding::numberOfFaces ( ) const

inline

Returns the number of faces.

Definition at line 193 of file CombinatorialEmbedding.h.

ogdf::ConstCombinatorialEmbedding::operator const Graph & ( ) const

inline

Returns associated graph.

Reimplemented in ogdf::CombinatorialEmbedding.

Definition at line 182 of file CombinatorialEmbedding.h.

ConstCombinatorialEmbedding& ogdf::ConstCombinatorialEmbedding::operator= ( const ConstCombinatorialEmbedding & C )

Assignment operator.

ListIterator<FaceArrayBase*> ogdf::ConstCombinatorialEmbedding::registerArray ( FaceArrayBase * pFaceArray ) const

Registers the face array pFaceArray.

This method is only used by face arrays.

void ogdf::ConstCombinatorialEmbedding::reinitArrays ( )

protected

Reinitialize associated face arrays.

face ogdf::ConstCombinatorialEmbedding::rightFace ( adjEntry adj ) const

inline

Returns the face to the right of adj, i.e., the face containing adj.

Parameters:

adj	is an adjecency element in the associated graph.

Definition at line 199 of file CombinatorialEmbedding.h.

void ogdf::ConstCombinatorialEmbedding::setExternalFace ( face f )

inline

Sets the external face to f.

Parameters:

f	is a face in this embedding.

Definition at line 234 of file CombinatorialEmbedding.h.

void ogdf::ConstCombinatorialEmbedding::unregisterArray ( ListIterator< FaceArrayBase * > it ) const

Unregisters the face array identified by it.

This method is only used by face arrays.

Member Data Documentation

const Graph* ogdf::ConstCombinatorialEmbedding::m_cpGraph

protected

The associated graph.

Definition at line 143 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::m_externalFace

protected

Definition at line 151 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_faceArrayTableSize

protected

The current table size of face arrays.

Definition at line 148 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount

protected

The index assigned to the next created face.

Definition at line 147 of file CombinatorialEmbedding.h.

GraphList<FaceElement> ogdf::ConstCombinatorialEmbedding::m_faces

protected

The list of all faces.

Definition at line 145 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_nFaces

protected

The number of faces.

Definition at line 146 of file CombinatorialEmbedding.h.

ListPure<FaceArrayBase*> ogdf::ConstCombinatorialEmbedding::m_regFaceArrays

mutableprotected

The external face.

The registered face arrays.

Definition at line 153 of file CombinatorialEmbedding.h.

AdjEntryArray<face> ogdf::ConstCombinatorialEmbedding::m_rightFace

protected

The face to which an adjacency entry belongs.

Definition at line 150 of file CombinatorialEmbedding.h.

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

ogdf/basic/CombinatorialEmbedding.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework