Planarized representations (of a connected component) of a graph. More...

#include <ogdf/planarity/PlanRepExpansion.h>

Inheritance diagram for ogdf::PlanRepExpansion:

Classes
struct	Crossing
class	NodeSplit
	Representation of a node split in a planarized expansion. More...
Public Types
typedef PlanRepExpansion::NodeSplit *	nodeSplit
	Pointer to a node split.
Public Member Functions
	PlanRepExpansion (const Graph &G)
	Creates a planarized expansion of graph G.
	PlanRepExpansion (const Graph &G, const List< node > &splittableNodes)
	Creates a planarized expansion of graph G with given splittable nodes.
	~PlanRepExpansion ()
Acess methods

const Graph &	original () const
	Returns a reference to the original graph.
node	original (node v) const
	Returns the original node of v, or 0 if v is a dummy.
const List< node > &	expansion (node vOrig) const
	Returns the list of copy nodes of vOrig.
node	copy (node vOrig) const
	Returns the first copy node of vOrig.
edge	originalEdge (edge e) const
	Returns the original edge of \ e, or 0 if e has none (e.g., e belongs to a node split).
const List< edge > &	chain (edge eOrig) const
	Returns the insertion path of edge eOrig.
edge	copy (edge eOrig) const
	Returns the first edge in eOrig's insertion path.
bool	splittable (node v) const
	Returns true iff v is splittable.
bool	splittableOrig (node vOrig) const
	Returns true iff vOrig is splittable.
NodeSplit *	nodeSplitOf (edge e) const
	Returns the node split associated with e, or 0 if none (e.g., e belongs to an original edge).
int	numberOfNodeSplits () const
	Returns the number of node splits.
int	numberOfSplittedNodes () const
List< NodeSplit > &	nodeSplits ()
	Returns the list of node splits.
List< edge > &	setOrigs (edge e, edge &eOrig, nodeSplit &ns)
	Sets the original edge and corresponding node split of e and returns the corresponding insertion path.
ListConstIterator< edge >	position (edge e) const
bool	isPseudoCrossing (node v) const
int	computeNumberOfCrossings () const
	Computes the number of crossings.
Processing connected components

int	numberOfCCs () const
	Returns the number of connected components in the original graph.
int	currentCC () const
	Returns the index of the current connected component (-1 if not yet initialized).
const List< node > &	nodesInCC (int i) const
	Returns the list of (original) nodes in connected component i.
const List< node > &	nodesInCC () const
	Returns the list of (original) nodes in the current connected component.
void	initCC (int i)
	Initializes the planarized representation for connected component i.
Update operations

edge	split (edge e)
	Splits edge e into two edges introducing a new node.
void	unsplit (edge eIn, edge eOut)
	Undoes a split operation.
void	delCopy (edge e)
	Removes edge e from the planarized expansion.
bool	embed ()
	Embeds the planarized expansion; returns true iff it is planar.
void	insertEdgePath (edge eOrig, nodeSplit ns, node vStart, node vEnd, List< Crossing > &eip, edge eSrc, edge eTgt)
void	insertEdgePathEmbedded (edge eOrig, nodeSplit ns, CombinatorialEmbedding &E, const List< Tuple2< adjEntry, adjEntry > > &crossedEdges)
	Inserts an edge or a node split according to insertion path crossedEdges.
void	removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, nodeSplit ns, FaceSetPure &newFaces, NodeSetPure &mergedNodes, node &oldSrc, node &oldTgt)
	Removes the insertion path of eOrig or ns.
void	removeEdgePath (edge eOrig, nodeSplit ns, node &oldSrc, node &oldTgt)
	Removes the insertion path of eOrig or ns.
void	contractSplit (nodeSplit ns, CombinatorialEmbedding &E)
	Removes an (unneccessary) node split consisting of a single edge.
void	contractSplit (nodeSplit ns)
	Removes an (unneccessary) node split consisting of a single edge.
edge	unsplitExpandNode (node u, edge eContract, edge eExpand, CombinatorialEmbedding &E)
	Unsplits a superfluous expansion node of degree 2.
