Combinatorial embeddings of planar graphs with modification functionality. More...

#include <ogdf/basic/CombinatorialEmbedding.h>

Inheritance diagram for ogdf::CombinatorialEmbedding:

Public Member Functions

	CombinatorialEmbedding ()
	Creates a combinatorial embedding associated with no graph. More...

	CombinatorialEmbedding (Graph &G)
	Creates a combinatorial embedding of graph `G`. More...

Access to the associated graph
const Graph &	getGraph () const
	Returns the associated graph. More...

Graph &	getGraph ()

	operator const Graph & () const

	operator Graph & ()

Initialization
void	init (Graph &G)
	Initializes the embedding for graph `G`. More...

void	clear ()
	Removes all nodes, edges, and faces from the graph and the embedding. More...

Update of embedding
edge	split (edge e)
	Splits edge `e=`(v,w) into e=(v,u) and e'=(u,w) creating a new node u. More...

void	unsplit (edge eIn, edge eOut)
	Undoes a split operation. More...

node	splitNode (adjEntry adjStartLeft, adjEntry adjStartRight)
	Splits a node while preserving the order of adjacency entries. More...

node	contract (edge e, bool keepSelfLoops=false)
	Contracts edge `e` while preserving the order of adjacency entries. More...

edge	splitFace (adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter=false)
	Splits a face by inserting a new edge. More...

edge	addEdgeToIsolatedNode (node v, adjEntry adjTgt)
	Inserts a new edge similarly to splitFace without having to call computeFaces again. More...

edge	addEdgeToIsolatedNode (adjEntry adjSrc, node v)
	Inserts a new edge similarly to splitFace without having to call computeFaces again. More...

face	joinFaces (edge e)
	Removes edge `e` and joins the two faces adjacent to `e`. More...

void	reverseEdge (edge e)
	Reverses edges `e` and updates embedding. More...

void	moveBridge (adjEntry adjBridge, adjEntry adjBefore)
	Moves a bridge in the graph. More...

void	removeDeg1 (node v)
	Removes degree-1 node `v`. More...

void	updateMerger (edge e, face fRight, face fLeft)
	Update face information after inserting a merger in a copy graph. More...

Public Member Functions inherited from ogdf::ConstCombinatorialEmbedding
	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...

Private Member Functions
	CombinatorialEmbedding (const CombinatorialEmbedding &)=delete

edge	addEdgeToIsolatedNode (adjEntry adj, node v, bool adjSrc)
	Inserts a new edge similarly to splitFace without having to call computeFaces again. More...

CombinatorialEmbedding &	operator= (const CombinatorialEmbedding &)=delete

Private Attributes
Graph *	m_pGraph
	The associated graph. More...

Friends
class	GraphCopy

Additional Inherited Members
Public Types inherited from ogdf::ConstCombinatorialEmbedding
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

Static Public Member Functions inherited from ogdf::ConstCombinatorialEmbedding
static int	keyToIndex (face key)

Public Attributes inherited from ogdf::ConstCombinatorialEmbedding
internal::GraphObjectContainer< FaceElement >	faces
	The container containing all face objects. More...

Protected Member Functions inherited from ogdf::ConstCombinatorialEmbedding
face	createFaceElement (adjEntry adjFirst)
	Create a new face. More...

Protected Member Functions inherited from ogdf::RegistryBase< Key, Registry, Iterator >
	RegistryBase ()=default

Protected Attributes inherited from ogdf::ConstCombinatorialEmbedding
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 with modification functionality.

Maintains a combinatorial embedding of an embedded connected graph, i.e., the set of faces, and provides method for modifying the embedding, e.g., by inserting edges.

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.

Definition at line 406 of file CombinatorialEmbedding.h.

Constructor & Destructor Documentation

◆ CombinatorialEmbedding() [1/3]

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( const CombinatorialEmbedding & )

privatedelete

