Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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 >
 The external face. More...
 
- Public Types inherited from ogdf::RegistryBase< Key, Registry, Iterator >
using iterator_type = Iterator
 
using key_type = Key
 
using registered_array_type = internal::RegisteredArrayBase< Registry >
 
using registration_iterator_type = typename registration_list_type::iterator
 
using registration_list_type = std::list< registered_array_type *, OGDFAllocator< registered_array_type * > >
 
using registry_type = Registry
 

Public Member Functions

 ConstCombinatorialEmbedding ()
 Creates a combinatorial embedding associated with no graph. More...
 
 ConstCombinatorialEmbedding (const ConstCombinatorialEmbedding &C)
 Copy constructor. More...
 
 ConstCombinatorialEmbedding (const Graph &G)
 Creates a combinatorial embedding of graph G. More...
 
virtual ~ConstCombinatorialEmbedding ()
 Destructor. More...
 
face_iterator begin () const
 
int calculateArraySize (int add) const
 
face chooseFace (std::function< bool(face)> includeFace=[](face) { return true;}, bool isFastTest=true) const
 Returns a random face. More...
 
void computeFaces ()
 Computes the list of faces. More...
 
void consistencyCheck () const
 Asserts that this embedding is consistent. More...
 
face_iterator end () const
 
face externalFace () const
 Returns the external face. 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...
 
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...
 
face firstFace () const
 Returns the first face in the list of all faces. More...
 
const GraphgetGraph () const
 Returns the associated graph of the combinatorial embedding. More...
 
void init ()
 
void init (const Graph &G)
 Initializes the embedding for graph G. More...
 
bool isBridge (edge e) const
 
bool isKeyAssociated (face key) const
 
face lastFace () const
 Returns the last face in the list of all faces. 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...
 
face maximalFace () const
 Returns a face of maximal size. More...
 
int maxKeyIndex () const
 
int numberOfFaces () const
 Returns the number of faces. More...
 
 operator const Graph & () const
 Returns associated graph. More...
 
ConstCombinatorialEmbeddingoperator= (const ConstCombinatorialEmbedding &C)
 Assignment operator. More...
 
face rightFace (adjEntry adj) const
 Returns the face to the right of adj, i.e., the face containing adj. More...
 
void setExternalFace (face f)
 Sets the external face to f. More...
 
bool valid () const
 Returns whether the embedding is associated with a graph. More...
 
- Public Member Functions inherited from ogdf::RegistryBase< Key, Registry, Iterator >
 RegistryBase (const RegistryBase &copy)=delete
 
 RegistryBase (RegistryBase &&move) noexcept=delete
 
virtual ~RegistryBase () noexcept
 Destructor. Unregisters all associated arrays. More...
 
void copyArrayEntries (int toIndex, int fromIndex)
 Copies the entry from fromIndex to toIndex in all registered arrays. More...
 
int getArraySize () const
 Returns the current size of all registered arrays. More...
 
const registration_list_typegetRegisteredArrays () const
 Returns a reference to the list of all registered arrays. More...
 
bool isAutoShrink () const
 Returns whether the registry allows arrays to shrink when keys are removed. More...
 
void keyAdded (Key key)
 Records the addition of a new key and resizes all registered arrays if necessary. More...
 
void keyRemoved (Key key)
 Records the deletion of a key and resizes all registered arrays if auto shrink is enabled. More...
 
void keysCleared ()
 Records that all keys have been cleared. If auto shrink is enabled, all arrays are cleared and resized to 0. More...
 
void moveRegisterArray (registration_iterator_type it, registered_array_type *pArray) const
 Stores array pArray at position it in the list of registered arrays. More...
 
RegistryBaseoperator= (const RegistryBase &other)=delete
 
RegistryBaseoperator= (RegistryBase &&other) noexcept=delete
 
OGDF_NODISCARD registration_iterator_type registerArray (registered_array_type *pArray) const
 Registers a new array with this registry. More...
 
void reserveSpace (int new_keys)
 Resizes all arrays to make space of new_keys new keys. More...
 
void resizeArrays ()
 Resizes all arrays to the size requested by calculateArraySize(). Only shrinks the arrays if auto shrink is enabled. More...
 