edge	unsplitExpandNode (node u, edge eContract, edge eExpand)
	Unsplits a superfluous expansion node of degree 2.
edge	enlargeSplit (node v, edge e, CombinatorialEmbedding &E)
	Splits edge e and introduces a new node split starting at v.
edge	enlargeSplit (node v, edge e)
	Splits edge e and introduces a new node split starting at v.
edge	splitNodeSplit (edge e, CombinatorialEmbedding &E)
	Introduces a new node split by splitting an exisiting node split.
edge	splitNodeSplit (edge e)
	Introduces a new node split by splitting an exisiting node split.
void	removeSelfLoop (edge e, CombinatorialEmbedding &E)
	Removes a self-loop e = (u,u).
void	removeSelfLoop (edge e)
PlanRepExpansion::nodeSplit	convertDummy (node u, node vOrig, PlanRepExpansion::nodeSplit ns)
	Converts a dummy node u to a copy of an original node vOrig.
edge	separateDummy (adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc)
void	resolvePseudoCrossing (node v)
Miscelleaneous

bool	consistencyCheck () const
	Performs various consistency checks on the data structure.
Private Member Functions
void	doInit (const Graph &G, const List< node > &splittableNodes)
void	prepareNodeSplit (const SList< adjEntry > &partitionLeft, adjEntry &adjLeft, adjEntry &adjRight)
Private Attributes
const Graph *	m_pGraph
	The original graph.
NodeArray< node >	m_vOrig
	The corresponding node in the original graph.
EdgeArray< edge >	m_eOrig
	The corresponding edge in the original graph.
EdgeArray< ListIterator< edge > >	m_eIterator
	The position of copy edge in the list.
EdgeArray< List< edge > >	m_eCopy
	The corresponding list of edges in the graph copy.
NodeArray< ListIterator< node > >	m_vIterator
	The position of copy node in the list.
NodeArray< List< node > >	m_vCopy
	The corresponding list of nodes in the graph copy.
NodeArray< bool >	m_splittable
NodeArray< bool >	m_splittableOrig
EdgeArray< NodeSplit * >	m_eNodeSplit
List< NodeSplit >	m_nodeSplits
int	m_currentCC
	The index of the current component.
int	m_numCC
	The number of components in the original graph.
Array< List< node > >	m_nodesInCC
	The list of original nodes in each component.
EdgeArray< edge >	m_eAuxCopy

Detailed Description

Planarized representations (of a connected component) of a graph.

Maintains types of edges (generalization, association) and nodes, and the connected components of the graph.

Definition at line 81 of file PlanRepExpansion.h.

Member Typedef Documentation

typedef PlanRepExpansion::NodeSplit* ogdf::PlanRepExpansion::nodeSplit

Pointer to a node split.

Definition at line 133 of file PlanRepExpansion.h.

Constructor & Destructor Documentation

ogdf::PlanRepExpansion::PlanRepExpansion ( const Graph & G )

Creates a planarized expansion of graph G.

All nodes are allowed to be split.

ogdf::PlanRepExpansion::PlanRepExpansion	(	const Graph &	G,
		const List< node > &	splittableNodes
	)

Creates a planarized expansion of graph G with given splittable nodes.

Only the node in splittableNodes are allowed to be split.

Parameters:

	G	is the original graph of this planarized expansion.
	splittableNodes	contains all the nodes in G that are splittable.

ogdf::PlanRepExpansion::~PlanRepExpansion ( ) [inline]

Definition at line 152 of file PlanRepExpansion.h.

Member Function Documentation

const List<edge>& ogdf::PlanRepExpansion::chain ( edge eOrig ) const [inline]

Returns the insertion path of edge eOrig.

Definition at line 176 of file PlanRepExpansion.h.

int ogdf::PlanRepExpansion::computeNumberOfCrossings ( ) const

Computes the number of crossings.

bool ogdf::PlanRepExpansion::consistencyCheck ( ) const

Performs various consistency checks on the data structure.

Reimplemented from ogdf::Graph.

void ogdf::PlanRepExpansion::contractSplit ( nodeSplit ns )

Removes an (unneccessary) node split consisting of a single edge.

