Non-planar core reduction. More...

#include <ogdf/planarity/NonPlanarCore.h>

Classes
struct	CutEdge
	Struct to represent an edge that needs to be crossed in order to cross an st-component. More...

Public Member Functions
	NonPlanarCore (const Graph &G, bool nonPlanarityGuaranteed=false)
	The unweighted version of the Algorithm call and constructor.

	NonPlanarCore (const Graph &G, const EdgeArray< TCost > &weight, bool nonPlanarityGuaranteed=false)
	An slimmed version of the Algorithm call and constructor.

	NonPlanarCore (const Graph &G, const EdgeArray< TCost > &weight, MinSTCutModule< TCost > *minSTCutModule, bool nonPlanarityGuaranteed=false)
	Algorithm call and constructor.

virtual	~NonPlanarCore ()

const Graph &	core () const
	Returns the non-planar core.

const EdgeArray< TCost > &	cost () const
	Returns the costs of the edges in the core, which is the number of original edges crossed, if e is crossed, i.e.

TCost	cost (edge e) const
	Returns the cost of `e`, which is the number of original edges crossed, if `e` is crossed, i.e.

bool	isVirtual (edge e) const
	True iff the edge `e` in the core represents more than one orginal edge and therefore is virtual.

EdgeArray< edge > *	mapE (edge e) const
	Returns a map from the edges of the st-component represented by the core edge e to the original graph.

const List< CutEdge > &	mincut (edge e) const
	Returns the mincut of the st-component represented by `e`.

List< edge >	original (edge e) const
	Returns the edges of the original graph, which are represented by `e` in the core.

node	original (node v) const
	Returns the node of the original graph, which is represented by `v` in the core.

const Graph &	originalGraph () const
	Returns the original graph.

edge	realEdge (edge e) const
	Returns the edge of the orginal graph, which is represented by `e` or nullptr iff `e` is virtual.

void	retransform (const GraphCopy &planarCore, GraphCopy &planarGraph, bool pCisPlanar=true)
	Inserts the crossings from a copy of the core into a copy of the original graph.

node	sNode (edge e) const
	Returns the s node of the skeleton of the st-component represented by the core edge `e` = (s,t) Note that this node is not contained in the input graph, but an internal auxiliary graph.

node	tNode (edge e) const
	Returns the t node of the skeleton of the st-component represented by the core edge `e` = (s,t) Note that this node is not contained in the input graph, but an internal auxiliary graph.

Protected Member Functions
void	call (const Graph &G, const EdgeArray< TCost > weight, MinSTCutModule< TCost > minSTCutModule, bool nonPlanarityGuaranteed)
	The private method behind the constructors.

void	getAllMultiedges (List< edge > &winningEdges, List< edge > &losingEdges)
	Checks for multiedges in the core.

void	getMincut (edge e, List< edge > &cut)
	Get the mincut of `e` with respect to its position in the chain of its original edge.

void	glue (edge eWinner, edge eLoser)
	Glues together the skeletons of `eWinner` and `eLoser` for pruned P- and S-nodes.

void	glueMincuts (edge eWinner, edge eLoser)
	Glues together the mincuts of the winner and the loser edge.

void	importEmbedding (edge e)
	This method asserts that all parts of the end graph that are represented by edge `e` internally have the same embedding every time retransform is called, regardless of which planarization of the core is given.

void	inflateCrossing (node v)
	The crossing denoted by dummy node `v` from the planarized copy of the core get inserted into the end graph.

void	markCore (NodeArray< bool > &mark)
	Marks all nodes of the underlying SPQRTree and prunes planar leaves until the marked nodes span a tree, which has only non-planar leaves, i.e.

void	normalizeCutEdgeDirection (edge coreEdge)
	Every edge of `coreEdge's` cut that doesn't go the same direction as `coreEdge` gets reversed.

void	removeSplitdummies (List< node > &splitdummies)
	After inserting the crossings, the end graph edges don't need to be partitioned anymore so the `splitdummies` get removed.