◆ CombinatorialEmbedding() [2/3]

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( )

inline

Creates a combinatorial embedding associated with no graph.

Definition at line 421 of file CombinatorialEmbedding.h.

◆ CombinatorialEmbedding() [3/3]

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( Graph & G )

inlineexplicit

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.

Definition at line 429 of file CombinatorialEmbedding.h.

Member Function Documentation

◆ addEdgeToIsolatedNode() [1/3]

edge ogdf::CombinatorialEmbedding::addEdgeToIsolatedNode	(	adjEntry	adj,
		node	v,
		bool	adjSrc
	)

private

Inserts a new edge similarly to splitFace without having to call computeFaces again.

Parameters

adj	The adjacency entry belonging to the face that we want to insert the new edge into
v	The degree 0 node.
adjSrc	whether v will be the target node.

Returns: The new edge.

◆ addEdgeToIsolatedNode() [2/3]

edge ogdf::CombinatorialEmbedding::addEdgeToIsolatedNode	(	adjEntry	adjSrc,
		node	v
	)

Inserts a new edge similarly to splitFace without having to call computeFaces again.

Creates a new edge from the node of adjSrc to the degree 0 node v. The face that adjSrc belongs to is split.

Returns: The new edge.

◆ addEdgeToIsolatedNode() [3/3]

edge ogdf::CombinatorialEmbedding::addEdgeToIsolatedNode	(	node	v,
		adjEntry	adjTgt
	)

Inserts a new edge similarly to splitFace without having to call computeFaces again.

Creates a new edge from the degree 0 node v to the node of adjTgt. The face that adjTgt belongs to is split.

Returns: The new edge.

◆ clear()

void ogdf::CombinatorialEmbedding::clear ( )

Removes all nodes, edges, and faces from the graph and the embedding.

◆ contract()

node ogdf::CombinatorialEmbedding::contract	(	edge	e,
		bool	keepSelfLoops = `false`
	)

Contracts edge e while preserving the order of adjacency entries.

Parameters

e	is the edge to be contracted.
keepSelfLoops	determines whether edges parallel to `e` will result in self-loops or not (in the latter case, they will also be contracted).

Returns: The endpoint of e to which all edges have been moved. The implementation ensures this to be the source of the former edge e.

◆ getGraph() [1/2]

Graph& ogdf::CombinatorialEmbedding::getGraph ( )

inline

Definition at line 443 of file CombinatorialEmbedding.h.

◆ getGraph() [2/2]

const Graph& ogdf::CombinatorialEmbedding::getGraph ( ) const

inline

Returns the associated graph.

Definition at line 438 of file CombinatorialEmbedding.h.

◆ init()

void ogdf::CombinatorialEmbedding::init ( Graph & G )

inline

Initializes the embedding for graph G.

Precondition: Graph G must be embedded, i.e., the adjacency lists of its nodes must define an embedding.

Definition at line 464 of file CombinatorialEmbedding.h.

◆ joinFaces()

face ogdf::CombinatorialEmbedding::joinFaces ( edge e )

Removes edge e and joins the two faces adjacent to e.

Parameters

e	is an edge in the associated graph.

Returns: the resulting (joined) face.

◆ moveBridge()

void ogdf::CombinatorialEmbedding::moveBridge	(	adjEntry	adjBridge,
		adjEntry	adjBefore
	)

Moves a bridge in the graph.

◆ operator const Graph &()

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

inline

Definition at line 448 of file CombinatorialEmbedding.h.

◆ operator Graph &()

ogdf::CombinatorialEmbedding::operator Graph & ( )

inline

Definition at line 450 of file CombinatorialEmbedding.h.

◆ operator=()

CombinatorialEmbedding& ogdf::CombinatorialEmbedding::operator= ( const CombinatorialEmbedding & )

privatedelete

◆ removeDeg1()

void ogdf::CombinatorialEmbedding::removeDeg1 ( node v )