void resizeArrays (int size)
 Resizes all arrays to size. Only shrinks the arrays if auto shrink is enabled. More...
 
void resizeArrays (int size, bool shrink)
 Resizes all arrays to size. If shrink is true, the arrays may also shrink. More...
 
void setAutoShrink (bool mAutoShrink)
 Specifies whether the registry allows arrays to shrink when keys are removed. More...
 
void swapArrayEntries (int index1, int index2)
 Swaps the entries at index1 and index2 in all registered arrays. More...
 
void unregisterArray (registration_iterator_type it) const noexcept
 Unregisters an array associated with this registry. More...
 
void unregisterArrays () noexcept
 Unregister all associated arrays. More...
 

Static Public Member Functions

static int keyToIndex (face key)
 

Public Attributes

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

Protected Member Functions

face createFaceElement (adjEntry adjFirst)
 Create a new face. More...
 
- Protected Member Functions inherited from ogdf::RegistryBase< Key, Registry, Iterator >
 RegistryBase ()=default
 

Protected Attributes

const Graphm_cpGraph
 The associated graph. More...
 
face m_externalFace
 
int m_faceIdCount
 The index assigned to the next created 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 216 of file CombinatorialEmbedding.h.

Member Typedef Documentation

◆ face_iterator

The external face.

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

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

◆ begin()

face_iterator ogdf::ConstCombinatorialEmbedding::begin ( ) const
inline

Definition at line 358 of file CombinatorialEmbedding.h.

◆ calculateArraySize()

int ogdf::ConstCombinatorialEmbedding::calculateArraySize ( int  add) const
inline

Definition at line 354 of file CombinatorialEmbedding.h.

◆ 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.

◆ consistencyCheck()

void ogdf::ConstCombinatorialEmbedding::consistencyCheck ( ) const

Asserts that this embedding is consistent.

◆ createFaceElement()

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

Create a new face.

◆ end()

face_iterator ogdf::ConstCombinatorialEmbedding::end ( ) const
inline

Definition at line 360 of file CombinatorialEmbedding.h.

◆ externalFace()

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

Returns the external face.

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

◆ firstFace()

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

Returns the first face in the list of all faces.

Definition at line 267 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 258 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 315 of file CombinatorialEmbedding.h.

◆ isKeyAssociated()

bool ogdf::ConstCombinatorialEmbedding::isKeyAssociated ( face  key) const
inline

Definition at line 338 of file CombinatorialEmbedding.h.

◆ keyToIndex()

static int ogdf::ConstCombinatorialEmbedding::keyToIndex ( face  key)
inlinestatic

Definition at line 336 of file CombinatorialEmbedding.h.

◆ lastFace()

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

Returns the last face in the list of all faces.

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

◆ maxFaceIndex()

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

Returns the largest used face index.

Definition at line 288 of file CombinatorialEmbedding.h.

◆ maximalFace()

face ogdf::ConstCombinatorialEmbedding::maximalFace ( ) const

Returns a face of maximal size.

◆ maxKeyIndex()

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

Definition at line 356 of file CombinatorialEmbedding.h.

◆ numberOfFaces()

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

Returns the number of faces.

Definition at line 273 of file CombinatorialEmbedding.h.

◆ operator const Graph &()

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

Returns associated graph.

Definition at line 264 of file CombinatorialEmbedding.h.

◆ operator=()

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

Assignment operator.

◆ 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 279 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 310 of file CombinatorialEmbedding.h.

◆ valid()

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

Returns whether the embedding is associated with a graph.

Definition at line 252 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ faces

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

The container containing all face objects.

Definition at line 230 of file CombinatorialEmbedding.h.

◆ m_cpGraph

const Graph* ogdf::ConstCombinatorialEmbedding::m_cpGraph
protected

The associated graph.

Definition at line 218 of file CombinatorialEmbedding.h.

◆ m_externalFace

face ogdf::ConstCombinatorialEmbedding::m_externalFace
protected

Definition at line 223 of file CombinatorialEmbedding.h.

◆ m_faceIdCount

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount
protected

The index assigned to the next created face.

Definition at line 220 of file CombinatorialEmbedding.h.

◆ m_rightFace

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

The face to which an adjacency entry belongs.

Definition at line 222 of file CombinatorialEmbedding.h.


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