void	splitEdgeIntoSections (edge e, List< node > &splitdummies)
	To be able to insert crossings correctly, an end graph edge ought to be split into n-1 sections if n is the number of crossings on the edge.

void	traversingPath (const Skeleton &Sv, edge eS, List< CutEdge > &path, NodeArray< node > &mapV, edge coreEdge, const EdgeArray< TCost > weight_src, MinSTCutModule< TCost > minSTCutModule)
	Computes the traversing path for a given edge and the unmarked tree rooted in the node of `eS` and saves the combinatorial embedding of the st-component which `eS` represents, i.e.

Protected Attributes
EdgeArray< TCost >	m_cost
	TCosts to cross each edge of the core.

GraphCopy *	m_endGraph
	A pointer to a copy of the original graph, in which crossings are replaced by dummy nodes.

Graph	m_graph
	The core.

EdgeArray< EdgeArray< edge > * >	m_mapE
	The mapping between the edges of each embedding and their original.

EdgeArray< NodeArray< node > * >	m_mapV
	The mapping between the nodes of each embedding and their original.

EdgeArray< List< CutEdge > >	m_mincut
	Traversing path for an edge in the core.

NodeArray< node >	m_orig
	Corresp. original node.

const GraphCopy *	m_planarCore
	A pointer to a copy of the core, in which crossings are replaced by dummy nodes.

const Graph *	m_pOriginal
	The original graph.

EdgeArray< edge >	m_real
	Corresp. original edge (0 if virtual)

EdgeArray< node >	m_sNode
	The s node of the st-component of a core edge.

StaticSPQRTree	m_T
	The SPQRTree that represents the original graph.

EdgeArray< node >	m_tNode
	The t node of the st-component of a core edge.

EdgeArray< Graph * >	m_underlyingGraphs
	The graph for the underlying skeleton of a virtual edge in the core.

Friends
template<typename T >
class	GlueMap

Detailed Description

template<typename TCost = int>
class ogdf::NonPlanarCore< TCost >

Non-planar core reduction.

The class ogdf::NonPlanarCore implements a reduction method that reduces a graph to a smaller core graph which behaves invariant with respect to non-planarity measures like crossing number, skewness, coarseness, and thickness. The core reduction is based on the decomposition of a graph into its triconnected components and can be computed in linear time.

The implementation is based on the following publication:

Markus Chimani, Carsten Gutwenger: Non-planar core reduction of graphs. Discrete Mathematics 309(7) (2009) 1838-1855

If the core reduction is done for a weighted graph, the running time is no longer linear, because the mincut of st-components can't be calculated via BFS anymore, but either via Dijkstra (default) on the dual graph (O(n log n)) or via any other minSTCut routine. In tests we found out that Dijkstra outperforms all other minSTCut routines for all instances.

Definition at line 65 of file NonPlanarCore.h.

Constructor & Destructor Documentation

◆ NonPlanarCore() [1/3]

template<typename TCost >

ogdf::NonPlanarCore< TCost >::NonPlanarCore	(	const Graph &	G,
		bool	nonPlanarityGuaranteed = `false`
	)

explicit

The unweighted version of the Algorithm call and constructor.

This constructor computes the non-planar core of the graph G.

Precondition: G has to be biconnected.

Parameters

G	the graph of which the NPC is to be made
nonPlanarityGuaranteed	iff set to true the algorithm runs a bit faster for nonplanar graphs

Definition at line 427 of file NonPlanarCore.h.

◆ NonPlanarCore() [2/3]

template<typename TCost >

ogdf::NonPlanarCore< TCost >::NonPlanarCore	(	const Graph &	G,
		const EdgeArray< TCost > &	weight,
		bool	nonPlanarityGuaranteed = `false`
	)

An slimmed version of the Algorithm call and constructor.

This constructor computes the non-planar core of the graph G.

