ogdf::CombinatorialEmbedding Class Reference

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

#include <CombinatorialEmbedding.h>

Inheritance diagram for ogdf::CombinatorialEmbedding:

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 Graph & getGraph () const

Returns the associated graph.

Graph & getGraph ()

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

CombinatorialEmbedding & operator= (const CombinatorialEmbedding &)

Private Attributes

Graph * m_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 295 of file CombinatorialEmbedding.h.

Constructor & Destructor Documentation

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

Definition at line 302 of file CombinatorialEmbedding.h.

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

Creates a combinatorial embedding associated with no graph.

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

Member Function Documentation

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

Definition at line 303 of file CombinatorialEmbedding.h.

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

Returns the associated graph.

Reimplemented from ogdf::ConstCombinatorialEmbedding.

Definition at line 334 of file CombinatorialEmbedding.h.

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

Definition at line 336 of file CombinatorialEmbedding.h.

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

Returns associated graph.

Reimplemented from ogdf::ConstCombinatorialEmbedding.

Definition at line 338 of file CombinatorialEmbedding.h.

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

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

void ogdf::CombinatorialEmbedding::clear ( )

Removes all nodes, edges, and faces from the graph and the 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:

is the edge to be split; e is modified by the split.

Returns:: the edge e'.

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

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.

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

Contracts edge e.

Parameters:

is an edge is the associated graph.

Returns:: the node resulting from the contraction.

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
	)

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

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

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

Parameters:

is an edge in the associated graph.

Returns:: the resulting (joined) face.

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

Reverses edges e and updates embedding.

void ogdf::CombinatorialEmbedding::moveBridge	(	adjEntry	adjBridge,
		adjEntry	adjBefore
	)

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

void ogdf::CombinatorialEmbedding::updateMerger	(	edge	e,
		face	fRight,
		face	fLeft
	)

Update face information after inserting a merger in a copy graph.

Member Data Documentation

Graph* ogdf::CombinatorialEmbedding::m_pGraph [private]

The associated graph.

Definition at line 297 of file CombinatorialEmbedding.h.

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

ogdf/basic/CombinatorialEmbedding.h

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:07 2007 by doxygen 1.5.4.


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 Graph &	getGraph () const
	Returns the associated graph.
Graph &	getGraph ()
	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 &)
CombinatorialEmbedding &	operator= (const CombinatorialEmbedding &)
Private Attributes
Graph *	m_pGraph
	The associated graph.

OpenGraph DrawingFramework

ogdf::CombinatorialEmbedding Class Reference

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework