Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CombinatorialEmbedding Class Reference

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 GraphgetGraph () const
 Returns the associated graph. More...
 
GraphgetGraph ()
 
 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 Graph &G)
 Creates a combinatorial embedding of graph G. More...
 
 ConstCombinatorialEmbedding (const ConstCombinatorialEmbedding &C)
 Copy constructor. More...
 
ConstCombinatorialEmbeddingoperator= (const ConstCombinatorialEmbedding &C)
 Assignment operator. More...
 
virtual ~ConstCombinatorialEmbedding ()
 Destructor. More...
 
bool valid () const
 Returns whether the embedding is associated with a graph. More...
 
const GraphgetGraph () const
 Returns the associated graph of the combinatorial embedding. More...
 
 operator const Graph & () const
 Returns associated graph. More...
 
face firstFace () const
 Returns the first face in the list of all faces. More...
 
face lastFace () const
 Returns the last face in the list of all faces. More...
 
int numberOfFaces () const
 Returns the number of faces. More...
 
face rightFace (adjEntry adj) const
 Returns the face to the right of adj, i.e., the face containing adj. 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...
 
int faceArrayTableSize () const
 Returns the table size of face arrays associated with this embedding. More...
 
face chooseFace (std::function< bool(face)> includeFace=[](face) { return true;}, bool isFastTest=true) const
 Returns a random face. More...
 
face maximalFace () const
 Returns a face of maximal size. More...
 
face externalFace () const
 Returns the external face. More...
 
void setExternalFace (face f)
 Sets the external face to f. More...
 
bool isBridge (edge e) const
 
void init (const Graph &G)
 Initializes the embedding for graph G. More...
 
void init ()
 
void computeFaces ()
 Computes the list of faces. More...
 
ListIterator< FaceArrayBase * > registerArray (FaceArrayBase *pFaceArray) const
 Registers the face array pFaceArray. More...
 
void unregisterArray (ListIterator< FaceArrayBase * > it) const
 Unregisters the face array identified by it. More...
 
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). 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...
 
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...
 

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...
 
CombinatorialEmbeddingoperator= (const CombinatorialEmbedding &)=delete
 

Private Attributes

Graphm_pGraph
 The associated graph. More...
 

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. More...
 
- Public Attributes inherited from ogdf::ConstCombinatorialEmbedding
internal::GraphObjectContainer< FaceElementfaces
 The container containing all face objects. More...
 
- Protected Member Functions inherited from ogdf::ConstCombinatorialEmbedding
face createFaceElement (adjEntry adjFirst)
 Create a new face. More...
 
void reinitArrays ()
 Reinitialize associated face arrays. More...
 
- Protected Attributes inherited from ogdf::ConstCombinatorialEmbedding
const Graphm_cpGraph
 The associated graph. More...
 
face m_externalFace
 
int m_faceArrayTableSize
 The current table size of face arrays. More...
 
int m_faceIdCount
 The index assigned to the next created face. More...
 
std::mutex m_mutexRegArrays
 The critical section for protecting shared acces to register/unregister methods. More...
 
ListPure< FaceArrayBase * > m_regFaceArrays
 The external face. More...
 
AdjEntryArray< facem_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 409 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 425 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 435 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
adjThe adjacency entry belonging to the face that we want to insert the new edge into
vThe degree 0 node.
adjSrcwhether 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
eis the edge to be contracted.
keepSelfLoopsdetermines 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 452 of file CombinatorialEmbedding.h.

◆ getGraph() [2/2]

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

Returns the associated graph.

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

◆ joinFaces()

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

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

Parameters
eis 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 458 of file CombinatorialEmbedding.h.

◆ operator Graph &()

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

Definition at line 460 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
eis 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
adjSrcThe adjEntry after which the source adjEntry of the new edge should be inserted.
adjTgtThe adjEntry after which the target adjEntry of the new edge should be inserted.
sourceAfterOnly 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
adjStartLeftis the first entry that goes to the left node.
adjStartRightis 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
eInis the edge (v,u).
eOutis 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 411 of file CombinatorialEmbedding.h.

Member Data Documentation

◆ m_pGraph

Graph* ogdf::CombinatorialEmbedding::m_pGraph
private

The associated graph.

Definition at line 413 of file CombinatorialEmbedding.h.


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