OpenGraph DrawingFramework

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

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

Splits a node while preserving the order of adjacency entries. More...

node contract (edge e)
Contracts edge e. More...

Splits a face by inserting a new edge. More...

Splits a face by inserting a new edge. More...

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

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

Returns the face to the right of adj, i.e., the face containing adj. More...

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

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

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.

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
 e is 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
 e is 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
 e is an edge in the associated graph.
Returns
the resulting (joined) face.

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
 e is the edge to be split; e is modified by the split.
Returns
the edge e'.

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
Returns
the new edge e.

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.

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.

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