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
using	nodeSplit = PlanRepExpansion::NodeSplit *
	Pointer to a node split. More...

Public Types inherited from ogdf::Graph
enum	EdgeType { EdgeType::association = 0, EdgeType::generalization = 1, EdgeType::dependency = 2 }
	The type of edges (only used in derived classes). More...

enum	NodeType { NodeType::vertex = 0, NodeType::dummy = 1, NodeType::generalizationMerger = 2, NodeType::generalizationExpander = 3, NodeType::highDegreeExpander = 4, NodeType::lowDegreeExpander = 5, NodeType::associationClass = 6 }
	The type of nodes. More...

using	node_iterator = internal::GraphIterator< node >
	Provides a bidirectional iterator to a node in a graph. More...

using	edge_iterator = internal::GraphIterator< edge >
	Provides a bidirectional iterator to an edge in a graph. More...

using	adjEntry_iterator = internal::GraphIterator< adjEntry >
	Provides a bidirectional iterator to an entry in an adjacency list. More...

Public Member Functions
	PlanRepExpansion (const Graph &G)
	Creates a planarized expansion of graph `G`. More...

	PlanRepExpansion (const Graph &G, const List< node > &splittableNodes)
	Creates a planarized expansion of graph `G` with given splittable nodes. More...

	~PlanRepExpansion ()

Acess methods
const Graph &	original () const
	Returns a reference to the original graph. More...

node	original (node v) const
	Returns the original node of `v`, or 0 if `v` is a dummy. More...

const List< node > &	expansion (node vOrig) const
	Returns the list of copy nodes of `vOrig`. More...

node	copy (node vOrig) const
	Returns the first copy node of `vOrig`. More...

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

const List< edge > &	chain (edge eOrig) const
	Returns the insertion path of edge `eOrig`. More...

edge	copy (edge eOrig) const
	Returns the first edge in `eOrig's` insertion path. More...

bool	splittable (node v) const
	Returns true iff `v` is splittable. More...

bool	splittableOrig (node vOrig) const
	Returns true iff `vOrig` is splittable. More...

NodeSplit *	nodeSplitOf (edge e) const
	Returns the node split associated with `e`, or 0 if none (e.g., `e` belongs to an original edge). More...

int	numberOfNodeSplits () const
	Returns the number of node splits. More...

int	numberOfSplittedNodes () const

List< NodeSplit > &	nodeSplits ()
	Returns the list of node splits. More...

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

ListConstIterator< edge >	position (edge e) const

bool	isPseudoCrossing (node v) const

int	computeNumberOfCrossings () const
	Computes the number of crossings. More...

Processing connected components
int	numberOfCCs () const
	Returns the number of connected components in the original graph. More...

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

const List< node > &	nodesInCC (int i) const
	Returns the list of (original) nodes in connected component `i`. More...

const List< node > &	nodesInCC () const
	Returns the list of (original) nodes in the current connected component. More...

void	initCC (int i)
	Initializes the planarized representation for connected component `i`. More...

Update operations
edge	split (edge e) override
	Splits edge `e` into two edges introducing a new node. More...

void	unsplit (edge eIn, edge eOut) override
	Undoes a split operation. More...

virtual void	delEdge (edge e) override
	Removes edge `e` from the planarized expansion. More...

bool	embed ()
	Embeds the planarized expansion; returns true iff it is planar. More...

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

void	removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, nodeSplit ns, FaceSet< false > &newFaces, NodeSet< false > &mergedNodes, node &oldSrc, node &oldTgt)
	Removes the insertion path of `eOrig` or `ns`. More...

void	removeEdgePath (edge eOrig, nodeSplit ns, node &oldSrc, node &oldTgt)
	Removes the insertion path of `eOrig` or `ns`. More...

void	contractSplit (nodeSplit ns, CombinatorialEmbedding &E)
	Removes an (unneccessary) node split consisting of a single edge. More...

void	contractSplit (nodeSplit ns)
	Removes an (unneccessary) node split consisting of a single edge. More...

edge	unsplitExpandNode (node u, edge eContract, edge eExpand, CombinatorialEmbedding &E)
	Unsplits a superfluous expansion node of degree 2. More...

edge	unsplitExpandNode (node u, edge eContract, edge eExpand)
	Unsplits a superfluous expansion node of degree 2. More...

edge	enlargeSplit (node v, edge e, CombinatorialEmbedding &E)
	Splits edge `e` and introduces a new node split starting at `v`. More...

