Open
Graph Drawing
Framework

 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.

Constructor & Destructor Documentation

◆ 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
Gthe graph of which the NPC is to be made
nonPlanarityGuaranteediff 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
Gthe graph of which the NPC is to be made
nonPlanarityGuaranteediff set to true the algorithm runs a bit faster for nonplanar graphs
weightif 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
Gthe graph of which the NPC is to be made
nonPlanarityGuaranteediff set to true the algorithm runs a bit faster for nonplanar graphs
weightif the graph is weighted, the weights otherwise a nullptr
minSTCutModulethe 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.

Member Function Documentation

◆ 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<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 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
winningEdgesThe list of edges that will survive the glue.
losingEdgesThe 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
eThe edge that we want to know the position of in the graphcopy representing the planarized version of the original graph.
cutA 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
eWinnerthe core edge that will represent the newly formed skeleton/embedding
eLoserthe 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
eWinnerthe edge whose mincut gets augmented
eLoserthe 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<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 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
markThe array where the marking is done

Definition at line 633 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 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
coreEdgethe core edge

Definition at line 1021 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 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
planarCorea GraphCopy of the core, in which dummy nodes are inserted to represent crossings
planarGrapha GraphCopy which is replaced by a GraphCopy of the original graph
pCisPlanarSet 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
eThe edge to be split
splitdummiesTo 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
Svthe Skeleton of one of the marked nodes of m_T.
eSan edge in Sv.
patha container to write the traversing path to true iff the source of the edge is on the s side of the cut.
mapVa NodeArray of the original graph to map original nodes to nodes created in this method.
coreEdgethe edge in the core that represents the st-component of which the traversing path is computed.
weight_srcthe weight of the edges of the original graph
minSTCutModulesame as in the constructor

Definition at line 683 of file NonPlanarCore.h.

Friends And Related Function Documentation

◆ GlueMap

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

Definition at line 69 of file NonPlanarCore.h.

Member Data Documentation

◆ m_cost

template<typename TCost = int>
EdgeArray<TCost> 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<EdgeArray<edge> *> 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<NodeArray<node> *> 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<List<CutEdge> > 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<node> 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<edge> 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<node> 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<node> 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<Graph *> 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: