Combinatorial embeddings of planar graphs. More...
#include <ogdf/basic/CombinatorialEmbedding.h>
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 Graph & | getGraph () 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... | |
ConstCombinatorialEmbedding & | operator= (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 ©)=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_type & | getRegisteredArrays () 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... | |
RegistryBase & | operator= (const RegistryBase &other)=delete |
RegistryBase & | operator= (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< FaceElement > | faces |
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 Graph * | m_cpGraph |
The associated graph. More... | |
face | m_externalFace |
int | m_faceIdCount |
The index assigned to the next created face. More... | |
AdjEntryArray< face > | m_rightFace |
The face to which an adjacency entry belongs. More... | |
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.
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.
Definition at line 216 of file CombinatorialEmbedding.h.
The external face.
Provides a bidirectional iterator to a face in a combinatorial embedding.
Definition at line 227 of file CombinatorialEmbedding.h.
ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding | ( | ) |
Creates a combinatorial embedding associated with no graph.
|
explicit |
Creates a combinatorial embedding of graph G
.
G
must be embedded, i.e., the adjacency lists of its nodes must define an embedding. ogdf::ConstCombinatorialEmbedding::ConstCombinatorialEmbedding | ( | const ConstCombinatorialEmbedding & | C | ) |
Copy constructor.
|
virtual |
Destructor.
|
inline |
Definition at line 358 of file CombinatorialEmbedding.h.
|
inline |
Definition at line 354 of file CombinatorialEmbedding.h.
void ogdf::ConstCombinatorialEmbedding::computeFaces | ( | ) |
Computes the list of faces.
void ogdf::ConstCombinatorialEmbedding::consistencyCheck | ( | ) | const |
Asserts that this embedding is consistent.
Create a new face.
|
inline |
Definition at line 360 of file CombinatorialEmbedding.h.
|
inline |
Returns the external face.
Definition at line 304 of file CombinatorialEmbedding.h.
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.
v | The first node, an adjacency entry of this node will be returned |
w | The second node |
adjW | The adjacency entry to the right of a common face of v and w, incident to w. |
left | Whether the common face should lie upon the left side of v and w . |
|
inline |
Identifies a common face of two nodes and returns the respective adjacency entry.
v | The first node, an adjacency entry of this node will be returned |
w | The second node |
left | Whether the common face should lie upon the left side of v and w . |
Definition at line 371 of file CombinatorialEmbedding.h.
|
inline |
Returns the first face in the list of all faces.
Definition at line 267 of file CombinatorialEmbedding.h.
|
inline |
Returns the associated graph of the combinatorial embedding.
Definition at line 258 of file CombinatorialEmbedding.h.
void ogdf::ConstCombinatorialEmbedding::init | ( | ) |
void ogdf::ConstCombinatorialEmbedding::init | ( | const Graph & | G | ) |
Initializes the embedding for graph G
.
G
must be embedded, i.e., the adjacency lists of its nodes must define an embedding.
|
inline |
Definition at line 315 of file CombinatorialEmbedding.h.
|
inline |
Definition at line 338 of file CombinatorialEmbedding.h.
|
inlinestatic |
Definition at line 336 of file CombinatorialEmbedding.h.
|
inline |
Returns the last face in the list of all faces.
Definition at line 270 of file CombinatorialEmbedding.h.
Returns the face to the left of adj
, i.e., the face containing the twin of adj
.
adj | is an adjacency element in the associated graph. |
Definition at line 285 of file CombinatorialEmbedding.h.
|
inline |
Returns the largest used face index.
Definition at line 288 of file CombinatorialEmbedding.h.
face ogdf::ConstCombinatorialEmbedding::maximalFace | ( | ) | const |
Returns a face of maximal size.
|
inline |
Definition at line 356 of file CombinatorialEmbedding.h.
|
inline |
Returns the number of faces.
Definition at line 273 of file CombinatorialEmbedding.h.
|
inline |
Returns associated graph.
Definition at line 264 of file CombinatorialEmbedding.h.
ConstCombinatorialEmbedding& ogdf::ConstCombinatorialEmbedding::operator= | ( | const ConstCombinatorialEmbedding & | C | ) |
Assignment operator.
Returns the face to the right of adj
, i.e., the face containing adj
.
adj | is an adjecency element in the associated graph. |
Definition at line 279 of file CombinatorialEmbedding.h.
|
inline |
Sets the external face to f
.
f | is a face in this embedding. |
Definition at line 310 of file CombinatorialEmbedding.h.
|
inline |
Returns whether the embedding is associated with a graph.
Definition at line 252 of file CombinatorialEmbedding.h.
internal::GraphObjectContainer<FaceElement> ogdf::ConstCombinatorialEmbedding::faces |
The container containing all face objects.
Definition at line 230 of file CombinatorialEmbedding.h.
|
protected |
The associated graph.
Definition at line 218 of file CombinatorialEmbedding.h.
|
protected |
Definition at line 223 of file CombinatorialEmbedding.h.
|
protected |
The index assigned to the next created face.
Definition at line 220 of file CombinatorialEmbedding.h.
|
protected |
The face to which an adjacency entry belongs.
Definition at line 222 of file CombinatorialEmbedding.h.