Nodes splits consisting of a single edge are superfluous and canbe removed by contracting the respective edge.

Parameters:

ns

is the node split to be removed.

void ogdf::PlanRepExpansion::contractSplit	(	nodeSplit	ns,
		CombinatorialEmbedding &	E
	)

Removes an (unneccessary) node split consisting of a single edge.

Nodes splits consisting of a single edge are superfluous and canbe removed by contracting the respective edge.

Parameters:

	ns	is the node split to be removed.
	E	is an embedding of the planarized expansion.

PlanRepExpansion::nodeSplit ogdf::PlanRepExpansion::convertDummy	(	node	u,
		node	vOrig,
		PlanRepExpansion::nodeSplit	ns
	)

Converts a dummy node u to a copy of an original node vOrig.

This method is used if two copy nodes x and y of the same original node vOrig can be connected by converting a dummy node u into a copy node of vOrig, since an insertion path starting (or ending) at x crosses an insertion path starting (or ending) at y.

Parameters:

	u	is a dummy node in the planarized expansion.
	vOrig	is an original node.
	ns	is a node split that can be reused for connecting x with u.

node ogdf::PlanRepExpansion::copy ( node vOrig ) const [inline]

Returns the first copy node of vOrig.

Definition at line 170 of file PlanRepExpansion.h.

edge ogdf::PlanRepExpansion::copy ( edge eOrig ) const [inline]

Returns the first edge in eOrig's insertion path.

Definition at line 179 of file PlanRepExpansion.h.

int ogdf::PlanRepExpansion::currentCC ( ) const [inline]

Returns the index of the current connected component (-1 if not yet initialized).

Definition at line 232 of file PlanRepExpansion.h.

void ogdf::PlanRepExpansion::delCopy ( edge e )

Removes edge e from the planarized expansion.

void ogdf::PlanRepExpansion::doInit	(	const Graph &	G,
		const List< node > &	splittableNodes
	)			`[private]`

bool ogdf::PlanRepExpansion::embed ( )

Embeds the planarized expansion; returns true iff it is planar.

edge ogdf::PlanRepExpansion::enlargeSplit	(	node	v,
		edge	e,
		CombinatorialEmbedding &	E
	)

Splits edge e and introduces a new node split starting at v.

Parameters:

	v	is a node in the planarized expansion; the expansion of v's original node is enlarged.
	e	is the edge to be split; the insertion path of e's original edge must start or end at v.
	E	is an embedding of the planarized expansion.

Returns:: the newly created edge; the node resulting from splitting e is the target node of this edge.

edge ogdf::PlanRepExpansion::enlargeSplit	(	node	v,
		edge	e
	)

Splits edge e and introduces a new node split starting at v.

Parameters:

	v	is a node in the planarized expansion; the expansion of v's original node is enlarged.
	e	is the edge to be split; the insertion path of e's original edge must start or end at v.

Returns:: the newly created edge; the node resulting from splitting e is the target node of this edge.

const List<node>& ogdf::PlanRepExpansion::expansion ( node vOrig ) const [inline]

Returns the list of copy nodes of vOrig.

Definition at line 167 of file PlanRepExpansion.h.

void ogdf::PlanRepExpansion::initCC ( int i )

Initializes the planarized representation for connected component i.

This initialization is always required. After performing this initialization, the planarized representation represents a copy of the i-th connected component of the original graph, where connected components are numbered 0,1,2,...

void ogdf::PlanRepExpansion::insertEdgePath	(	edge	eOrig,
		nodeSplit	ns,
		node	vStart,
		node	vEnd,
		List< Crossing > &	eip,
		edge	eSrc,
		edge	eTgt
	)

void ogdf::PlanRepExpansion::insertEdgePathEmbedded	(	edge	eOrig,
		nodeSplit	ns,
		CombinatorialEmbedding &	E,
		const List< Tuple2< adjEntry, adjEntry > > &	crossedEdges
	)

Inserts an edge or a node split according to insertion path crossedEdges.

If eOrig is not 0, a new insertion path for eOrig is inserted; otherwise, a new insertion path for node split ns is inserted.

