Open
Graph Drawing
Framework

 v. snapshot-2018-03-28
 

ogdf::ExtractKuratowskis Class Reference

Extracts multiple Kuratowski Subdivisions. More...

#include <ogdf/planarity/ExtractKuratowskis.h>

Public Types

enum  KuratowskiType { KuratowskiType::none = 0, KuratowskiType::K33 = 1, KuratowskiType::K5 = 2 }
 Enumeration over Kuratowski Type none, K33, K5. More...
 

Public Member Functions

 ExtractKuratowskis (BoyerMyrvoldPlanar &bm)
 Constructor. More...
 
 ~ExtractKuratowskis ()
 Destructor. More...
 
void extract (const SListPure< KuratowskiStructure > &allKuratowskis, SList< KuratowskiWrapper > &output)
 Extracts all Kuratowski Subdivisions and adds them to output (without bundles) More...
 
void extractBundles (const SListPure< KuratowskiStructure > &allKuratowskis, SList< KuratowskiWrapper > &output)
 Extracts all Kuratowski Subdivisions and adds them to output (with bundles) More...
 
ExtractKuratowskisoperator= (const ExtractKuratowskis &)
 Assignment operator is undefined! More...
 

Static Public Member Functions

static bool isANewKuratowski (const Graph &g, const SListPure< edge > &kuratowski, const SList< KuratowskiWrapper > &output)
 Returns true, iff the Kuratowski is not already contained in output. More...
 
static bool isANewKuratowski (const EdgeArray< int > &test, const SList< KuratowskiWrapper > &output)
 Returns true, iff the Kuratowski is not already contained in output. More...
 
static KuratowskiType whichKuratowski (const Graph &m_g, const NodeArray< int > &dfi, const SListPure< edge > &list)
 Checks, if list forms a valid Kuratowski Subdivision and returns the type. More...
 
static KuratowskiType whichKuratowskiArray (const Graph &g, EdgeArray< int > &edgenumber)
 Checks, if edges in Array edgenumber form a valid Kuratowski Subdivision and returns the type. More...
 

Protected Member Functions

void addDFSPath (SListPure< edge > &list, node bottom, node top)
 Adds DFS-path from node bottom to node top to list. More...
 
void addDFSPathReverse (SListPure< edge > &list, node bottom, node top)
 Adds DFS-path from node top to node bottom to list. More...
 
void addExternalFacePath (SListPure< edge > &list, const SListPure< adjEntry > &externPath)
 Adds external face edges to list. More...
 
adjEntry adjToLowestNodeBelow (node high, int low)
 Returns adjEntry of the edge between node high and a special node. More...
 
bool checkMinorE2 (bool firstWPath, bool firstWOnHighestXY) const
 Checks for minortype E2 preconditions. More...
 