Precondition: G has to be biconnected.

Parameters

G	the graph of which the NPC is to be made
nonPlanarityGuaranteed	iff set to true the algorithm runs a bit faster for nonplanar graphs
weight	if the graph is weighted, the weights otherwise a nullptr

Definition at line 461 of file NonPlanarCore.h.

◆ NonPlanarCore() [3/3]

template<typename TCost >

ogdf::NonPlanarCore< TCost >::NonPlanarCore	(	const Graph &	G,
		const EdgeArray< TCost > &	weight,
		MinSTCutModule< TCost > *	minSTCutModule,
		bool	nonPlanarityGuaranteed = `false`
	)

Algorithm call and constructor.

This constructor computes the non-planar core of the graph G.

Precondition: G has to be biconnected.

Parameters

G	the graph of which the NPC is to be made
nonPlanarityGuaranteed	iff set to true the algorithm runs a bit faster for nonplanar graphs
weight	if the graph is weighted, the weights otherwise a nullptr
minSTCutModule	the MaxFlowModule that should be used for calculating the traversing path for weighted graphs.

Definition at line 444 of file NonPlanarCore.h.

◆ ~NonPlanarCore()

template<typename TCost >

ogdf::NonPlanarCore< TCost >::~NonPlanarCore ( )

virtual

Definition at line 479 of file NonPlanarCore.h.

Member Function Documentation

◆ call()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::call	(	const Graph &	G,
		const EdgeArray< TCost > *	weight,
		MinSTCutModule< TCost > *	minSTCutModule,
		bool	nonPlanarityGuaranteed
	)

protected

The private method behind the constructors.

Definition at line 492 of file NonPlanarCore.h.

◆ core()

template<typename TCost = int>

const Graph & ogdf::NonPlanarCore< TCost >::core ( ) const

inline

Returns the non-planar core.

Definition at line 112 of file NonPlanarCore.h.

◆ cost() [1/2]

template<typename TCost = int>

const EdgeArray< TCost > & ogdf::NonPlanarCore< TCost >::cost ( ) const

inline

Returns the costs of the edges in the core, which is the number of original edges crossed, if e is crossed, i.e.

one if an edge is real and |mincut(edge)| if an edge is virtual

Definition at line 146 of file NonPlanarCore.h.

◆ cost() [2/2]

template<typename TCost = int>

TCost ogdf::NonPlanarCore< TCost >::cost ( edge e ) const

inline

Returns the cost of e, which is the number of original edges crossed, if e is crossed, i.e.

1 if e is real and |mincut(e)| if e is virtual

Definition at line 169 of file NonPlanarCore.h.

◆ getAllMultiedges()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::getAllMultiedges	(	List< edge > &	winningEdges,
		List< edge > &	losingEdges
	)

protected

Checks for multiedges in the core.

This method is a slightly modified version of ogdf::IsParallelFreeUndirected(), that adds the functionality that the found multiedges are stored in lists.

Parameters

winningEdges	The list of edges that will survive the glue.
losingEdges	The list of edges that won't survive the glue.

Definition at line 822 of file NonPlanarCore.h.

◆ getMincut()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::getMincut	(	edge	e,
		List< edge > &	cut
	)

protected

Get the mincut of e with respect to its position in the chain of its original edge.

Parameters

e	The edge that we want to know the position of in the graphcopy representing the planarized version of the original graph.
cut	A list to write the mincut to.

Definition at line 1150 of file NonPlanarCore.h.

◆ glue()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::glue	(	edge	eWinner,
		edge	eLoser
	)

protected

Glues together the skeletons of eWinner and eLoser for pruned P- and S-nodes.

This is done, by inserting all nodes and edges of eLoser's skeleton into eWinner's skeleton, while preserving the embedding of both skeletons.

Parameters

eWinner	the core edge that will represent the newly formed skeleton/embedding
eLoser	the core edge that is copied from

Definition at line 841 of file NonPlanarCore.h.