Parameters:

	eOrig	is an original edge in the graph (or 0).
	ns	is a node split in the planarized expansion.
	E	is an embedding of the planarized expansion.
	crossedEdges	defines the insertion path.

Precondition:: Not both eOrig and ns may be 0.

See also:: GraphCopy::insertEdgePathEmbedded() for a specification of crossedEdges.

bool ogdf::PlanRepExpansion::isPseudoCrossing ( node v ) const

const List<node>& ogdf::PlanRepExpansion::nodesInCC ( ) const [inline]

Returns the list of (original) nodes in the current connected component.

Definition at line 248 of file PlanRepExpansion.h.

const List<node>& ogdf::PlanRepExpansion::nodesInCC ( int i ) const [inline]

Returns the list of (original) nodes in connected component i.

Note that connected components are numbered 0,1,...

Definition at line 241 of file PlanRepExpansion.h.

NodeSplit* ogdf::PlanRepExpansion::nodeSplitOf ( edge e ) const [inline]

Returns the node split associated with e, or 0 if none (e.g., e belongs to an original edge).

Definition at line 188 of file PlanRepExpansion.h.

List<NodeSplit>& ogdf::PlanRepExpansion::nodeSplits ( ) [inline]

Returns the list of node splits.

Definition at line 195 of file PlanRepExpansion.h.

int ogdf::PlanRepExpansion::numberOfCCs ( ) const [inline]

Returns the number of connected components in the original graph.

Definition at line 225 of file PlanRepExpansion.h.

int ogdf::PlanRepExpansion::numberOfNodeSplits ( ) const [inline]

Returns the number of node splits.

Definition at line 191 of file PlanRepExpansion.h.

int ogdf::PlanRepExpansion::numberOfSplittedNodes ( ) const

node ogdf::PlanRepExpansion::original ( node v ) const [inline]

Returns the original node of v, or 0 if v is a dummy.

Definition at line 164 of file PlanRepExpansion.h.

const Graph& ogdf::PlanRepExpansion::original ( ) const [inline]

Returns a reference to the original graph.

Definition at line 161 of file PlanRepExpansion.h.

edge ogdf::PlanRepExpansion::originalEdge ( edge e ) const [inline]

Returns the original edge of \ e, or 0 if e has none (e.g., e belongs to a node split).

Definition at line 173 of file PlanRepExpansion.h.

ListConstIterator<edge> ogdf::PlanRepExpansion::position ( edge e ) const [inline]

Definition at line 208 of file PlanRepExpansion.h.

void ogdf::PlanRepExpansion::prepareNodeSplit	(	const SList< adjEntry > &	partitionLeft,
		adjEntry &	adjLeft,
		adjEntry &	adjRight
	)			`[private]`

void ogdf::PlanRepExpansion::removeEdgePath	(	edge	eOrig,
		nodeSplit	ns,
		node &	oldSrc,
		node &	oldTgt
	)

Removes the insertion path of eOrig or ns.

Parameters:

	eOrig	is an original edge in the graph (or 0).
	ns	is a node split in the planarized expansion.
	oldSrc	is assigned the source node of the removed insertion path.
	oldTgt	is assigned the target node of the removed insertion path.

Precondition:: Not both eOrig and ns may be 0.

void ogdf::PlanRepExpansion::removeEdgePathEmbedded	(	CombinatorialEmbedding &	E,
		edge	eOrig,
		nodeSplit	ns,
		FaceSetPure &	newFaces,
		NodeSetPure &	mergedNodes,
		node &	oldSrc,
		node &	oldTgt
	)

Removes the insertion path of eOrig or ns.

Parameters:

	E	is an embedding of the planarized expansion.
	eOrig	is an original edge in the graph (or 0).
	ns	is a node split in the planarized expansion.
	newFaces	is assigned the set of new faces resulting from joining faces when removing edges.
	mergedNodes	is assigned the set of nodes in the planarized expansion that resulted from merging (splittable) nodes.
	oldSrc	is assigned the source node of the removed insertion path.
	oldTgt	is assigned the target node of the removed insertion path.

Precondition:: Not both eOrig and ns may be 0.

