Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ConstCombinatorialEmbedding Class Reference

Combinatorial embeddings of planar graphs. More...

#include <ogdf/basic/CombinatorialEmbedding.h>

+ Inheritance diagram for ogdf::ConstCombinatorialEmbedding:

Public Types

using face_iterator = internal::GraphIterator< face >
 Provides a bidirectional iterator to a face in a combinatorial embedding. More...
 

Public Member Functions

 ConstCombinatorialEmbedding ()
 Creates a combinatorial embedding associated with no graph. More...
 
 ConstCombinatorialEmbedding (const Graph &G)
 Creates a combinatorial embedding of graph G. More...
 
 ConstCombinatorialEmbedding (const ConstCombinatorialEmbedding &C)
 Copy constructor. More...
 
ConstCombinatorialEmbeddingoperator= (const ConstCombinatorialEmbedding &C)
 Assignment operator. More...
 
virtual ~ConstCombinatorialEmbedding ()
 Destructor. More...
 
bool valid () const
 Returns whether the embedding is associated with a graph. More...
 
const GraphgetGraph () const
 Returns the associated graph of the combinatorial embedding. More...
 
 operator const Graph & () const
 Returns associated graph. More...
 
face firstFace () const
 Returns the first face in the list of all faces. More...
 
face lastFace () const
 Returns the last face in the list of all faces. More...
 
int numberOfFaces () const
 Returns the number of faces. More...
 
face rightFace (adjEntry adj) const
 Returns the face to the right of adj, i.e., the face containing adj. More...
 
face leftFace (adjEntry adj) const
 Returns the face to the left of adj, i.e., the face containing the twin of adj. More...
 
int maxFaceIndex () const
 Returns the largest used face index. More...
 
int faceArrayTableSize () const
 Returns the table size of face arrays associated with this embedding. More...
 
face chooseFace (std::function< bool(face)> includeFace=[](face) { return true;}, bool isFastTest=true) const
 Returns a random face. More...
 
face maximalFace () const
 Returns a face of maximal size. More...
 
face externalFace () const
 Returns the external face. More...
 
void setExternalFace (face f)
 Sets the external face to f. More...
 
bool isBridge (edge e) const
 
void init (const Graph &G)
 Initializes the embedding for graph G. More...
 
void init ()
 
void computeFaces ()
 Computes the list of faces. More...
 
ListIterator< FaceArrayBase * > registerArray (FaceArrayBase *pFaceArray) const
 Registers the face array pFaceArray. More...
 
void unregisterArray (ListIterator< FaceArrayBase * > it) const
 Unregisters the face array identified by it. More...
 
void moveRegisterArray (ListIterator< FaceArrayBase * > it, FaceArrayBase *pFaceArray) const
 Move the registration it of a node array to pFaceArray (used with move semantics for face arrays). More...
 
adjEntry findCommonFace (const node v, const node w, bool left=true) const
 Identifies a common face of two nodes and returns the respective adjacency entry. More...
 
adjEntry findCommonFace (const node v, const node w, adjEntry &adjW, bool left=true) const
 Identifies a common face of two nodes and returns the respective adjacency entry. More...
 

Public Attributes

internal::GraphObjectContainer< FaceElementfaces
 The container containing all face objects. More...
 

Protected Member Functions

face createFaceElement (adjEntry adjFirst)
 Create a new face. More...
 
void reinitArrays ()
 Reinitialize associated face arrays. More...
 

Protected Attributes

const Graphm_cpGraph
 The associated graph. More...
 
face m_externalFace
 
int m_faceArrayTableSize
 The current table size of face arrays. More...
 
int m_faceIdCount
 The index assigned to the next created face. More...
 
std::mutex m_mutexRegArrays
 The critical section for protecting shared acces to register/unregister methods. More...
 
ListPure< FaceArrayBase * > m_regFaceArrays
 The external face. More...
 
AdjEntryArray< facem_rightFace
 The face to which an adjacency entry belongs. More...
 

Detailed Description

Combinatorial embeddings of planar graphs.

Maintains a combinatorial embedding of an embedded connected 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.

Thread Safety

The class Graph allows shared access of threads to const methods only. If one thread executes a non-const method, shared access is no longer thread-safe.

See also
CombinatorialEmbedding provides additional functionality for modifying the embedding.

Definition at line 198 of file CombinatorialEmbedding.h.

Member Typedef Documentation

◆ face_iterator

Provides a bidirectional iterator to a face in a combinatorial embedding.

Definition at line 217 of file CombinatorialEmbedding.h.

Constructor & Destructor Documentation

◆ ConstCombinatorialEmbedding() [1/3]

ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding ( )

Creates a combinatorial embedding associated with no graph.

◆ ConstCombinatorialEmbedding() [2/3]

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.

◆ ConstCombinatorialEmbedding() [3/3]

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

Copy constructor.

◆ ~ConstCombinatorialEmbedding()

virtual ogdf::ConstCombinatorialEmbedding::~ConstCombinatorialEmbedding ( )
virtual

Destructor.

Member Function Documentation

◆ chooseFace()

face ogdf::ConstCombinatorialEmbedding::chooseFace ( std::function< bool(face)>  includeFace = [](face) { return true;},
bool  isFastTest = true 
) const

Returns a random face.

nullptr is returned if no feasible face exists.

See also
chooseIteratorFrom