◆ glueMincuts()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::glueMincuts	(	edge	eWinner,
		edge	eLoser
	)

protected

Glues together the mincuts of the winner and the loser edge.

Parameters

eWinner	the edge whose mincut gets augmented
eLoser	the edge whose mincut gets glued to the winner mincut

Definition at line 1178 of file NonPlanarCore.h.

◆ importEmbedding()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::importEmbedding ( edge e )

protected

This method asserts that all parts of the end graph that are represented by edge e internally have the same embedding every time retransform is called, regardless of which planarization of the core is given.

Only nodes that are present in the core can have a different embedding for a different planarization of the core. They are infact reassembling the planarization of the core.

Definition at line 1066 of file NonPlanarCore.h.

◆ inflateCrossing()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::inflateCrossing ( node v )

protected

The crossing denoted by dummy node v from the planarized copy of the core get inserted into the end graph.

Definition at line 1101 of file NonPlanarCore.h.

◆ isVirtual()

template<typename TCost = int>

bool ogdf::NonPlanarCore< TCost >::isVirtual ( edge e ) const

inline

True iff the edge e in the core represents more than one orginal edge and therefore is virtual.

Definition at line 137 of file NonPlanarCore.h.

◆ mapE()

template<typename TCost = int>

EdgeArray< edge > * ogdf::NonPlanarCore< TCost >::mapE ( edge e ) const

inline

Returns a map from the edges of the st-component represented by the core edge e to the original graph.

Definition at line 163 of file NonPlanarCore.h.

◆ markCore()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::markCore ( NodeArray< bool > & mark )

protected

Marks all nodes of the underlying SPQRTree and prunes planar leaves until the marked nodes span a tree, which has only non-planar leaves, i.e.

non-planar R-nodes.

Parameters

mark	The array where the marking is done

Definition at line 630 of file NonPlanarCore.h.

◆ mincut()

template<typename TCost = int>

const List< CutEdge > & ogdf::NonPlanarCore< TCost >::mincut ( edge e ) const

inline

Returns the mincut of the st-component represented by e.

Definition at line 172 of file NonPlanarCore.h.

◆ normalizeCutEdgeDirection()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::normalizeCutEdgeDirection ( edge coreEdge )

protected

Every edge of coreEdge's cut that doesn't go the same direction as coreEdge gets reversed.

This method is used to both normalize the cutedges and denormalize them after the retransformation.

Parameters

coreEdge the core edge

Definition at line 1020 of file NonPlanarCore.h.

◆ original() [1/2]

template<typename TCost = int>

List< edge > ogdf::NonPlanarCore< TCost >::original ( edge e ) const

inline

Returns the edges of the original graph, which are represented by e in the core.

Definition at line 121 of file NonPlanarCore.h.

◆ original() [2/2]

template<typename TCost = int>

node ogdf::NonPlanarCore< TCost >::original ( node v ) const

inline

Returns the node of the original graph, which is represented by v in the core.

Definition at line 118 of file NonPlanarCore.h.

◆ originalGraph()

template<typename TCost = int>

const Graph & ogdf::NonPlanarCore< TCost >::originalGraph ( ) const

inline

Returns the original graph.

Definition at line 115 of file NonPlanarCore.h.

◆ realEdge()

template<typename TCost = int>

edge ogdf::NonPlanarCore< TCost >::realEdge ( edge e ) const

inline

Returns the edge of the orginal graph, which is represented by e or nullptr iff e is virtual.

Definition at line 140 of file NonPlanarCore.h.

◆ removeSplitdummies()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::removeSplitdummies ( List< node > & splitdummies )

protected

After inserting the crossings, the end graph edges don't need to be partitioned anymore so the splitdummies get removed.

Definition at line 1031 of file NonPlanarCore.h.

◆ retransform()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::retransform	(	const GraphCopy &	planarCore,
		GraphCopy &	planarGraph,
		bool	pCisPlanar = `true`
	)