void ogdf::PlanRepExpansion::removeSelfLoop	(	edge	e,
		CombinatorialEmbedding &	E
	)

Removes a self-loop e = (u,u).

u must be a dummy node; hence, u has degree 2 node after removing \ e, and u is unsplit afterwards.

Parameters:

	e	must be a self loop in the planarized expansion.
	E	is an embedding of the planarized expansion.

void ogdf::PlanRepExpansion::removeSelfLoop ( edge e )

void ogdf::PlanRepExpansion::resolvePseudoCrossing ( node v )

edge ogdf::PlanRepExpansion::separateDummy	(	adjEntry	adj_1,
		adjEntry	adj_2,
		node	vStraight,
		bool	isSrc
	)

List<edge>& ogdf::PlanRepExpansion::setOrigs	(	edge	e,
		edge &	eOrig,
		nodeSplit &	ns
	)

Sets the original edge and corresponding node split of e and returns the corresponding insertion path.

Parameters:

	e	is an edge in the planarized expansion.
	eOrig	is assigned the original edge of e (or 0 if none).
	ns	is assigned the node split corresponding to e (or 0 if none).

Returns:: a reference to the insertion path containing e; this is either the insertion path of eOrig (if this is not 0), or of ns.

edge ogdf::PlanRepExpansion::split ( edge e ) [virtual]

Splits edge e into two edges introducing a new node.

Let e=(v,w). Then, the resulting two edges are e=(v,u) and e'=(u,w), where u is a new node.

Returns:: The edge e'.

Note:: The edge e is modified by this operation.

Reimplemented from ogdf::Graph.

edge ogdf::PlanRepExpansion::splitNodeSplit ( edge e )

Introduces a new node split by splitting an exisiting node split.

Parameters:

e

is the edge to be split; the node split corresponding to e is split into two node splits.

Returns:: the newly created edge; the node resulting from splitting e is the target node of this edge.

edge ogdf::PlanRepExpansion::splitNodeSplit	(	edge	e,
		CombinatorialEmbedding &	E
	)

Introduces a new node split by splitting an exisiting node split.

Parameters:

	e	is the edge to be split; the node split corresponding to e is split into two node splits.
	E	is an embedding of the planarized expansion.

Returns:: the newly created edge; the node resulting from splitting e is the target node of this edge.

bool ogdf::PlanRepExpansion::splittable ( node v ) const [inline]

Returns true iff v is splittable.

Definition at line 182 of file PlanRepExpansion.h.

bool ogdf::PlanRepExpansion::splittableOrig ( node vOrig ) const [inline]

Returns true iff vOrig is splittable.

Definition at line 185 of file PlanRepExpansion.h.

void ogdf::PlanRepExpansion::unsplit	(	edge	eIn,
		edge	eOut
	)			`[virtual]`

Undoes a split operation.

For two edges eIn = (x,u) and eOut = (u,y), removes node u by joining eIn and eOut. Edge eOut is removed and eIn is reused.

Precondition:: eIn and eOut are the only edges incident with u and none of them is a self-loop.

Reimplemented from ogdf::Graph.

edge ogdf::PlanRepExpansion::unsplitExpandNode	(	node	u,
		edge	eContract,
		edge	eExpand
	)

Unsplits a superfluous expansion node of degree 2.

Parameters:

	u	is a node in the planarized expansion which has degree 2 and is part of the expansion of an original node.
	eContract	is the edge incident to u which is part of a node split; this edge gets contracted.
	eExpand	is the edge incident to u which belongs to the insertion path that gets enlarged.

edge ogdf::PlanRepExpansion::unsplitExpandNode	(	node	u,
		edge	eContract,
		edge	eExpand,
		CombinatorialEmbedding &	E
	)

Unsplits a superfluous expansion node of degree 2.

Parameters:

	u	is a node in the planarized expansion which has degree 2 and is part of the expansion of an original node.
	eContract	is the edge incident to u which is part of a node split; this edge gets contracted.
	eExpand	is the edge incident to u which belongs to the insertion path that gets enlarged.
	E	is an embedding of the planarized expansion.