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

ExtractKuratowskis &	operator= (const ExtractKuratowskis &)
	Assignment operator is undefined! More...

Static Public Member Functions
static bool	isANewKuratowski (const EdgeArray< int > &test, const SList< KuratowskiWrapper > &output)
	Returns true, iff the Kuratowski is not already contained in output. More...

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 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
BoyerMyrvoldPlanar &	BMP
	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 Graph &	m_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 95 of file ExtractKuratowskis.h.

Member Enumeration Documentation

◆ KuratowskiType

enum ogdf::ExtractKuratowskis::KuratowskiType

strong

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

Constructor & Destructor Documentation

◆ ExtractKuratowskis()

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

explicit

Constructor.

◆ ~ExtractKuratowskis()

ogdf::ExtractKuratowskis::~ExtractKuratowskis ( )

inline

Destructor.

Definition at line 101 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 265 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 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.

◆ isANewKuratowski() [2/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.

◆ isMinorE1()

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

inlineprotected

Checks for minortype E1.

Definition at line 251 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 270 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 293 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 306 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 319 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:

include/ogdf/planarity/ExtractKuratowskis.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

◆ KuratowskiType

Constructor & Destructor Documentation

◆ ExtractKuratowskis()

◆ ~ExtractKuratowskis()

Member Function Documentation

◆ addDFSPath()

◆ addDFSPathReverse()

◆ addExternalFacePath()

◆ adjToLowestNodeBelow()

◆ checkMinorE2()

◆ extract()

◆ extractBundles()

◆ extractMinorA()

◆ extractMinorB()

◆ extractMinorBBundles()

◆ extractMinorC()

◆ extractMinorD()

◆ extractMinorE()

◆ extractMinorE1()

◆ extractMinorE2()

◆ extractMinorE3()

◆ extractMinorE4()

◆ extractMinorE5()

◆ extractMinorEBundles()

◆ isANewKuratowski() [1/2]

◆ isANewKuratowski() [2/2]

◆ isMinorE1()

◆ isMinorE2()

◆ isMinorE3()

◆ isMinorE4()

◆ isMinorE5()

◆ operator=()

◆ truncateEdgelist()

◆ whichKuratowski()

◆ whichKuratowskiArray()

Member Data Documentation

◆ BMP

◆ m_adjParent

◆ m_avoidE2Minors

◆ m_dfi

◆ m_embeddingGrade

◆ m_g

◆ m_nodeFromDFI

◆ m_nodeMarker

◆ m_wasHere

Open
Graph Drawing
Framework