Inserts the crossings from a copy of the core into a copy of the original graph.

This method expects planarCore to be planarly embedded without pseudo-crossings.

Parameters

planarCore	a GraphCopy of the core, in which dummy nodes are inserted to represent crossings
planarGraph	a GraphCopy which is replaced by a GraphCopy of the original graph
pCisPlanar	Set this to true if a non-planar embedding of `planarCore` is given.

Definition at line 932 of file NonPlanarCore.h.

◆ sNode()

template<typename TCost = int>

node ogdf::NonPlanarCore< TCost >::sNode ( edge e ) const

inline

Returns the s node of the skeleton of the st-component represented by the core edge e = (s,t) Note that this node is not contained in the input graph, but an internal auxiliary graph.

Definition at line 158 of file NonPlanarCore.h.

◆ splitEdgeIntoSections()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::splitEdgeIntoSections	(	edge	e,
		List< node > &	splitdummies
	)

protected

To be able to insert crossings correctly, an end graph edge ought to be split into n-1 sections if n is the number of crossings on the edge.

This method does exactly that.

Parameters

e	The edge to be split
splitdummies	To delete the inserted dummynodes later, we store all of them in here

Definition at line 1044 of file NonPlanarCore.h.

◆ tNode()

template<typename TCost = int>

node ogdf::NonPlanarCore< TCost >::tNode ( edge e ) const

inline

Returns the t node of the skeleton of the st-component represented by the core edge e = (s,t) Note that this node is not contained in the input graph, but an internal auxiliary graph.

Definition at line 152 of file NonPlanarCore.h.

◆ traversingPath()

template<typename TCost >

void ogdf::NonPlanarCore< TCost >::traversingPath	(	const Skeleton &	Sv,
		edge	eS,
		List< CutEdge > &	path,
		NodeArray< node > &	mapV,
		edge	coreEdge,
		const EdgeArray< TCost > *	weight_src,
		MinSTCutModule< TCost > *	minSTCutModule
	)

protected

Computes the traversing path for a given edge and the unmarked tree rooted in the node of eS and saves the combinatorial embedding of the st-component which eS represents, i.e.

a list of edges that are to be crossed, when the given edge is crossed in the core. This list is minimal.

Parameters

Sv	the Skeleton of one of the marked nodes of m_T.
eS	an edge in `Sv`.
path	a container to write the traversing path to `true` iff the source of the edge is on the s side of the cut.
mapV	a NodeArray of the original graph to map original nodes to nodes created in this method.
coreEdge	the edge in the core that represents the st-component of which the traversing path is computed.
weight_src	the weight of the edges of the original graph
minSTCutModule	same as in the constructor

Definition at line 680 of file NonPlanarCore.h.

Friends And Related Symbol Documentation

◆ GlueMap

template<typename TCost = int>

template<typename T >

friend class GlueMap

friend

Definition at line 67 of file NonPlanarCore.h.

Member Data Documentation

◆ m_cost

template<typename TCost = int>

EdgeArray<TCost> ogdf::NonPlanarCore< TCost >::m_cost

protected

TCosts to cross each edge of the core.

Definition at line 323 of file NonPlanarCore.h.

◆ m_endGraph

template<typename TCost = int>

GraphCopy* ogdf::NonPlanarCore< TCost >::m_endGraph

protected

A pointer to a copy of the original graph, in which crossings are replaced by dummy nodes.

It's a nullptr unless NonPlanarCore::retransform was called.

Definition at line 311 of file NonPlanarCore.h.

◆ m_graph

template<typename TCost = int>

Graph ogdf::NonPlanarCore< TCost >::m_graph

protected

The core.

Definition at line 296 of file NonPlanarCore.h.

◆ m_mapE

template<typename TCost = int>

EdgeArray<EdgeArray<edge>*> ogdf::NonPlanarCore< TCost >::m_mapE

protected

The mapping between the edges of each embedding and their original.

