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.

Public Member Functions

	ConstCombinatorialEmbedding (const Graph &G)
	Creates a combinatorial embedding of graph `G`.

	ConstCombinatorialEmbedding (const ConstCombinatorialEmbedding &C)
	Copy constructor.

ConstCombinatorialEmbedding &	operator= (const ConstCombinatorialEmbedding &C)
	Assignment operator.

bool	valid () const
	Returns whether the embedding is associated with a graph.


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 (std::function< bool(face)> includeFace=[](face) { return true;}, bool isFastTest=true) 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	init ()

void	computeFaces ()
	Computes the list of faces.


ListIterator< FaceArrayBase * >	registerArray (FaceArrayBase *pFaceArray) const
	Registers the face array `pFaceArray`.

void	unregisterArray (ListIterator< FaceArrayBase * > it) const
	Unregisters the face array identified by `it`.

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

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.

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.

Public Attributes
internal::GraphObjectContainer< FaceElement >	faces
	The container containing all face objects.

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.

face	m_externalFace

int	m_faceArrayTableSize
	The current table size of face arrays.

int	m_faceIdCount
	The index assigned to the next created face.

std::mutex	m_mutexRegArrays
	The critical section for protecting shared acces to register/unregister methods.

ListPure< FaceArrayBase * >	m_regFaceArrays
	The external face.

AdjEntryArray< face >	m_rightFace
	The face to which an adjacency entry belongs.

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

Member Typedef Documentation

◆ face_iterator

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

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

Definition at line 210 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 301 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 283 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 257 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 246 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 312 of file CombinatorialEmbedding.h.

◆ lastFace()

face ogdf::ConstCombinatorialEmbedding::lastFace ( ) const

inline

Returns the last face in the list of all faces.

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

◆ maxFaceIndex()

int ogdf::ConstCombinatorialEmbedding::maxFaceIndex ( ) const

inline

Returns the largest used face index.

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

◆ operator const Graph &()

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

inline

Returns associated graph.

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

adj	is an adjecency element in the associated graph.

Definition at line 269 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 307 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 239 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ faces

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

The container containing all face objects.

Definition at line 213 of file CombinatorialEmbedding.h.

◆ m_cpGraph

const Graph* ogdf::ConstCombinatorialEmbedding::m_cpGraph

protected

The associated graph.

Definition at line 194 of file CombinatorialEmbedding.h.

◆ m_externalFace

face ogdf::ConstCombinatorialEmbedding::m_externalFace

protected

Definition at line 200 of file CombinatorialEmbedding.h.

◆ m_faceArrayTableSize

int ogdf::ConstCombinatorialEmbedding::m_faceArrayTableSize

protected

The current table size of face arrays.

Definition at line 197 of file CombinatorialEmbedding.h.

◆ m_faceIdCount

int ogdf::ConstCombinatorialEmbedding::m_faceIdCount

protected

The index assigned to the next created face.

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

◆ m_regFaceArrays

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

mutableprotected

The external face.

The registered face arrays.

Definition at line 202 of file CombinatorialEmbedding.h.

◆ m_rightFace

AdjEntryArray<face> ogdf::ConstCombinatorialEmbedding::m_rightFace

protected

The face to which an adjacency entry belongs.

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

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

◆ chooseFace()

◆ computeFaces()

◆ createFaceElement()

◆ externalFace()

◆ faceArrayTableSize()

◆ findCommonFace() [1/2]

◆ findCommonFace() [2/2]

◆ firstFace()

◆ getGraph()

◆ init() [1/2]

◆ init() [2/2]

◆ isBridge()

◆ lastFace()

◆ leftFace()

◆ maxFaceIndex()

◆ maximalFace()

◆ moveRegisterArray()

◆ numberOfFaces()

◆ operator const Graph &()

◆ operator=()

◆ registerArray()

◆ reinitArrays()

◆ rightFace()

◆ setExternalFace()

◆ unregisterArray()

◆ valid()

Member Data Documentation

◆ faces

◆ m_cpGraph

◆ m_externalFace

◆ m_faceArrayTableSize

◆ m_faceIdCount

◆ m_mutexRegArrays

◆ m_regFaceArrays

◆ m_rightFace

Open
Graph Drawing
Framework