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 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 &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_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...

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

Member Typedef Documentation

◆ face_iterator

using ogdf::ConstCombinatorialEmbedding::face_iterator = internal::GraphIterator<face>

The external face.

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

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

◆ calculateArraySize()

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

inline

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

◆ externalFace()

face ogdf::ConstCombinatorialEmbedding::externalFace ( ) const

inline

Returns the external face.

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

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

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

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

Returns: The adjacency entry to the right of a common face of v and w, incident to v.

Definition at line 362 of file CombinatorialEmbedding.h.

◆ firstFace()

face ogdf::ConstCombinatorialEmbedding::firstFace ( ) const

inline

Returns the first face in the list of all faces.

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

◆ isKeyAssociated()

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

inline

Definition at line 329 of file CombinatorialEmbedding.h.

◆ keyToIndex()

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

inlinestatic

Definition at line 327 of file CombinatorialEmbedding.h.

◆ lastFace()

face ogdf::ConstCombinatorialEmbedding::lastFace ( ) const

inline

Returns the last face in the list of all faces.

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

adj	is an adjacency element in the associated graph.

Definition at line 276 of file CombinatorialEmbedding.h.

◆ maxFaceIndex()

int ogdf::ConstCombinatorialEmbedding::maxFaceIndex ( ) const

inline

Returns the largest used face index.

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

◆ numberOfFaces()

int ogdf::ConstCombinatorialEmbedding::numberOfFaces ( ) const

inline

Returns the number of faces.

Definition at line 264 of file CombinatorialEmbedding.h.

◆ operator const Graph &()

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

inline

Returns associated graph.

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

adj	is an adjecency element in the associated graph.

Definition at line 270 of file CombinatorialEmbedding.h.

◆ setExternalFace()

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

inline

Sets the external face to f.

Parameters

f	is a face in this embedding.

Definition at line 301 of file CombinatorialEmbedding.h.

◆ valid()

bool ogdf::ConstCombinatorialEmbedding::valid ( ) const

inline

Returns whether the embedding is associated with a graph.

Definition at line 243 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ faces

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

The container containing all face objects.

Definition at line 221 of file CombinatorialEmbedding.h.

◆ m_cpGraph

const Graph* ogdf::ConstCombinatorialEmbedding::m_cpGraph

protected

The associated graph.

Definition at line 209 of file CombinatorialEmbedding.h.

◆ m_externalFace

face ogdf::ConstCombinatorialEmbedding::m_externalFace

protected

Definition at line 214 of file CombinatorialEmbedding.h.

◆ m_faceIdCount

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount

protected

The index assigned to the next created face.

Definition at line 211 of file CombinatorialEmbedding.h.

◆ m_rightFace

AdjEntryArray<face> ogdf::ConstCombinatorialEmbedding::m_rightFace

protected

The face to which an adjacency entry belongs.

Definition at line 213 of file CombinatorialEmbedding.h.

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

include/ogdf/basic/CombinatorialEmbedding.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Thread Safety

Member Typedef Documentation

◆ face_iterator

Constructor & Destructor Documentation

◆ ConstCombinatorialEmbedding() [1/3]

◆ ConstCombinatorialEmbedding() [2/3]

◆ ConstCombinatorialEmbedding() [3/3]

◆ ~ConstCombinatorialEmbedding()

Member Function Documentation

◆ begin()

◆ calculateArraySize()

◆ chooseFace()

◆ computeFaces()

◆ consistencyCheck()

◆ createFaceElement()

◆ end()

◆ externalFace()

◆ findCommonFace() [1/2]

◆ findCommonFace() [2/2]

◆ firstFace()

◆ getGraph()

◆ init() [1/2]

◆ init() [2/2]

◆ isBridge()

◆ isKeyAssociated()

◆ keyToIndex()

◆ lastFace()

◆ leftFace()

◆ maxFaceIndex()

◆ maximalFace()

◆ maxKeyIndex()

◆ numberOfFaces()

◆ operator const Graph &()

◆ operator=()

◆ rightFace()

◆ setExternalFace()

◆ valid()

Member Data Documentation

◆ faces

◆ m_cpGraph

◆ m_externalFace

◆ m_faceIdCount

◆ m_rightFace

Open
Graph Drawing
Framework