Definition at line 332 of file NonPlanarCore.h.

◆ m_mapV

template<typename TCost = int>

EdgeArray<NodeArray<node>*> ogdf::NonPlanarCore< TCost >::m_mapV

protected

The mapping between the nodes of each embedding and their original.

Definition at line 329 of file NonPlanarCore.h.

◆ m_mincut

template<typename TCost = int>

EdgeArray<List<CutEdge> > ogdf::NonPlanarCore< TCost >::m_mincut

protected

Traversing path for an edge in the core.

Definition at line 320 of file NonPlanarCore.h.

◆ m_orig

template<typename TCost = int>

NodeArray<node> ogdf::NonPlanarCore< TCost >::m_orig

protected

Corresp. original node.

Definition at line 314 of file NonPlanarCore.h.

◆ m_planarCore

template<typename TCost = int>

const GraphCopy* ogdf::NonPlanarCore< TCost >::m_planarCore

protected

A pointer to a copy of the core, in which crossings are replaced by dummy nodes.

It's a nullptr unless NonPlanarCore::retransform was called.

Definition at line 305 of file NonPlanarCore.h.

◆ m_pOriginal

template<typename TCost = int>

const Graph* ogdf::NonPlanarCore< TCost >::m_pOriginal

protected

The original graph.

Definition at line 299 of file NonPlanarCore.h.

◆ m_real

template<typename TCost = int>

EdgeArray<edge> ogdf::NonPlanarCore< TCost >::m_real

protected

Corresp. original edge (0 if virtual)

Definition at line 317 of file NonPlanarCore.h.

◆ m_sNode

template<typename TCost = int>

EdgeArray<node> ogdf::NonPlanarCore< TCost >::m_sNode

protected

The s node of the st-component of a core edge.

Definition at line 338 of file NonPlanarCore.h.

◆ m_T

template<typename TCost = int>

StaticSPQRTree ogdf::NonPlanarCore< TCost >::m_T

protected

The SPQRTree that represents the original graph.

Definition at line 326 of file NonPlanarCore.h.

◆ m_tNode

template<typename TCost = int>

EdgeArray<node> ogdf::NonPlanarCore< TCost >::m_tNode

protected

The t node of the st-component of a core edge.

Definition at line 341 of file NonPlanarCore.h.

◆ m_underlyingGraphs

template<typename TCost = int>

EdgeArray<Graph*> ogdf::NonPlanarCore< TCost >::m_underlyingGraphs

protected

The graph for the underlying skeleton of a virtual edge in the core.

Definition at line 335 of file NonPlanarCore.h.

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

include/ogdf/planarity/NonPlanarCore.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ NonPlanarCore() [1/3]

◆ NonPlanarCore() [2/3]

◆ NonPlanarCore() [3/3]

◆ ~NonPlanarCore()

Member Function Documentation

◆ call()

◆ core()

◆ cost() [1/2]

◆ cost() [2/2]

◆ getAllMultiedges()

◆ getMincut()

◆ glue()

◆ glueMincuts()

◆ importEmbedding()

◆ inflateCrossing()

◆ isVirtual()

◆ mapE()

◆ markCore()

◆ mincut()

◆ normalizeCutEdgeDirection()

◆ original() [1/2]

◆ original() [2/2]

◆ originalGraph()

◆ realEdge()

◆ removeSplitdummies()

◆ retransform()

◆ sNode()

◆ splitEdgeIntoSections()

◆ tNode()

◆ traversingPath()

Friends And Related Symbol Documentation

◆ GlueMap

Member Data Documentation

◆ m_cost

◆ m_endGraph

◆ m_graph

◆ m_mapE

◆ m_mapV

◆ m_mincut

◆ m_orig

◆ m_planarCore

◆ m_pOriginal

◆ m_real

◆ m_sNode

◆ m_T

◆ m_tNode

◆ m_underlyingGraphs

Open
Graph Drawing
Framework