Nonplanar 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 stcomponent. 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 nonplanar 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 stcomponent represented by the core edge e to the original graph.  
const List< CutEdge > &  mincut (edge e) const 
Returns the mincut of the stcomponent 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 stcomponent 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 stcomponent 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 Snodes.  
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 nonplanar 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 n1 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 stcomponent 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 stcomponent of a core edge.  
StaticSPQRTree  m_T 
The SPQRTree that represents the original graph.  
EdgeArray< node >  m_tNode 
The t node of the stcomponent 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 
Nonplanar 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 nonplanarity 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: Nonplanar core reduction of graphs. Discrete Mathematics 309(7) (2009) 18381855
If the core reduction is done for a weighted graph, the running time is no longer linear, because the mincut of stcomponents 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.

explicit 
The unweighted version of the Algorithm call and constructor.
This constructor computes the nonplanar core of the graph G
.
G
has to be biconnected.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.
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 nonplanar core of the graph G
.
G
has to be biconnected.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.
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 nonplanar core of the graph G
.
G
has to be biconnected.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.

virtual 
Definition at line 479 of file NonPlanarCore.h.

protected 
The private method behind the constructors.
Definition at line 492 of file NonPlanarCore.h.
Returns the nonplanar core.
Definition at line 112 of file NonPlanarCore.h.

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

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.
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.
Get the mincut of e
with respect to its position in the chain of its original edge.
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.

protected 
Glues together the skeletons of eWinner
and eLoser
for pruned P and Snodes.
This is done, by inserting all nodes and edges of eLoser's
skeleton into eWinner's
skeleton, while preserving the embedding of both skeletons.
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.

protected 
Glues together the mincuts of the winner and the loser edge.
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.
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.
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.
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.

inline 
Returns a map from the edges of the stcomponent represented by the core edge e to the original graph.
Definition at line 163 of file NonPlanarCore.h.

protected 
Marks all nodes of the underlying SPQRTree and prunes planar leaves until the marked nodes span a tree, which has only nonplanar leaves, i.e.
nonplanar Rnodes.
mark  The array where the marking is done 
Definition at line 630 of file NonPlanarCore.h.
Returns the mincut of the stcomponent represented by e
.
Definition at line 172 of file NonPlanarCore.h.

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.
coreEdge  the core edge 
Definition at line 1020 of file NonPlanarCore.h.

inline 
Returns the edges of the original graph, which are represented by e
in the core.
Definition at line 121 of file NonPlanarCore.h.
Returns the node of the original graph, which is represented by v
in the core.
Definition at line 118 of file NonPlanarCore.h.

inline 
Returns the original graph.
Definition at line 115 of file NonPlanarCore.h.
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.

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.
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 pseudocrossings.
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 nonplanar embedding of planarCore is given. 
Definition at line 932 of file NonPlanarCore.h.
Returns the s node of the skeleton of the stcomponent 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.

protected 
To be able to insert crossings correctly, an end graph edge ought to be split into n1 sections if n is the number of crossings on the edge.
This method does exactly that.
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.
Returns the t node of the skeleton of the stcomponent 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.

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 stcomponent 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.
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 stcomponent 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.
Definition at line 67 of file NonPlanarCore.h.
TCosts to cross each edge of the core.
Definition at line 323 of file NonPlanarCore.h.

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.

protected 
The core.
Definition at line 296 of file NonPlanarCore.h.

protected 
The mapping between the edges of each embedding and their original.
Definition at line 332 of file NonPlanarCore.h.

protected 
The mapping between the nodes of each embedding and their original.
Definition at line 329 of file NonPlanarCore.h.

protected 
Traversing path for an edge in the core.
Definition at line 320 of file NonPlanarCore.h.
Corresp. original node.
Definition at line 314 of file NonPlanarCore.h.

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.
The original graph.
Definition at line 299 of file NonPlanarCore.h.
Corresp. original edge (0 if virtual)
Definition at line 317 of file NonPlanarCore.h.
The s node of the stcomponent of a core edge.
Definition at line 338 of file NonPlanarCore.h.

protected 
The SPQRTree that represents the original graph.
Definition at line 326 of file NonPlanarCore.h.
The t node of the stcomponent of a core edge.
Definition at line 341 of file NonPlanarCore.h.

protected 
The graph for the underlying skeleton of a virtual edge in the core.
Definition at line 335 of file NonPlanarCore.h.