 # OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::NonPlanarCore< TCost > Class Template Reference

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

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

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

virtual ~NonPlanarCore ()

const Graphcore () const
Returns the non-planar core. More...

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

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

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

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

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

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

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

const GraphoriginalGraph () const
Returns the original graph. More...

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

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

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

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

## Protected Member Functions

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

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

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

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

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

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

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

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

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

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

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

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

## Protected Attributes

EdgeArray< TCost > m_cost
Costs to cross each edge of the core. More...

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

Graph m_graph
The core. More...

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

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

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

NodeArray< nodem_orig
Corresp. original node. More...

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

const Graphm_pOriginal
The original graph. More...

EdgeArray< edgem_real
Corresp. original edge (0 if virtual) More...

EdgeArray< nodem_sNode
The s node of the st-component of a core edge. More...

StaticSPQRTree m_T
The SPQRTree that represents the original graph. More...

EdgeArray< nodem_tNode
The t node of the st-component of a core edge. More...

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

## 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 66 of file NonPlanarCore.h.

## ◆ NonPlanarCore() [1/3]

template<typename Cost >
 ogdf::NonPlanarCore< Cost >::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 454 of file NonPlanarCore.h.

## ◆ NonPlanarCore() [2/3]

template<typename TCost = int>
 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

## ◆ NonPlanarCore() [3/3]

template<typename TCost = int>
 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.

## ◆ ~NonPlanarCore()

template<typename Cost >
 ogdf::NonPlanarCore< Cost >::~NonPlanarCore
virtual

Definition at line 482 of file NonPlanarCore.h.

## ◆ call()

template<typename TCost = int>
 void ogdf::NonPlanarCore< Cost >::call ( const Graph & G, const EdgeArray< TCost > * weight, MinSTCutModule< TCost > * minSTCutModule, bool nonPlanarityGuaranteed )
protected

The private method behind the constructors.

Definition at line 495 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 113 of file NonPlanarCore.h.

## ◆ cost() [1/2]

template<typename TCost = int>
 const EdgeArray& 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 157 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 188 of file NonPlanarCore.h.

## ◆ getAllMultiedges()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 825 of file NonPlanarCore.h.

## ◆ getMincut()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1151 of file NonPlanarCore.h.

## ◆ glue()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 844 of file NonPlanarCore.h.

## ◆ glueMincuts()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1179 of file NonPlanarCore.h.

## ◆ importEmbedding()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1067 of file NonPlanarCore.h.

## ◆ inflateCrossing()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1102 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 144 of file NonPlanarCore.h.

## ◆ mapE()

template<typename TCost = int>
 EdgeArray* 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 180 of file NonPlanarCore.h.

## ◆ markCore()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 633 of file NonPlanarCore.h.

## ◆ mincut()

template<typename TCost = int>
 const List& ogdf::NonPlanarCore< TCost >::mincut ( edge e ) const
inline

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

Definition at line 193 of file NonPlanarCore.h.

## ◆ normalizeCutEdgeDirection()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1021 of file NonPlanarCore.h.

## ◆ original() [1/2]

template<typename TCost = int>
 List 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 128 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 123 of file NonPlanarCore.h.

## ◆ originalGraph()

template<typename TCost = int>
 const Graph& ogdf::NonPlanarCore< TCost >::originalGraph ( ) const
inline

Returns the original graph.

Definition at line 118 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 149 of file NonPlanarCore.h.

## ◆ removeSplitdummies()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1032 of file NonPlanarCore.h.

## ◆ retransform()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 935 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 173 of file NonPlanarCore.h.

## ◆ splitEdgeIntoSections()

template<typename Cost >
 void ogdf::NonPlanarCore< Cost >::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 1045 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 165 of file NonPlanarCore.h.

## ◆ traversingPath()

template<typename TCost = int>
 void ogdf::NonPlanarCore< Cost >::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 683 of file NonPlanarCore.h.

## ◆ GlueMap

template<typename TCost = int>
template<typename T >
 friend class GlueMap
friend

Definition at line 69 of file NonPlanarCore.h.

## ◆ m_cost

template<typename TCost = int>
 EdgeArray ogdf::NonPlanarCore< TCost >::m_cost
protected

Costs to cross each edge of the core.

Definition at line 346 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 334 of file NonPlanarCore.h.

## ◆ m_graph

template<typename TCost = int>
 Graph ogdf::NonPlanarCore< TCost >::m_graph
protected

The core.

Definition at line 319 of file NonPlanarCore.h.

## ◆ m_mapE

template<typename TCost = int>
 EdgeArray *> ogdf::NonPlanarCore< TCost >::m_mapE
protected

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

Definition at line 355 of file NonPlanarCore.h.

## ◆ m_mapV

template<typename TCost = int>
 EdgeArray *> ogdf::NonPlanarCore< TCost >::m_mapV
protected

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

Definition at line 352 of file NonPlanarCore.h.

## ◆ m_mincut

template<typename TCost = int>
 EdgeArray > ogdf::NonPlanarCore< TCost >::m_mincut
protected

Traversing path for an edge in the core.

Definition at line 343 of file NonPlanarCore.h.

## ◆ m_orig

template<typename TCost = int>
 NodeArray ogdf::NonPlanarCore< TCost >::m_orig
protected

Corresp. original node.

Definition at line 337 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 328 of file NonPlanarCore.h.

## ◆ m_pOriginal

template<typename TCost = int>
 const Graph* ogdf::NonPlanarCore< TCost >::m_pOriginal
protected

The original graph.

Definition at line 322 of file NonPlanarCore.h.

## ◆ m_real

template<typename TCost = int>
 EdgeArray ogdf::NonPlanarCore< TCost >::m_real
protected

Corresp. original edge (0 if virtual)

Definition at line 340 of file NonPlanarCore.h.

## ◆ m_sNode

template<typename TCost = int>
 EdgeArray ogdf::NonPlanarCore< TCost >::m_sNode
protected

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

Definition at line 361 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 349 of file NonPlanarCore.h.

## ◆ m_tNode

template<typename TCost = int>
 EdgeArray ogdf::NonPlanarCore< TCost >::m_tNode
protected

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

Definition at line 364 of file NonPlanarCore.h.

## ◆ m_underlyingGraphs

template<typename TCost = int>
 EdgeArray ogdf::NonPlanarCore< TCost >::m_underlyingGraphs
protected

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

Definition at line 358 of file NonPlanarCore.h.

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