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

#include <ogdf/basic/CombinatorialEmbedding.h>

Inheritance diagram for ogdf::CombinatorialEmbedding:

Public Member Functions

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

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

Graph &	getGraph ()

	operator const Graph & () const

	operator Graph & ()

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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.

CombinatorialEmbedding &	operator= (const CombinatorialEmbedding &)=delete

Private Attributes
Graph *	m_pGraph
	The associated graph.

Friends
class	GraphCopy

Additional Inherited Members
Public Types inherited from ogdf::ConstCombinatorialEmbedding
using	face_iterator = internal::GraphIterator< face >
	Provides a bidirectional iterator to a face in a combinatorial embedding.

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

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

void	reinitArrays ()
	Reinitialize associated face arrays.

Protected Attributes inherited from ogdf::ConstCombinatorialEmbedding
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 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 402 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 417 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 425 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 439 of file CombinatorialEmbedding.h.

◆ getGraph() [2/2]

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

inline

Returns the associated graph.

Definition at line 434 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 460 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 444 of file CombinatorialEmbedding.h.

◆ operator Graph &()

ogdf::CombinatorialEmbedding::operator Graph & ( )

inline

Definition at line 446 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 Symbol Documentation

◆ GraphCopy

friend class GraphCopy

friend

Definition at line 403 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ m_pGraph

Graph* ogdf::CombinatorialEmbedding::m_pGraph

private

The associated graph.

Definition at line 405 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 Symbol Documentation

◆ GraphCopy

Member Data Documentation

◆ m_pGraph

Open
Graph Drawing
Framework