◆ computeFaces()

void ogdf::ConstCombinatorialEmbedding::computeFaces ( )

Computes the list of faces.

◆ createFaceElement()

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

Create a new face.

◆ externalFace()

face ogdf::ConstCombinatorialEmbedding::externalFace ( ) const
inline

Returns the external face.

Definition at line 306 of file CombinatorialEmbedding.h.

◆ faceArrayTableSize()

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

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

Definition at line 290 of file CombinatorialEmbedding.h.

◆ findCommonFace() [1/2]

adjEntry ogdf::ConstCombinatorialEmbedding::findCommonFace ( const node  v,
const node  w,
adjEntry adjW,
bool  left = true 
) const

Identifies a common face of two nodes and returns the respective adjacency entry.

Parameters
vThe first node, an adjacency entry of this node will be returned
wThe second node
adjWThe adjacency entry to the right of a common face of v and w, incident to w.
leftWhether the common face should lie upon the left side of v and w.
Returns
The adjacency entry to the right of a common face of v and w, incident to v.

◆ findCommonFace() [2/2]

adjEntry ogdf::ConstCombinatorialEmbedding::findCommonFace ( const node  v,
const node  w,
bool  left = true 
) const
inline

Identifies a common face of two nodes and returns the respective adjacency entry.

Parameters
vThe first node, an adjacency entry of this node will be returned
wThe second node
leftWhether the common face should lie upon the left side of v and w.
Returns
The adjacency entry to the right of a common face of v and w, incident to v.

Definition at line 369 of file CombinatorialEmbedding.h.

◆ firstFace()

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

Returns the first face in the list of all faces.

Definition at line 264 of file CombinatorialEmbedding.h.

◆ getGraph()

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

Returns the associated graph of the combinatorial embedding.

Precondition
The associated graph exists. See valid().

Definition at line 253 of file CombinatorialEmbedding.h.

◆ init() [1/2]

void ogdf::ConstCombinatorialEmbedding::init ( )

◆ init() [2/2]

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.

◆ isBridge()

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

Definition at line 319 of file CombinatorialEmbedding.h.

◆ lastFace()

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

Returns the last face in the list of all faces.

Definition at line 267 of file CombinatorialEmbedding.h.

◆ leftFace()

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

◆ maxFaceIndex()

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

Returns the largest used face index.

Definition at line 287 of file CombinatorialEmbedding.h.

◆ maximalFace()

face ogdf::ConstCombinatorialEmbedding::maximalFace ( ) const

Returns a face of maximal size.

◆ moveRegisterArray()

void ogdf::ConstCombinatorialEmbedding::moveRegisterArray ( ListIterator< FaceArrayBase * >  it,
FaceArrayBase pFaceArray 
) const

Move the registration it of a node array to pFaceArray (used with move semantics for face arrays).

◆ numberOfFaces()

int ogdf::ConstCombinatorialEmbedding::numberOfFaces ( ) const
inline

Returns the number of faces.

Definition at line 270 of file CombinatorialEmbedding.h.

◆ operator const Graph &()

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

Returns associated graph.

Definition at line 259 of file CombinatorialEmbedding.h.

◆ operator=()

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

Assignment operator.

◆ registerArray()

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

Registers the face array pFaceArray.

This method is only used by face arrays.

◆ reinitArrays()

void ogdf::ConstCombinatorialEmbedding::reinitArrays ( )
protected

Reinitialize associated face arrays.

◆ rightFace()

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

◆ setExternalFace()

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

Sets the external face to f.

Parameters
fis a face in this embedding.

Definition at line 314 of file CombinatorialEmbedding.h.

◆ unregisterArray()

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

Unregisters the face array identified by it.

This method is only used by face arrays.

◆ valid()

bool ogdf::ConstCombinatorialEmbedding::valid ( ) const
inline

Returns whether the embedding is associated with a graph.

Definition at line 246 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ faces

internal::GraphObjectContainer<FaceElement> ogdf::ConstCombinatorialEmbedding::faces

The container containing all face objects.

Definition at line 220 of file CombinatorialEmbedding.h.

◆ m_cpGraph

const Graph* ogdf::ConstCombinatorialEmbedding::m_cpGraph
protected

The associated graph.

Definition at line 201 of file CombinatorialEmbedding.h.

◆ m_externalFace

face ogdf::ConstCombinatorialEmbedding::m_externalFace
protected

Definition at line 207 of file CombinatorialEmbedding.h.

◆ m_faceArrayTableSize

int ogdf::ConstCombinatorialEmbedding::m_faceArrayTableSize
protected

The current table size of face arrays.

Definition at line 204 of file CombinatorialEmbedding.h.

◆ m_faceIdCount

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount
protected

The index assigned to the next created face.

Definition at line 203 of file CombinatorialEmbedding.h.

◆ m_mutexRegArrays

std::mutex ogdf::ConstCombinatorialEmbedding::m_mutexRegArrays
mutableprotected

The critical section for protecting shared acces to register/unregister methods.

Definition at line 212 of file CombinatorialEmbedding.h.

◆ m_regFaceArrays

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

The external face.

The registered face arrays.

Definition at line 209 of file CombinatorialEmbedding.h.

◆ m_rightFace

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

The face to which an adjacency entry belongs.

Definition at line 206 of file CombinatorialEmbedding.h.


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