Open
Graph Drawing
Framework

 v.2010.10
 

Private Member Functions | Private Attributes

ogdf::CombinatorialEmbedding Class Reference

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

#include <ogdf/basic/CombinatorialEmbedding.h>

Inheritance diagram for ogdf::CombinatorialEmbedding:
ogdf::ConstCombinatorialEmbedding ogdf::DualGraph

List of all members.

Public Member Functions

 CombinatorialEmbedding ()
 Creates a combinatorial embedding associated with no graph.
 CombinatorialEmbedding (Graph &G)
 Creates a combinatorial embedding of graph G.
Access to the associated graph

const GraphgetGraph () const
 Returns the associated graph.
GraphgetGraph ()
 operator const Graph & () const
 Returns associated graph.
 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)
 Contracts edge e.
edge splitFace (adjEntry adjSrc, adjEntry adjTgt)
 Splits a face by inserting a new edge.
edge splitFace (node v, adjEntry adjTgt)
edge splitFace (adjEntry adjSrc, node v)
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)
void removeDeg1 (node v)
void updateMerger (edge e, face fRight, face fLeft)
 Update face information after inserting a merger in a copy graph.

Private Member Functions

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

Private Attributes

Graphm_pGraph
 The associated graph.

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.

Definition at line 303 of file CombinatorialEmbedding.h.


Constructor & Destructor Documentation

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( const CombinatorialEmbedding  )  [inline, private]

Definition at line 310 of file CombinatorialEmbedding.h.

ogdf::CombinatorialEmbedding::CombinatorialEmbedding (  )  [inline]

Creates a combinatorial embedding associated with no graph.

Definition at line 319 of file CombinatorialEmbedding.h.

ogdf::CombinatorialEmbedding::CombinatorialEmbedding ( Graph G  )  [inline, explicit]

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

Reimplemented from ogdf::ConstCombinatorialEmbedding.

Definition at line 342 of file CombinatorialEmbedding.h.

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

Definition at line 344 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 363 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.
void ogdf::CombinatorialEmbedding::moveBridge ( adjEntry  adjBridge,
adjEntry  adjBefore 
)
ogdf::CombinatorialEmbedding::operator const Graph & (  )  const [inline]

Returns associated graph.

Reimplemented from ogdf::ConstCombinatorialEmbedding.

Definition at line 346 of file CombinatorialEmbedding.h.

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

Definition at line 348 of file CombinatorialEmbedding.h.

CombinatorialEmbedding& ogdf::CombinatorialEmbedding::operator= ( const CombinatorialEmbedding  )  [inline, private]

Definition at line 311 of file CombinatorialEmbedding.h.

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


Member Data Documentation

The associated graph.

Definition at line 305 of file CombinatorialEmbedding.h.


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