Removes degree-1 node v.

◆ reverseEdge()

void ogdf::CombinatorialEmbedding::reverseEdge ( edge e )

Reverses edges e and updates embedding.

◆ split()

edge ogdf::CombinatorialEmbedding::split ( edge e )

Splits edge e=(v,w) into e=(v,u) and e'=(u,w) creating a new node u.

Parameters

e	is the edge to be split; `e` is modified by the split.

Returns: the edge e'.

◆ splitFace()

edge ogdf::CombinatorialEmbedding::splitFace	(	adjEntry	adjSrc,
		adjEntry	adjTgt,
		bool	sourceAfter = `false`
	)

Splits a face by inserting a new edge.

Creates a new edge from the node of adjSrc to the one of adjTgt. Note that this can also be achieved by inserting an edge in the underlying graph directly and calling computeFaces again. In contrast, this operation achieves constant running time.

Precondition: adjSrc and adjTgt belong to the same face.

Parameters

adjSrc	The adjEntry after which the source adjEntry of the new edge should be inserted.
adjTgt	The adjEntry after which the target adjEntry of the new edge should be inserted.
sourceAfter	Only has an effect if `adjSrc` == `adjTgt`. Marks whether the source of the introduced self-loop comes after its target in the adjacency list.

Returns: The new edge.

◆ splitNode()

node ogdf::CombinatorialEmbedding::splitNode	(	adjEntry	adjStartLeft,
		adjEntry	adjStartRight
	)

Splits a node while preserving the order of adjacency entries.

This method splits a node v into two nodes vl and vr. Node vl receives all adjacent edges of v from adjStartLeft until the edge preceding adjStartRight, and vr the remaining nodes (thus adjStartRight is the first edge that goes to vr). The order of adjacency entries is preserved. Additionally, a new edge (vl,vr) is created, such that this edge is inserted before adjStartLeft and adjStartRight in the the adjacency lists of vl and vr.

Node v is modified to become node vl, and node vr is returned.

Parameters

adjStartLeft	is the first entry that goes to the left node.
adjStartRight	is the first entry that goes to the right node.

Returns: the newly created node.

◆ unsplit()

void ogdf::CombinatorialEmbedding::unsplit	(	edge	eIn,
		edge	eOut
	)

Undoes a split operation.

Parameters

eIn	is the edge (v,u).
eOut	is the edge (u,w).

◆ updateMerger()

void ogdf::CombinatorialEmbedding::updateMerger	(	edge	e,
		face	fRight,
		face	fLeft
	)

Update face information after inserting a merger in a copy graph.

Friends And Related Function Documentation

◆ GraphCopy

friend class GraphCopy

friend

Definition at line 407 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ m_pGraph

Graph* ogdf::CombinatorialEmbedding::m_pGraph

private

The associated graph.

Definition at line 409 of file CombinatorialEmbedding.h.

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

include/ogdf/basic/CombinatorialEmbedding.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Thread Safety

Constructor & Destructor Documentation

◆ CombinatorialEmbedding() [1/3]

◆ CombinatorialEmbedding() [2/3]

◆ CombinatorialEmbedding() [3/3]

Member Function Documentation

◆ addEdgeToIsolatedNode() [1/3]

◆ addEdgeToIsolatedNode() [2/3]

◆ addEdgeToIsolatedNode() [3/3]

◆ clear()

◆ contract()

◆ getGraph() [1/2]

◆ getGraph() [2/2]

◆ init()

◆ joinFaces()

◆ moveBridge()

◆ operator const Graph &()

◆ operator Graph &()

◆ operator=()

◆ removeDeg1()

◆ reverseEdge()

◆ split()

◆ splitFace()

◆ splitNode()

◆ unsplit()

◆ updateMerger()

Friends And Related Function Documentation

◆ GraphCopy

Member Data Documentation

◆ m_pGraph

Open
Graph Drawing
Framework