void extractMinorA (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype A and adds it to list output. More...
 
void extractMinorB (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype B and adds it to list output (no bundles) More...
 
void extractMinorBBundles (SList< KuratowskiWrapper > &output, NodeArray< int > &nodeflags, const int nodemarker, const KuratowskiStructure &k, EdgeArray< int > &flags, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype B and adds it to list output (with bundles) More...
 
void extractMinorC (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype C and adds it to list output. More...
 
void extractMinorD (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype D and adds it to list output. More...
 
void extractMinorE (SList< KuratowskiWrapper > &output, bool firstXPath, bool firstPath, bool firstWPath, bool firstWOnHighestXY, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype E and adds it to list output (no bundles) More...
 
void extractMinorE1 (SList< KuratowskiWrapper > &output, int before, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
 Extracts minorsubtype E1 and adds it to list output. More...
 
void extractMinorE2 (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathZ)
 Extracts minorsubtype E2 and adds it to list output. More...
 
void extractMinorE3 (SList< KuratowskiWrapper > &output, int before, const node z, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
 Extracts minorsubtype E3 and adds it to list output. More...
 
void extractMinorE4 (SList< KuratowskiWrapper > &output, int before, const node z, const node px, const node py, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
 Extracts minorsubtype E4 and adds it to list output. More...
 
void extractMinorE5 (SList< KuratowskiWrapper > &output, const KuratowskiStructure &k, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW, const SListPure< edge > &pathZ, const node endnodeZ)
 Extracts minorsubtype E5 and adds it to list output. More...
 
void extractMinorEBundles (SList< KuratowskiWrapper > &output, bool firstXPath, bool firstPath, bool firstWPath, bool firstWOnHighestXY, NodeArray< int > &nodeflags, const int nodemarker, const KuratowskiStructure &k, EdgeArray< int > &flags, const WInfo &info, const SListPure< edge > &pathX, const node endnodeX, const SListPure< edge > &pathY, const node endnodeY, const SListPure< edge > &pathW)
 Extracts minortype E and adds it to list output (bundles) More...
 
bool isMinorE1 (int before, bool firstXPath, bool firstYPath) const
 Checks for minortype E1. More...
 
bool isMinorE2 (const node endnodeX, const node endnodeY, const node endnodeZ) const
 Checks for minortype E2. More...
 
bool isMinorE3 (const node endnodeX, const node endnodeY, const node endnodeZ) const
 Checks for minortype E3. More...
 
bool isMinorE4 (const node px, const node py, const KuratowskiStructure &k, const WInfo &info) const
 Checks for minortype E4. More...
 
bool isMinorE5 (const node px, const node py, const KuratowskiStructure &k, const node endnodeX, const node endnodeY, const node endnodeZ) const
 Checks for minortype E5 (K5) More...
 
void truncateEdgelist (SListPure< edge > &list1, const SListPure< edge > &list2)
 Separates list1 from edges already contained in list2. More...
 

Protected Attributes

BoyerMyrvoldPlanarBMP
 Link to class BoyerMyrvoldPlanar. More...
 
const NodeArray< adjEntry > & m_adjParent
 The adjEntry which goes from DFS-parent to current vertex. More...
 
const bool m_avoidE2Minors
 Some parameters, see BoyerMyrvold for further instructions. More...
 
const NodeArray< int > & m_dfi
 The one and only DFI-NodeArray. More...
 
int m_embeddingGrade
 Some parameters, see BoyerMyrvold for further instructions. More...
 
const Graphm_g
 Input graph. More...
 
const Array< node > & m_nodeFromDFI
 Returns appropriate node from given DFI. More...
 
int m_nodeMarker
 Value used as marker for visited nodes etc. More...
 
NodeArray< int > m_wasHere
 Array maintaining visited bits on each node. More...
 

Detailed Description

Extracts multiple Kuratowski Subdivisions.

Precondition
Graph has to be simple.

Definition at line 88 of file ExtractKuratowskis.h.

Member Enumeration Documentation

◆ KuratowskiType

Enumeration over Kuratowski Type none, K33, K5.

Enumerator
none 

no kuratowski subdivision exists

K33 

a K3,3 subdivision exists

K5 

a K5 subdivision exists

Definition at line 106 of file ExtractKuratowskis.h.

Constructor & Destructor Documentation

◆ ExtractKuratowskis()

ogdf::ExtractKuratowskis::ExtractKuratowskis ( BoyerMyrvoldPlanar bm)
explicit

Constructor.

◆ ~ExtractKuratowskis()

ogdf::ExtractKuratowskis::~ExtractKuratowskis ( )
inline

Destructor.

Definition at line 93 of file ExtractKuratowskis.h.

Member Function Documentation

◆ addDFSPath()

void ogdf::ExtractKuratowskis::addDFSPath ( SListPure< edge > &  list,
node  bottom,
node  top 
)
inlineprotected

Adds DFS-path from node bottom to node top to list.

Precondition
Each virtual node has to be merged.

◆ addDFSPathReverse()

void ogdf::ExtractKuratowskis::addDFSPathReverse ( SListPure< edge > &  list,
node  bottom,
node  top 
)
inlineprotected

Adds DFS-path from node top to node bottom to list.

Precondition
Each virtual node has to be merged.

◆ addExternalFacePath()

void ogdf::ExtractKuratowskis::addExternalFacePath ( SListPure< edge > &  list,
const SListPure< adjEntry > &  externPath 
)
inlineprotected

Adds external face edges to list.

Definition at line 187 of file ExtractKuratowskis.h.

◆ adjToLowestNodeBelow()

adjEntry ogdf::ExtractKuratowskis::adjToLowestNodeBelow ( node  high,
int  low 
)
inlineprotected

Returns adjEntry of the edge between node high and a special node.

The special node is that node with the lowest DFI not less than the DFI of low.

◆ checkMinorE2()

bool ogdf::ExtractKuratowskis::checkMinorE2 ( bool  firstWPath,
bool  firstWOnHighestXY 
) const
inlineprotected

Checks for minortype E2 preconditions.

Definition at line 329 of file ExtractKuratowskis.h.

◆ extract()

void ogdf::ExtractKuratowskis::extract ( const SListPure< KuratowskiStructure > &  allKuratowskis,
SList< KuratowskiWrapper > &  output 
)

Extracts all Kuratowski Subdivisions and adds them to output (without bundles)

◆ extractBundles()

void ogdf::ExtractKuratowskis::extractBundles ( const SListPure< KuratowskiStructure > &  allKuratowskis,
SList< KuratowskiWrapper > &  output 
)

Extracts all Kuratowski Subdivisions and adds them to output (with bundles)

◆ extractMinorA()

void ogdf::ExtractKuratowskis::extractMinorA ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype A and adds it to list output.

◆ extractMinorB()

void ogdf::ExtractKuratowskis::extractMinorB ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype B and adds it to list output (no bundles)

◆ extractMinorBBundles()

void ogdf::ExtractKuratowskis::extractMinorBBundles ( SList< KuratowskiWrapper > &  output,
NodeArray< int > &  nodeflags,
const int  nodemarker,
const KuratowskiStructure k,
EdgeArray< int > &  flags,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype B and adds it to list output (with bundles)

◆ extractMinorC()

void ogdf::ExtractKuratowskis::extractMinorC ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype C and adds it to list output.

◆ extractMinorD()

void ogdf::ExtractKuratowskis::extractMinorD ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype D and adds it to list output.

◆ extractMinorE()

void ogdf::ExtractKuratowskis::extractMinorE ( SList< KuratowskiWrapper > &  output,
bool  firstXPath,
bool  firstPath,
bool  firstWPath,
bool  firstWOnHighestXY,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype E and adds it to list output (no bundles)

◆ extractMinorE1()

void ogdf::ExtractKuratowskis::extractMinorE1 ( SList< KuratowskiWrapper > &  output,
int  before,
const node  px,
const node  py,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW,
const SListPure< edge > &  pathZ,
const node  endnodeZ 
)
protected

Extracts minorsubtype E1 and adds it to list output.

◆ extractMinorE2()

void ogdf::ExtractKuratowskis::extractMinorE2 ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathZ 
)
protected

Extracts minorsubtype E2 and adds it to list output.

◆ extractMinorE3()

void ogdf::ExtractKuratowskis::extractMinorE3 ( SList< KuratowskiWrapper > &  output,
int  before,
const node  z,
const node  px,
const node  py,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW,
const SListPure< edge > &  pathZ,
const node  endnodeZ 
)
protected

Extracts minorsubtype E3 and adds it to list output.

◆ extractMinorE4()

void ogdf::ExtractKuratowskis::extractMinorE4 ( SList< KuratowskiWrapper > &  output,
int  before,
const node  z,
const node  px,
const node  py,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW,
const SListPure< edge > &  pathZ,
const node  endnodeZ 
)
protected

Extracts minorsubtype E4 and adds it to list output.

◆ extractMinorE5()

void ogdf::ExtractKuratowskis::extractMinorE5 ( SList< KuratowskiWrapper > &  output,
const KuratowskiStructure k,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW,
const SListPure< edge > &  pathZ,
const node  endnodeZ 
)
protected

Extracts minorsubtype E5 and adds it to list output.

◆ extractMinorEBundles()

void ogdf::ExtractKuratowskis::extractMinorEBundles ( SList< KuratowskiWrapper > &  output,
bool  firstXPath,
bool  firstPath,
bool  firstWPath,
bool  firstWOnHighestXY,
NodeArray< int > &  nodeflags,
const int  nodemarker,
const KuratowskiStructure k,
EdgeArray< int > &  flags,
const WInfo info,
const SListPure< edge > &  pathX,
const node  endnodeX,
const SListPure< edge > &  pathY,
const node  endnodeY,
const SListPure< edge > &  pathW 
)
protected

Extracts minortype E and adds it to list output (bundles)

◆ isANewKuratowski() [1/2]

static bool ogdf::ExtractKuratowskis::isANewKuratowski ( const Graph g,
const SListPure< edge > &  kuratowski,
const SList< KuratowskiWrapper > &  output 
)
static

Returns true, iff the Kuratowski is not already contained in output.

◆ isANewKuratowski() [2/2]

static bool ogdf::ExtractKuratowskis::isANewKuratowski ( const EdgeArray< int > &  test,
const SList< KuratowskiWrapper > &  output 
)
static

Returns true, iff the Kuratowski is not already contained in output.

Precondition
Kuratowski Edges are all edges != 0 in the Array.

◆ isMinorE1()

bool ogdf::ExtractKuratowskis::isMinorE1 ( int  before,
bool  firstXPath,
bool  firstYPath 
) const
inlineprotected

Checks for minortype E1.

Definition at line 302 of file ExtractKuratowskis.h.

◆ isMinorE2()

bool ogdf::ExtractKuratowskis::isMinorE2 ( const node  endnodeX,
const node  endnodeY,
const node  endnodeZ 
) const
inlineprotected

Checks for minortype E2.

Definition at line 338 of file ExtractKuratowskis.h.

◆ isMinorE3()

bool ogdf::ExtractKuratowskis::isMinorE3 ( const node  endnodeX,
const node  endnodeY,
const node  endnodeZ 
) const
inlineprotected

Checks for minortype E3.

Definition at line 370 of file ExtractKuratowskis.h.

◆ isMinorE4()

bool ogdf::ExtractKuratowskis::isMinorE4 ( const node  px,
const node  py,
const KuratowskiStructure k,
const WInfo info 
) const
inlineprotected

Checks for minortype E4.

Definition at line 396 of file ExtractKuratowskis.h.

◆ isMinorE5()

bool ogdf::ExtractKuratowskis::isMinorE5 ( const node  px,
const node  py,
const KuratowskiStructure k,
const node  endnodeX,
const node  endnodeY,
const node  endnodeZ 
) const
inlineprotected

Checks for minortype E5 (K5)

Definition at line 422 of file ExtractKuratowskis.h.

◆ operator=()

ExtractKuratowskis& ogdf::ExtractKuratowskis::operator= ( const ExtractKuratowskis )

Assignment operator is undefined!

◆ truncateEdgelist()

void ogdf::ExtractKuratowskis::truncateEdgelist ( SListPure< edge > &  list1,
const SListPure< edge > &  list2 
)
inlineprotected

Separates list1 from edges already contained in list2.

◆ whichKuratowski()

static KuratowskiType ogdf::ExtractKuratowskis::whichKuratowski ( const Graph m_g,
const NodeArray< int > &  dfi,
const SListPure< edge > &  list 
)
static

Checks, if list forms a valid Kuratowski Subdivision and returns the type.

Returns
Returns the following value:
  • none = no Kuratowski
  • K33 = the K3,3
  • K5 = the K5

◆ whichKuratowskiArray()

static KuratowskiType ogdf::ExtractKuratowskis::whichKuratowskiArray ( const Graph g,
EdgeArray< int > &  edgenumber 
)
static

Checks, if edges in Array edgenumber form a valid Kuratowski Subdivision and returns the type.

Precondition
The numer of edges has to be 1 for used edges, otherwise 0.
Returns
Returns the following value:
  • none = no Kuratowski
  • K33 = the K3,3
  • K5 = the K5

Member Data Documentation

◆ BMP

BoyerMyrvoldPlanar& ogdf::ExtractKuratowskis::BMP
protected

Link to class BoyerMyrvoldPlanar.

Definition at line 160 of file ExtractKuratowskis.h.

◆ m_adjParent

const NodeArray<adjEntry>& ogdf::ExtractKuratowskis::m_adjParent
protected

The adjEntry which goes from DFS-parent to current vertex.

Definition at line 184 of file ExtractKuratowskis.h.

◆ m_avoidE2Minors

const bool ogdf::ExtractKuratowskis::m_avoidE2Minors
protected

Some parameters, see BoyerMyrvold for further instructions.

Definition at line 168 of file ExtractKuratowskis.h.

◆ m_dfi

const NodeArray<int>& ogdf::ExtractKuratowskis::m_dfi
protected

The one and only DFI-NodeArray.

Definition at line 178 of file ExtractKuratowskis.h.

◆ m_embeddingGrade

int ogdf::ExtractKuratowskis::m_embeddingGrade
protected

Some parameters, see BoyerMyrvold for further instructions.

Definition at line 166 of file ExtractKuratowskis.h.

◆ m_g

const Graph& ogdf::ExtractKuratowskis::m_g
protected

Input graph.

Definition at line 163 of file ExtractKuratowskis.h.

◆ m_nodeFromDFI

const Array<node>& ogdf::ExtractKuratowskis::m_nodeFromDFI
protected

Returns appropriate node from given DFI.

Definition at line 181 of file ExtractKuratowskis.h.

◆ m_nodeMarker

int ogdf::ExtractKuratowskis::m_nodeMarker
protected

Value used as marker for visited nodes etc.

Used during Backtracking and the extraction of some specific minortypes

Definition at line 173 of file ExtractKuratowskis.h.

◆ m_wasHere

NodeArray<int> ogdf::ExtractKuratowskis::m_wasHere
protected

Array maintaining visited bits on each node.

Definition at line 175 of file ExtractKuratowskis.h.


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