edge	enlargeSplit (node v, edge e)
	Splits edge `e` and introduces a new node split starting at `v`. More...

edge	splitNodeSplit (edge e, CombinatorialEmbedding &E)
	Introduces a new node split by splitting an exisiting node split. More...

edge	splitNodeSplit (edge e)
	Introduces a new node split by splitting an exisiting node split. More...

void	removeSelfLoop (edge e, CombinatorialEmbedding &E)
	Removes a self-loop `e` = (u,u). More...

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

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

void	resolvePseudoCrossing (node v)

Miscelleaneous
void	consistencyCheck () const

Public Member Functions inherited from ogdf::Graph
	Graph ()
	Constructs an empty graph. More...

	Graph (const Graph &copy)
	Constructs a graph that is a copy of `G`. More...

	Graph (Graph &&move)=delete

virtual	~Graph ()
	Destructor. More...

Graph &	operator= (const Graph &copy)
	Overwrites this graph to be a copy of `G`. More...

Graph &	operator= (Graph &&move)=delete

bool	empty () const
	Returns true iff the graph is empty, i.e., contains no nodes. More...

int	numberOfNodes () const
	Returns the number of nodes in the graph. More...

int	numberOfEdges () const
	Returns the number of edges in the graph. More...

int	maxNodeIndex () const
	Returns the largest used node index. More...

int	maxEdgeIndex () const
	Returns the largest used edge index. More...

int	maxAdjEntryIndex () const
	Returns the largest used adjEntry index. More...

node	firstNode () const
	Returns the first node in the list of all nodes. More...

node	lastNode () const
	Returns the last node in the list of all nodes. More...

edge	firstEdge () const
	Returns the first edge in the list of all edges. More...

edge	lastEdge () const
	Returns the last edge in the list of all edges. More...

node	chooseNode (std::function< bool(node)> includeNode=[](node) { return true;}, bool isFastTest=true) const
	Returns a random node. More...

edge	chooseEdge (std::function< bool(edge)> includeEdge=[](edge) { return true;}, bool isFastTest=true) const
	Returns a random edge. More...

template<class CONTAINER >
void	allNodes (CONTAINER &nodeContainer) const
	Returns a container with all nodes of the graph. More...

template<class CONTAINER >
void	allEdges (CONTAINER &edgeContainer) const
	Returns a container with all edges of the graph. More...

node	newNode (int index=-1)
	Creates a new node and returns it. More...

edge	newEdge (node v, node w, int index=-1)
	Creates a new edge (`v`,`w`) and returns it. More...

edge	newEdge (node v, adjEntry adjTgt, int index=-1)
	Creates a new edge at predefined positions in the adjacency lists. More...

edge	newEdge (adjEntry adjSrc, node w, int index=-1)
	Creates a new edge at predefined positions in the adjacency lists. More...

edge	newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=Direction::after, int index=-1)
	Creates a new edge at predefined positions in the adjacency lists. More...

template<typename S , typename T >
edge	newEdge (S src, Direction dirSrc, T tgt, Direction dirTgt, int index=-1)
	Creates a new edge at predefined positions in the adjacency lists. More...

virtual void	delNode (node v)
	Removes node `v` and all incident edges from the graph. More...

virtual void	clear ()
	Removes all nodes and all edges from the graph. More...

void	restoreAllEdges ()
	Restore all hidden edges and invalidate all HiddenEdgeSets. More...

void	unsplit (node u)
	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, bool keepSelfLoops=false)
	Contracts edge `e` while preserving the order of adjacency entries. More...

void	move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt)
	Moves edge `e` to a different adjacency list. More...

void	moveTarget (edge e, node w)
	Moves the target node of edge `e` to node `w`. More...

void	moveTarget (edge e, adjEntry adjTgt, Direction dir)
	Moves the target node of edge `e` to a specific position in an adjacency list. More...

void	moveSource (edge e, node w)
	Moves the source node of edge `e` to node `w`. More...

void	moveSource (edge e, adjEntry adjSrc, Direction dir)
	Moves the source node of edge `e` to a specific position in an adjacency list. More...

edge	searchEdge (node v, node w, bool directed=false) const
	Searches and returns an edge connecting nodes `v` and `w` in time O( min(deg(`v` ), deg(`w` ))). More...

void	reverseEdge (edge e)
	Reverses the edge `e`, i.e., exchanges source and target node. More...

void	reverseAllEdges ()
	Reverses all edges in the graph. More...

