Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes

ogdf::ExtractKuratowskis Class Reference

Extracts multiple Kuratowski Subdivisions. More...

#include <ogdf/planarity/ExtractKuratowskis.h>

List of all members.

Public Types

enum  enumKuratowskiType { none = 0, K33 = 1, K5 = 2 }
 

Enumeration over Kuratowski Type none, K33, K5.

More...

Public Member Functions

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

Static Public Member Functions

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

Protected Member Functions

void addExternalFacePath (SListPure< edge > &list, const SListPure< adjEntry > &externPath)
 Adds external face edges to list.
adjEntry adjToLowestNodeBelow (node high, int low)
 Returns adjEntry of the edge between node high and a special node.
void addDFSPath (SListPure< edge > &list, node bottom, node top)
 Adds DFS-path from node bottom to node top to list.
void addDFSPathReverse (SListPure< edge > &list, node bottom, node top)
 Adds DFS-path from node top to node bottom to list.
void truncateEdgelist (SListPure< edge > &list1, const SListPure< edge > &list2)
 Separates list1 from edges already contained in list2.
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.
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).
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).
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.
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.
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).
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).
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.
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.
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.
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.
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.

Protected Attributes

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

Detailed Description

Extracts multiple Kuratowski Subdivisions.

Precondition:
Graph has to be simple.

Definition at line 192 of file ExtractKuratowskis.h.

Member Enumeration Documentation

enum ogdf::ExtractKuratowskis::enumKuratowskiType

Enumeration over Kuratowski Type none, K33, K5.

Enumerator:
none 
K33 
K5 

Definition at line 210 of file ExtractKuratowskis.h.

Constructor & Destructor Documentation

ogdf::ExtractKuratowskis::ExtractKuratowskis ( BoyerMyrvoldPlanar &  bm  ) 

Constructor.

ogdf::ExtractKuratowskis::~ExtractKuratowskis (  )  [inline]

Destructor.

Definition at line 197 of file ExtractKuratowskis.h.

Member Function Documentation

void ogdf::ExtractKuratowskis::addDFSPath ( SListPure< edge > &  list,
node  bottom,
node  top 
) [inline, protected]

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

Precondition:
Each virtual node has to be merged.
void ogdf::ExtractKuratowskis::addDFSPathReverse ( SListPure< edge > &  list,
node  bottom,
node  top 
) [inline, protected]

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

Precondition:
Each virtual node has to be merged.
void ogdf::ExtractKuratowskis::addExternalFacePath ( SListPure< edge > &  list,
const SListPure< adjEntry > &  externPath 
) [inline, protected]

Adds external face edges to list.

Definition at line 283 of file ExtractKuratowskis.h.

adjEntry ogdf::ExtractKuratowskis::adjToLowestNodeBelow ( node  high,
int  low 
) [inline, protected]

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.

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

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

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

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

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.

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

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

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.

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.

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

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.

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.

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.

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.

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.

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

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

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

Assignment operator is undefined!

void ogdf::ExtractKuratowskis::truncateEdgelist ( SListPure< edge > &  list1,
const SListPure< edge > &  list2 
) [inline, protected]

Separates list1 from edges already contained in list2.

static int ogdf::ExtractKuratowskis::whichKuratowski ( const Graph &  m_g,
const NodeArray< int > &  m_dfi,
const SListPure< edge > &  list 
) [static]

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

Parameters:
[out] none = no Kuratowski
[out] K33 = the K3,3
[out] K5 = the K5
static int ogdf::ExtractKuratowskis::whichKuratowskiArray ( const Graph &  m_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.
Parameters:
[out] none = no Kuratowski
[out] K33 = the K3,3
[out] K5 = the K5

Member Data Documentation

BoyerMyrvoldPlanar& ogdf::ExtractKuratowskis::BMP [protected]

Link to class BoyerMyrvoldPlanar.

Definition at line 256 of file ExtractKuratowskis.h.

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

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

Definition at line 280 of file ExtractKuratowskis.h.

const bool ogdf::ExtractKuratowskis::m_avoidE2Minors [protected]

Some parameters, see BoyerMyrvold for further instructions.

Definition at line 264 of file ExtractKuratowskis.h.

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

The one and only DFI-NodeArray.

Definition at line 274 of file ExtractKuratowskis.h.

int ogdf::ExtractKuratowskis::m_embeddingGrade [protected]

Some parameters, see BoyerMyrvold for further instructions.

Definition at line 262 of file ExtractKuratowskis.h.

const Graph& ogdf::ExtractKuratowskis::m_g [protected]

Input graph.

Definition at line 259 of file ExtractKuratowskis.h.

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

Returns appropriate node from given DFI.

Definition at line 277 of file ExtractKuratowskis.h.

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 269 of file ExtractKuratowskis.h.

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

Array maintaining visited bits on each node.

Definition at line 271 of file ExtractKuratowskis.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:23 by doxygen 1.7.1.