Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Protected Member Functions | Protected Attributes

ogdf::ConstCombinatorialEmbedding Class Reference

Combinatorial embeddings of planar graphs. More...

#include <ogdf/basic/CombinatorialEmbedding.h>

Inheritance diagram for ogdf::ConstCombinatorialEmbedding:
ogdf::CombinatorialEmbedding ogdf::DualGraph

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.
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 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.
GraphList< FaceElement > m_faces
 The list of all faces.
int m_nFaces
 The number of faces.
int m_faceIdCount
 The index assigned to the next created face.
int m_faceArrayTableSize
 The current table size of face arrays.
AdjEntryArray< face > m_rightFace
 The face to which an adjacency entry belongs.
face m_externalFace
ListPure< FaceArrayBase * > m_regFaceArrays
 The external face.

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 149 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 235 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::faceArrayTableSize (  )  const [inline]

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

Definition at line 222 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::firstFace (  )  const [inline]

Returns the first face in the list of all faces.

Definition at line 196 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 188 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.
bool ogdf::ConstCombinatorialEmbedding::isBridge ( edge  e  )  const [inline]

Definition at line 248 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::lastFace (  )  const [inline]

Returns the last face in the list of all faces.

Definition at line 199 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 214 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::maxFaceIndex (  )  const [inline]

Returns the largest used face index.

Definition at line 219 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 202 of file CombinatorialEmbedding.h.

ogdf::ConstCombinatorialEmbedding::operator const Graph & (  )  const [inline]

Returns associated graph.

Reimplemented in ogdf::CombinatorialEmbedding.

Definition at line 191 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 208 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 243 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 152 of file CombinatorialEmbedding.h.

face ogdf::ConstCombinatorialEmbedding::m_externalFace [protected]

Definition at line 160 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_faceArrayTableSize [protected]

The current table size of face arrays.

Definition at line 157 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount [protected]

The index assigned to the next created face.

Definition at line 156 of file CombinatorialEmbedding.h.

GraphList<FaceElement> ogdf::ConstCombinatorialEmbedding::m_faces [protected]

The list of all faces.

Definition at line 154 of file CombinatorialEmbedding.h.

int ogdf::ConstCombinatorialEmbedding::m_nFaces [protected]

The number of faces.

Definition at line 155 of file CombinatorialEmbedding.h.

ListPure<FaceArrayBase*> ogdf::ConstCombinatorialEmbedding::m_regFaceArrays [mutable, protected]

The external face.

The registered face arrays.

Definition at line 162 of file CombinatorialEmbedding.h.

AdjEntryArray<face> ogdf::ConstCombinatorialEmbedding::m_rightFace [protected]

The face to which an adjacency entry belongs.

Definition at line 159 of file CombinatorialEmbedding.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:12 by doxygen 1.7.1.