template<class NODELIST >
void	collapse (NODELIST &nodesToCollapse)
	Collapses all nodes in the list `nodesToCollapse` to the first node in the list. More...

template<class ADJ_ENTRY_LIST >
void	sort (node v, const ADJ_ENTRY_LIST &newOrder)
	Sorts the adjacency list of node `v` according to `newOrder`. More...

template<class IT >
void	sort (node v, IT begin, IT end)
	Sorts the adjacency list of node `v` according to the range denoted by two iterators. More...

void	reverseAdjEdges (node v)
	Reverses the adjacency list of `v`. More...

void	moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos)
	Moves adjacency entry `adjMove` before or after `adjPos`. More...

void	moveAdjAfter (adjEntry adjMove, adjEntry adjAfter)
	Moves adjacency entry `adjMove` after `adjAfter`. More...

void	moveAdjBefore (adjEntry adjMove, adjEntry adjBefore)
	Moves adjacency entry `adjMove` before `adjBefore`. More...

void	reverseAdjEdges ()
	Reverses all adjacency lists. More...

void	swapAdjEdges (adjEntry adj1, adjEntry adj2)
	Exchanges two entries in an adjacency list. More...

int	genus () const
	Returns the genus of the graph's embedding. More...

bool	representsCombEmbedding () const
	Returns true iff the graph represents a combinatorial embedding. More...

void	consistencyCheck () const
	Asserts that this graph is consistent. More...

internal::GraphNodeRegistry &	nodeRegistry ()
	Returns a reference to the registry of node arrays associated with this graph. More...

const internal::GraphNodeRegistry &	nodeRegistry () const
	Returns a const reference to the registry of node arrays associated with this graph. More...

	operator const internal::GraphNodeRegistry & () const

internal::GraphEdgeRegistry &	edgeRegistry ()
	Returns a reference to the registry of edge arrays associated with this graph. More...

const internal::GraphEdgeRegistry &	edgeRegistry () const
	Returns a const reference to the registry of edge arrays associated with this graph. More...

	operator const internal::GraphEdgeRegistry & () const

internal::GraphAdjRegistry &	adjEntryRegistry ()
	Returns a reference to the registry of adjEntry arrays associated with this graph. More...

const internal::GraphAdjRegistry &	adjEntryRegistry () const
	Returns a const reference to the registry of adjEntry arrays associated with this graph. More...

	operator const internal::GraphAdjRegistry & () const

void	resetEdgeIdCount (int maxId)
	Resets the edge id count to `maxId`. More...

void	resetNodeIdCount (int maxId)

