Open
Graph Drawing
Framework

 v.2012.07
 

ogdf::ConstCombinatorialEmbedding Class Reference

Combinatorial embeddings of planar graphs. More...

#include <ogdf/basic/CombinatorialEmbedding.h>

+ Inheritance diagram for ogdf::ConstCombinatorialEmbedding:

List of all members.

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.
ConstCombinatorialEmbeddingoperator= (const ConstCombinatorialEmbedding &C)
 Assignment operator.
const GraphgetGraph () 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 Graphm_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< FaceElementm_faces
 The list of all faces.
int m_nFaces
 The number of faces.
ListPure< FaceArrayBase * > m_regFaceArrays
 The external face.
AdjEntryArray< facem_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:
adjis 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:
adjis 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:
fis 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: