Open
Graph Drawing
Framework

 v.2015.05
 

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)
 Contracts edge e. More...
 
edge splitFace (adjEntry adjSrc, adjEntry adjTgt)
 Splits a face by inserting a new edge. More...
 
edge splitFace (node v, adjEntry adjTgt)
 Splits a face by inserting a new edge. More...
 
edge splitFace (adjEntry adjSrc, node v)
 Splits a face by inserting a new edge. 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...
 
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 () 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...
 
bool consistencyCheck ()
 Checks the consistency of the data structure. 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...
 

Protected Member Functions

face joinFacesPure (edge e)
 Joins the two faces adjacent to e but does not remove edge e. More...
 
- Protected Member Functions inherited from ogdf::ConstCombinatorialEmbedding
face createFaceElement (adjEntry adjFirst)
 Create a new face. More...
 
void enterCSRegArrays () const
 Enter critical section for (un-)registering arrays. More...
 
void leaveCSRegArrays () const
 Leave critical section for (un-)registering arrays. More...
 
void reinitArrays ()
 Reinitialize associated face arrays. More...
 

Private Member Functions

 CombinatorialEmbedding (const CombinatorialEmbedding &)
 
CombinatorialEmbeddingoperator= (const CombinatorialEmbedding &)
 

Private Attributes

Graphm_pGraph
 The associated graph. More...
 

Friends

class GraphCopy
 

Additional Inherited Members

- Protected Attributes inherited from ogdf::ConstCombinatorialEmbedding
const Graphm_cpGraph
 The associated graph. More...
 
CriticalSection m_csRegArrays
 The critical section for protecting shared acces to register/unregister methods. 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...
 
GraphList< FaceElementm_faces
 The list of all faces. More...
 
int m_nFaces
 The number of faces. 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 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 328 of file CombinatorialEmbedding.h.

Constructor & Destructor Documentation

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( const CombinatorialEmbedding )
inlineprivate

Definition at line 337 of file CombinatorialEmbedding.h.

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( )
inline

Creates a combinatorial embedding associated with no graph.

Definition at line 346 of file CombinatorialEmbedding.h.

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

Member Function Documentation

void ogdf::CombinatorialEmbedding::clear ( )

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

node ogdf::CombinatorialEmbedding::contract ( edge  e)

Contracts edge e.

Parameters
eis an edge is the associated graph.
Returns
the node resulting from the contraction.
const Graph& ogdf::CombinatorialEmbedding::getGraph ( ) const
inline

Returns the associated graph.

Definition at line 369 of file CombinatorialEmbedding.h.

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

Definition at line 371 of file CombinatorialEmbedding.h.

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

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.
face ogdf::CombinatorialEmbedding::joinFacesPure ( edge  e)
protected

Joins the two faces adjacent to e but does not remove edge e.

Parameters
eis an edge in the associated graph.
Returns
the resulting (joined) face.
void ogdf::CombinatorialEmbedding::moveBridge ( adjEntry  adjBridge,
adjEntry  adjBefore 
)

Moves a bridge in the graph.

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

Definition at line 373 of file CombinatorialEmbedding.h.

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

Definition at line 375 of file CombinatorialEmbedding.h.

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

Definition at line 338 of file CombinatorialEmbedding.h.

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

Removes degree-1 node v.

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

Reverses edges e and updates embedding.

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'.
edge ogdf::CombinatorialEmbedding::splitFace ( adjEntry  adjSrc,
adjEntry  adjTgt 
)

Splits a face by inserting a new edge.

This operation introduces a new edge e from the node to which adjSrc belongs to the node to which adjTgt belongs.

Precondition
adjSrc and adjTgt belong to the same face.
Returns
the new edge e.
edge ogdf::CombinatorialEmbedding::splitFace ( node  v,
adjEntry  adjTgt 
)

Splits a face by inserting a new edge.

Special version of splitFace doing a pushback of the new edge on the adjacency list of v making it possible to insert new degree 0 nodes into a face.

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

Splits a face by inserting a new edge.

Special version of splitFace doing a pushback of the new edge on the adjacency list of v making it possible to insert new degree 0 nodes into a face.

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.
void ogdf::CombinatorialEmbedding::unsplit ( edge  eIn,
edge  eOut 
)

Undoes a split operation.

Parameters
eInis the edge (v,u).
eOutis the edge (u,w).
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

friend class GraphCopy
friend

Definition at line 330 of file CombinatorialEmbedding.h.

Member Data Documentation

Graph* ogdf::CombinatorialEmbedding::m_pGraph
private

The associated graph.

Definition at line 332 of file CombinatorialEmbedding.h.


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