template<OGDF_NODE_ITER NI, OGDF_EDGE_ITER EI, bool copyEmbedding = true, bool copyIDs = false, bool notifyObservers = true>
std::pair< int, int >	insert (const NI &nodesBegin, const NI &nodesEnd, const EI &edgesBegin, const EI &edgesEnd, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given subgraph into this graph. More...

template<OGDF_NODE_ITER NI, OGDF_EDGE_FILTER EF, bool copyIDs = false, bool notifyObservers = true>
std::pair< int, int >	insert (const NI &nodesBegin, const NI &nodesEnd, const EF &edgeFilter, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given subgraph into this graph. More...

template<OGDF_NODE_LIST NL>
std::pair< int, int >	insert (const NL &nodeList, const EdgeSet< true > &edgeSet, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given subgraph into this graph. More...

template<OGDF_NODE_LIST NL>
std::pair< int, int >	insert (const NL &nodeList, const EdgeSet< false > &edgeSet, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given subgraph into this graph. More...

template<OGDF_NODE_LIST NL, OGDF_EDGE_LIST EL>
std::pair< int, int >	insert (const NL &nodeList, const EL &edgeList, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given subgraph into this graph. More...

std::pair< int, int >	insert (const CCsInfo &info, int cc, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given connected component `cc` into this graph. More...

std::pair< int, int >	insert (const Graph &G, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap)
	Inserts a copy of a given Graph `G` into this graph. More...

std::pair< int, int >	insert (const Graph &G)
	Inserts a copy of a given Graph `G` into this graph. More...

Public Member Functions inherited from ogdf::Observable< GraphObserver, Graph >
	Observable ()=default

	Observable (const Observable &copy)=delete
	If you want to copy a subclass of Observable, call the default Observable() constructor. More...

	Observable (Observable &&move)=delete
	If you want to move a subclass of Observable, call the default Observable() constructor. More...

virtual	~Observable ()

Observable &	operator= (const Observable &copy)=delete

Observable &	operator= (Observable &&move)=delete

Private Member Functions
void	doInit (const Graph &G, const List< node > &splittableNodes)

void	prepareNodeSplit (const SList< adjEntry > &partitionLeft, adjEntry &adjLeft, adjEntry &adjRight)

Private Attributes
int	m_currentCC
	The index of the current component. More...

EdgeArray< edge >	m_eAuxCopy

EdgeArray< List< edge > >	m_eCopy
	The corresponding list of edges in the graph copy. More...

EdgeArray< ListIterator< edge > >	m_eIterator
	The position of copy edge in the list. More...

EdgeArray< NodeSplit * >	m_eNodeSplit

EdgeArray< edge >	m_eOrig
	The corresponding edge in the original graph. More...

Array< List< node > >	m_nodesInCC
	The list of original nodes in each component. More...

List< NodeSplit >	m_nodeSplits

int	m_numCC
	The number of components in the original graph. More...

const Graph *	m_pGraph
	The original graph. More...

NodeArray< bool >	m_splittable

NodeArray< bool >	m_splittableOrig

NodeArray< List< node > >	m_vCopy
	The corresponding list of nodes in the graph copy. More...

NodeArray< ListIterator< node > >	m_vIterator
	The position of copy node in the list. More...

NodeArray< node >	m_vOrig
	The corresponding node in the original graph. More...

Additional Inherited Members
Public Attributes inherited from ogdf::Graph
internal::GraphObjectContainer< NodeElement >	nodes
	The container containing all node objects. More...

internal::GraphObjectContainer< EdgeElement >	edges
	The container containing all edge objects. More...

Protected Member Functions inherited from ogdf::Graph
virtual void *	preInsert (bool copyEmbedding, bool copyIDs, bool notifyObservers, bool edgeFilter, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap, int newNodes, int newEdges)
	Callback notifying subclasses that some graph is about to be insert() -ed. More...

virtual void	nodeInserted (void *userData, node original, node copy)
	Callback notifying subclasses that insert() copied a node. More...

virtual void	edgeInserted (void *userData, edge original, edge copy)
	Callback notifying subclasses that insert() copied an edge. More...

virtual void	postInsert (void *userData, int newNodes, int newEdges)
	Callback notifying subclasses that an insert() call has finished. More...

Protected Member Functions inherited from ogdf::Observable< GraphObserver, Graph >
void	clearObservers ()

const ListPure< GraphObserver * > &	getObservers () const

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 58 of file PlanRepExpansion.h.

Member Typedef Documentation

◆ nodeSplit

using ogdf::PlanRepExpansion::nodeSplit = PlanRepExpansion::NodeSplit*

Pointer to a node split.

Definition at line 108 of file PlanRepExpansion.h.

Constructor & Destructor Documentation

◆ PlanRepExpansion() [1/2]

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

Creates a planarized expansion of graph G.

All nodes are allowed to be split.

◆ PlanRepExpansion() [2/2]

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.

◆ ~PlanRepExpansion()

ogdf::PlanRepExpansion::~PlanRepExpansion ( )

inline

Definition at line 127 of file PlanRepExpansion.h.

Member Function Documentation

◆ chain()

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

inline

Returns the insertion path of edge eOrig.

Definition at line 150 of file PlanRepExpansion.h.

◆ computeNumberOfCrossings()

int ogdf::PlanRepExpansion::computeNumberOfCrossings ( ) const

Computes the number of crossings.

◆ consistencyCheck()

void ogdf::PlanRepExpansion::consistencyCheck ( ) const

◆ contractSplit() [1/2]

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.

◆ contractSplit() [2/2]

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.

◆ convertDummy()

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

◆ copy() [1/2]

edge ogdf::PlanRepExpansion::copy ( edge eOrig ) const

inline

Returns the first edge in eOrig's insertion path.

Definition at line 153 of file PlanRepExpansion.h.

◆ copy() [2/2]

node ogdf::PlanRepExpansion::copy ( node vOrig ) const

inline

Returns the first copy node of vOrig.

Definition at line 144 of file PlanRepExpansion.h.

◆ currentCC()

int ogdf::PlanRepExpansion::currentCC ( ) const

inline

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

Definition at line 205 of file PlanRepExpansion.h.

◆ delEdge()

virtual void ogdf::PlanRepExpansion::delEdge ( edge e )

overridevirtual

Removes edge e from the planarized expansion.

Reimplemented from ogdf::Graph.

◆ doInit()

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

private

◆ embed()

bool ogdf::PlanRepExpansion::embed ( )

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

◆ enlargeSplit() [1/2]

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.

◆ enlargeSplit() [2/2]

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.

◆ expansion()

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

inline

Returns the list of copy nodes of vOrig.

Definition at line 141 of file PlanRepExpansion.h.

◆ initCC()

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

◆ insertEdgePath()

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

◆ insertEdgePathEmbedded()

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.

◆ isPseudoCrossing()

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

◆ nodesInCC() [1/2]

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

inline

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

Definition at line 217 of file PlanRepExpansion.h.

◆ nodesInCC() [2/2]

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 212 of file PlanRepExpansion.h.

◆ nodeSplitOf()

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 162 of file PlanRepExpansion.h.

◆ nodeSplits()

List<NodeSplit>& ogdf::PlanRepExpansion::nodeSplits ( )

inline

Returns the list of node splits.

Definition at line 170 of file PlanRepExpansion.h.

◆ numberOfCCs()

int ogdf::PlanRepExpansion::numberOfCCs ( ) const

inline

Returns the number of connected components in the original graph.

Definition at line 200 of file PlanRepExpansion.h.

◆ numberOfNodeSplits()

int ogdf::PlanRepExpansion::numberOfNodeSplits ( ) const

inline

Returns the number of node splits.

Definition at line 165 of file PlanRepExpansion.h.

◆ numberOfSplittedNodes()

int ogdf::PlanRepExpansion::numberOfSplittedNodes ( ) const

◆ original() [1/2]

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

inline

Returns a reference to the original graph.

Definition at line 135 of file PlanRepExpansion.h.

◆ original() [2/2]

node ogdf::PlanRepExpansion::original ( node v ) const

inline

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

Definition at line 138 of file PlanRepExpansion.h.

◆ originalEdge()

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 147 of file PlanRepExpansion.h.

◆ position()

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

inline

Definition at line 183 of file PlanRepExpansion.h.

◆ prepareNodeSplit()

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

private

◆ removeEdgePath()

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.

◆ removeEdgePathEmbedded()

void ogdf::PlanRepExpansion::removeEdgePathEmbedded	(	CombinatorialEmbedding &	E,
		edge	eOrig,
		nodeSplit	ns,
		FaceSet< false > &	newFaces,
		NodeSet< false > &	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.

◆ removeSelfLoop() [1/2]

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

◆ removeSelfLoop() [2/2]

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.

◆ resolvePseudoCrossing()

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

◆ separateDummy()

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

◆ setOrigs()

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.

◆ split()

edge ogdf::PlanRepExpansion::split ( edge e )

overridevirtual

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.

Note: The edge e is modified by this operation.

Parameters

e	is the edge to be split.

Returns: The edge e'.

Reimplemented from ogdf::Graph.

◆ splitNodeSplit() [1/2]

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.

◆ splitNodeSplit() [2/2]

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.

◆ splittable()

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

inline

Returns true iff v is splittable.

Definition at line 156 of file PlanRepExpansion.h.

◆ splittableOrig()

bool ogdf::PlanRepExpansion::splittableOrig ( node vOrig ) const

inline

Returns true iff vOrig is splittable.

Definition at line 159 of file PlanRepExpansion.h.

◆ unsplit()

void ogdf::PlanRepExpansion::unsplit	(	edge	eIn,
		edge	eOut
	)

overridevirtual

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.

Parameters

eIn	is the (only) incoming edge of u.
eOut	is the (only) outgoing edge of u.

Reimplemented from ogdf::Graph.

◆ unsplitExpandNode() [1/2]

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.

◆ unsplitExpandNode() [2/2]

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.

Member Data Documentation

◆ m_currentCC

int ogdf::PlanRepExpansion::m_currentCC

private

The index of the current component.

Definition at line 438 of file PlanRepExpansion.h.

◆ m_eAuxCopy

EdgeArray<edge> ogdf::PlanRepExpansion::m_eAuxCopy

private

Definition at line 442 of file PlanRepExpansion.h.

◆ m_eCopy

EdgeArray<List<edge> > ogdf::PlanRepExpansion::m_eCopy

private

The corresponding list of edges in the graph copy.

Definition at line 429 of file PlanRepExpansion.h.

◆ m_eIterator

EdgeArray<ListIterator<edge> > ogdf::PlanRepExpansion::m_eIterator

private

The position of copy edge in the list.

Definition at line 428 of file PlanRepExpansion.h.

◆ m_eNodeSplit

EdgeArray<NodeSplit*> ogdf::PlanRepExpansion::m_eNodeSplit

private

Definition at line 435 of file PlanRepExpansion.h.

◆ m_eOrig

EdgeArray<edge> ogdf::PlanRepExpansion::m_eOrig

private

The corresponding edge in the original graph.

Definition at line 427 of file PlanRepExpansion.h.

◆ m_nodesInCC

Array<List<node> > ogdf::PlanRepExpansion::m_nodesInCC

private

The list of original nodes in each component.

Definition at line 441 of file PlanRepExpansion.h.

◆ m_nodeSplits

List<NodeSplit> ogdf::PlanRepExpansion::m_nodeSplits

private

Definition at line 436 of file PlanRepExpansion.h.

◆ m_numCC

int ogdf::PlanRepExpansion::m_numCC

private

The number of components in the original graph.

Definition at line 439 of file PlanRepExpansion.h.

◆ m_pGraph

const Graph* ogdf::PlanRepExpansion::m_pGraph

private

The original graph.

Definition at line 425 of file PlanRepExpansion.h.

◆ m_splittable

NodeArray<bool> ogdf::PlanRepExpansion::m_splittable

private

Definition at line 433 of file PlanRepExpansion.h.

◆ m_splittableOrig

NodeArray<bool> ogdf::PlanRepExpansion::m_splittableOrig

private

Definition at line 434 of file PlanRepExpansion.h.

◆ m_vCopy

NodeArray<List<node> > ogdf::PlanRepExpansion::m_vCopy

private

The corresponding list of nodes in the graph copy.

Definition at line 431 of file PlanRepExpansion.h.

◆ m_vIterator

NodeArray<ListIterator<node> > ogdf::PlanRepExpansion::m_vIterator

private

The position of copy node in the list.

Definition at line 430 of file PlanRepExpansion.h.

◆ m_vOrig

NodeArray<node> ogdf::PlanRepExpansion::m_vOrig

private

The corresponding node in the original graph.

Definition at line 426 of file PlanRepExpansion.h.

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

include/ogdf/planarity/PlanRepExpansion.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ nodeSplit

Constructor & Destructor Documentation

◆ PlanRepExpansion() [1/2]

◆ PlanRepExpansion() [2/2]

◆ ~PlanRepExpansion()

Member Function Documentation

◆ chain()

◆ computeNumberOfCrossings()

◆ consistencyCheck()

◆ contractSplit() [1/2]

◆ contractSplit() [2/2]

◆ convertDummy()

◆ copy() [1/2]

◆ copy() [2/2]

◆ currentCC()

◆ delEdge()

◆ doInit()

◆ embed()

◆ enlargeSplit() [1/2]

◆ enlargeSplit() [2/2]

◆ expansion()

◆ initCC()

◆ insertEdgePath()

◆ insertEdgePathEmbedded()

◆ isPseudoCrossing()

◆ nodesInCC() [1/2]

◆ nodesInCC() [2/2]

◆ nodeSplitOf()

◆ nodeSplits()

◆ numberOfCCs()

◆ numberOfNodeSplits()

◆ numberOfSplittedNodes()

◆ original() [1/2]

◆ original() [2/2]

◆ originalEdge()

◆ position()

◆ prepareNodeSplit()

◆ removeEdgePath()

◆ removeEdgePathEmbedded()

◆ removeSelfLoop() [1/2]

◆ removeSelfLoop() [2/2]

◆ resolvePseudoCrossing()

◆ separateDummy()

◆ setOrigs()

◆ split()

◆ splitNodeSplit() [1/2]

◆ splitNodeSplit() [2/2]

◆ splittable()

◆ splittableOrig()

◆ unsplit()

◆ unsplitExpandNode() [1/2]

◆ unsplitExpandNode() [2/2]

Member Data Documentation

◆ m_currentCC

◆ m_eAuxCopy

◆ m_eCopy

◆ m_eIterator

◆ m_eNodeSplit

◆ m_eOrig

◆ m_nodesInCC

◆ m_nodeSplits

◆ m_numCC

◆ m_pGraph

◆ m_splittable

◆ m_splittableOrig

◆ m_vCopy

◆ m_vIterator

◆ m_vOrig

Open
Graph Drawing
Framework