# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

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 Graphcore () 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< edgeoriginal (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 GraphoriginalGraph () 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< TCostm_cost
TCosts to cross each edge of the core.

GraphCopym_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< nodem_orig
Corresp. original node.

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

const Graphm_pOriginal
The original graph.

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

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

StaticSPQRTree m_T
The SPQRTree that represents the original graph.

EdgeArray< nodem_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.

## ◆ 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.

## ◆ 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.

## ◆ GlueMap

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

Definition at line 67 of file NonPlanarCore.h.

## ◆ m_cost

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