This class implements the extended BoyerMyrvold planarity embedding algorithm. More...

#include <ogdf/planarity/boyer_myrvold/BoyerMyrvoldPlanar.h>

Public Types
enum	EmbeddingGrade { EmbeddingGrade::doNotEmbed = -3, EmbeddingGrade::doNotFind = -2, EmbeddingGrade::doFindUnlimited = -1, EmbeddingGrade::doFindZero = 0 }
	Denotes the different embedding options. More...

Public Member Functions
	BoyerMyrvoldPlanar (Graph &g, bool bundles, EmbeddingGrade embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
	Constructor, for parameters see BoyerMyrvold. More...

	BoyerMyrvoldPlanar (Graph &g, bool bundles, int embeddingGrade, bool limitStructures, SListPure< KuratowskiStructure > &output, double randomness, bool avoidE2Minors, bool extractSubgraph, const EdgeArray< int > *edgeCosts=nullptr)
	Constructor, for parameters see BoyerMyrvold. More...

void	flipBicomp (int c, int marker, NodeArray< int > &visited, bool wholeGraph, bool deleteFlipFlags)
	Flips all nodes of the bicomp with unique, real, rootchild c as necessary. More...

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

void	seed (const std::minstd_rand rand)
	Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator. More...

bool	start ()
	Starts the embedding algorithm. More...

Static Public Attributes
const static int	DirectionCCW
	Direction for counterclockwise traversal. More...

const static int	DirectionCW
	Direction for clockwise traversal. More...

Protected Member Functions
Methods for Walkup and Walkdown
bool	pertinent (node w) const
	Checks whether node `w` is pertinent. `w` has to be non-virtual. More...

bool	internallyActive (node w, int v) const
	Checks whether real node `w` is internally active while embedding node with DFI `v`. More...

bool	externallyActive (node w, int v) const
	Checks whether real node `w` is externally active while embedding node with DFI `v`. More...

bool	inactive (node w, int v)
	Checks whether real node `w` is inactive while embedding node with DFI `v`. More...

int	infoAboutNode (node w, int v) const
	Checks all dynamic information about a node `w` while embedding node with DFI `v`. More...

node	successorOnExternalFace (node w, int &direction) const
	Walks upon external face in the given `direction` starting at `w`. More...

node	successorWithoutShortCircuit (node w, int &direction)
	Walks upon external face in given `direction` avoiding short circuit edges. More...

node	constSuccessorOnExternalFace (node v, int direction)
	Returns the successornode on the external face in given `direction`. More...

node	constSuccessorWithoutShortCircuit (node v, int direction) const
	Walks upon external face in `direction` avoiding short circuit edges. More...

adjEntry	beforeShortCircuitEdge (node v, int direction) const
	Returns underlying former adjEntry, if a short circuit edge in `direction` of `v` exists. More...

node	activeSuccessor (node w, int &direction, int v, int &info) const
	Walks upon external face in the given `direction` starting at `w` until an active vertex is reached. More...

node	constActiveSuccessor (node w, int direction, int v, int &info) const
	Walks upon external face in the given `direction` (without changing it) until an active vertex is reached. More...

bool	wNodesExist (node root, node stopx, node stopy) const
	Checks, if one ore more wNodes exist between the two stopping vertices `stopx` and `stopy`. More...

void	printNodeInfo (node v)
	Prints informations about node `v`. More...

void	mergeBiconnectedComponent (ArrayBuffer< int > &stack)
	Merges the last two biconnected components saved in `stack`. Embeds them iff m_embeddingGrade != EmbeddingGrade::doNotEmbed. More...

void	embedBackedges (const node v, const int v_dir, const node w, const int w_dir)
	Links (and embeds iff m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node `v` with direction `v_dir` to node `w` with direction `w_dir`. More...

void	createShortCircuitEdge (const node v, const int v_dir, const node w, const int w_dir)
	Creates a short circuit edge from node `v` with direction `v_dir` to node `w` with direction `w_dir`. More...

node	walkup (const node v, const node w, const int marker, const edge back)
	Walkup: Builds the pertinent subgraph for the backedge `back`. More...

int	walkdown (const int i, const node v, FindKuratowskis *findKuratowskis)
	Walkdown: Embeds all backedges with DFI `i` as targetnode to node `v`. More...

void	mergeUnprocessedNodes ()
	Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart. More...

void	postProcessEmbedding ()
	Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped. More...

bool	embed ()
	Starts the embedding phase, which embeds m_g node by node in descending DFI-order. More...

Protected Attributes
bool	m_extractSubgraph = true
	Flag for extracting a planar subgraph instead of testing for planarity. More...

int	m_flippedNodes
	The whole number of bicomps, which have to be flipped. More...

Graph &	m_g
	Input graph, which can be altered. More...

Some parameters... see BoyerMyrvold for further options
const bool	m_bundles

const int	m_embeddingGrade

const bool	m_limitStructures

const double	m_randomness

const bool	m_avoidE2Minors

const EdgeArray< int > *	m_edgeCosts

std::minstd_rand	m_rand

Members from BoyerMyrvoldInit
NodeArray< node >	m_realVertex
	Link to non-virtual vertex of a virtual Vertex. More...

NodeArray< int >	m_dfi
	The one and only DFI-NodeArray. More...

Array< node >	m_nodeFromDFI
	Returns appropriate node from given DFI. More...

NodeArray< adjEntry >	m_link [2]
	Links to opposite adjacency entries on external face in clockwise resp. ccw order. More...

NodeArray< adjEntry >	m_beforeSCE [2]
	Links for short circuit edges. More...

NodeArray< adjEntry >	m_adjParent
	The adjEntry which goes from DFS-parent to current vertex. More...

NodeArray< int >	m_leastAncestor
	The DFI of the least ancestor node over all backedges. More...

EdgeArray< BoyerMyrvoldEdgeType >	m_edgeType
	Contains the type of each edge. More...

NodeArray< int >	m_lowPoint
	The lowpoint of each node. More...

NodeArray< int >	m_highestSubtreeDFI
	The highest DFI in a subtree with node as root. More...

NodeArray< ListPure< node > >	m_separatedDFSChildList
	A list to all separated DFS-children of node. More...

NodeArray< ListIterator< node > >	m_pNodeInParent
	Pointer to node contained in the DFSChildList of his parent, if exists. More...

Members for Walkup and Walkdown
NodeArray< int >	m_visited
	This Array keeps track of all vertices that are visited by current walkup. More...

EdgeArray< node >	m_pointsToRoot
	Identifies the rootnode of the child bicomp the given backedge points to. More...

NodeArray< edge >	m_visitedWithBackedge
	Stores for each (real) non-root vertex v with which backedge it was visited during the walkup. More...

NodeArray< int >	m_numUnembeddedBackedgesInBicomp
	Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded. More...

NodeArray< bool >	m_flipped
	Iff true, the node is the root of a bicomp which has to be flipped. More...

NodeArray< SListPure< adjEntry > >	m_backedgeFlags
	Holds information, if node is the source of a backedge. More...

NodeArray< SListPure< node > >	m_pertinentRoots
	List of virtual bicomp roots, that are pertinent to the current embedded node. More...

SListPure< KuratowskiStructure > &	m_output
	Data structure for the Kuratowski subdivisions, which will be returned. More...

Friends
class	boyer_myrvold::BoyerMyrvoldInit

class	BoyerMyrvold

class	ExtractKuratowskis

class	FindKuratowskis

Detailed Description

This class implements the extended BoyerMyrvold planarity embedding algorithm.

Definition at line 66 of file BoyerMyrvoldPlanar.h.

Member Enumeration Documentation

◆ EmbeddingGrade

enum ogdf::BoyerMyrvoldPlanar::EmbeddingGrade

strong

Denotes the different embedding options.

Enumerator
doNotEmbed
doNotFind
doFindUnlimited
doFindZero

Definition at line 80 of file BoyerMyrvoldPlanar.h.

Constructor & Destructor Documentation

◆ BoyerMyrvoldPlanar() [1/2]

ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar	(	Graph &	g,
		bool	bundles,
		int	embeddingGrade,
		bool	limitStructures,
		SListPure< KuratowskiStructure > &	output,
		double	randomness,
		bool	avoidE2Minors,
		bool	extractSubgraph,
		const EdgeArray< int > *	edgeCosts = `nullptr`
	)

Constructor, for parameters see BoyerMyrvold.

◆ BoyerMyrvoldPlanar() [2/2]

ogdf::BoyerMyrvoldPlanar::BoyerMyrvoldPlanar	(	Graph &	g,
		bool	bundles,
		EmbeddingGrade	embeddingGrade,
		bool	limitStructures,
		SListPure< KuratowskiStructure > &	output,
		double	randomness,
		bool	avoidE2Minors,
		bool	extractSubgraph,
		const EdgeArray< int > *	edgeCosts = `nullptr`
	)

inline

Constructor, for parameters see BoyerMyrvold.

Definition at line 93 of file BoyerMyrvoldPlanar.h.

Member Function Documentation

◆ activeSuccessor()

node ogdf::BoyerMyrvoldPlanar::activeSuccessor	(	node	w,
		int &	direction,
		int	v,
		int &	info
	)		const

protected

Walks upon external face in the given direction starting at w until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex.

◆ beforeShortCircuitEdge()

adjEntry ogdf::BoyerMyrvoldPlanar::beforeShortCircuitEdge	(	node	v,
		int	direction
	)		const

inlineprotected

Returns underlying former adjEntry, if a short circuit edge in direction of v exists.

Otherwise the common edge is returned. In every case the returned adjEntry points to the targetnode.

Definition at line 260 of file BoyerMyrvoldPlanar.h.

◆ constActiveSuccessor()

node ogdf::BoyerMyrvoldPlanar::constActiveSuccessor	(	node	w,
		int	direction,
		int	v,
		int &	info
	)		const

inlineprotected

Walks upon external face in the given direction (without changing it) until an active vertex is reached.

Returns dynamical typeinformation info of that endvertex. But does not change the direction.

Definition at line 274 of file BoyerMyrvoldPlanar.h.

◆ constSuccessorOnExternalFace()

node ogdf::BoyerMyrvoldPlanar::constSuccessorOnExternalFace	(	node	v,
		int	direction
	)

inlineprotected

Returns the successornode on the external face in given direction.

direction is not changed.

Definition at line 241 of file BoyerMyrvoldPlanar.h.

◆ constSuccessorWithoutShortCircuit()

node ogdf::BoyerMyrvoldPlanar::constSuccessorWithoutShortCircuit	(	node	v,
		int	direction
	)		const

inlineprotected

Walks upon external face in direction avoiding short circuit edges.

direction is not changed.

Definition at line 250 of file BoyerMyrvoldPlanar.h.

◆ createShortCircuitEdge()

void ogdf::BoyerMyrvoldPlanar::createShortCircuitEdge	(	const node	v,
		const int	v_dir,
		const node	w,
		const int	w_dir
	)

protected

Creates a short circuit edge from node v with direction v_dir to node w with direction w_dir.

◆ embed()

bool ogdf::BoyerMyrvoldPlanar::embed ( )

protected

Starts the embedding phase, which embeds m_g node by node in descending DFI-order.

Returns true, if graph is planar, false otherwise.

◆ embedBackedges()

void ogdf::BoyerMyrvoldPlanar::embedBackedges	(	const node	v,
		const int	v_dir,
		const node	w,
		const int	w_dir
	)

protected

Links (and embeds iff m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node v with direction v_dir to node w with direction w_dir.

◆ externallyActive()

bool ogdf::BoyerMyrvoldPlanar::externallyActive	(	node	w,
		int	v
	)		const

inlineprotected

Checks whether real node w is externally active while embedding node with DFI v.

Definition at line 138 of file BoyerMyrvoldPlanar.h.

◆ flipBicomp()

void ogdf::BoyerMyrvoldPlanar::flipBicomp	(	int	c,
		int	marker,
		NodeArray< int > &	visited,
		bool	wholeGraph,
		bool	deleteFlipFlags
	)

Flips all nodes of the bicomp with unique, real, rootchild c as necessary.

Parameters

c	is the unique rootchild of the bicomp
marker	is the value which marks nodes as visited
visited	is the array containing visiting information
wholeGraph	Iff true, all bicomps of all connected components will be traversed
deleteFlipFlags	Iff true, the flipping flags will be deleted after flipping

◆ inactive()

bool ogdf::BoyerMyrvoldPlanar::inactive	(	node	w,
		int	v
	)

inlineprotected

Checks whether real node w is inactive while embedding node with DFI v.

Definition at line 151 of file BoyerMyrvoldPlanar.h.

◆ infoAboutNode()

int ogdf::BoyerMyrvoldPlanar::infoAboutNode	(	node	w,
		int	v
	)		const

inlineprotected

Checks all dynamic information about a node w while embedding node with DFI v.

Returns

This method returns the following values:

0 = inactive
1 = internallyActive
2 = pertinent and externallyActive
3 = externallyActive and not pertinent

Definition at line 171 of file BoyerMyrvoldPlanar.h.

◆ internallyActive()

bool ogdf::BoyerMyrvoldPlanar::internallyActive	(	node	w,
		int	v
	)		const

inlineprotected

Checks whether real node w is internally active while embedding node with DFI v.

Definition at line 132 of file BoyerMyrvoldPlanar.h.

◆ mergeBiconnectedComponent()

void ogdf::BoyerMyrvoldPlanar::mergeBiconnectedComponent ( ArrayBuffer< int > & stack )

protected

Merges the last two biconnected components saved in stack. Embeds them iff m_embeddingGrade != EmbeddingGrade::doNotEmbed.

◆ mergeUnprocessedNodes()

void ogdf::BoyerMyrvoldPlanar::mergeUnprocessedNodes ( )

protected

Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart.

◆ operator=()

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

Assignment operator is undefined!

◆ pertinent()

bool ogdf::BoyerMyrvoldPlanar::pertinent ( node w ) const

inlineprotected

Checks whether node w is pertinent. w has to be non-virtual.

Definition at line 126 of file BoyerMyrvoldPlanar.h.

◆ postProcessEmbedding()

void ogdf::BoyerMyrvoldPlanar::postProcessEmbedding ( )

protected

Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped.

In addition, embedding steps for parallel edges and self-loops are implemented.

◆ printNodeInfo()

void ogdf::BoyerMyrvoldPlanar::printNodeInfo ( node v )

inlineprotected

Prints informations about node v.

Definition at line 303 of file BoyerMyrvoldPlanar.h.

◆ seed()

void ogdf::BoyerMyrvoldPlanar::seed ( const std::minstd_rand rand )

inline

Seeds the random generator for performing a random DFS. If this method is never called the random generator will be seeded by a value extracted from the global random generator.

Definition at line 119 of file BoyerMyrvoldPlanar.h.

◆ start()

bool ogdf::BoyerMyrvoldPlanar::start ( )

Starts the embedding algorithm.

◆ successorOnExternalFace()

node ogdf::BoyerMyrvoldPlanar::successorOnExternalFace	(	node	w,
		int &	direction
	)		const

inlineprotected

Walks upon external face in the given direction starting at w.

If none of the bicomps has been flipped then CW = clockwise and CCW = counterclockwise holds. In general, the traversaldirection could have been changed due to flipped components. If this occurs, the traversaldirection is flipped.

Definition at line 203 of file BoyerMyrvoldPlanar.h.

◆ successorWithoutShortCircuit()

node ogdf::BoyerMyrvoldPlanar::successorWithoutShortCircuit	(	node	w,
		int &	direction
	)

inlineprotected

Walks upon external face in given direction avoiding short circuit edges.

Definition at line 221 of file BoyerMyrvoldPlanar.h.

◆ walkdown()

int ogdf::BoyerMyrvoldPlanar::walkdown	(	const int	i,
		const node	v,
		FindKuratowskis *	findKuratowskis
	)

protected

Walkdown: Embeds all backedges with DFI i as targetnode to node v.

Parameters

i	is the DFI of the current vertex to embed
v	is the virtual node being the root of the bicomp attached to `i`
findKuratowskis	collects information in order to extract Kuratowski Subdivisions later

Returns: 1, iff the embedding process found a stopping configuration

◆ walkup()

node ogdf::BoyerMyrvoldPlanar::walkup	(	const node	v,
		const node	w,
		const int	marker,
		const edge	back
	)

protected

Walkup: Builds the pertinent subgraph for the backedge back.

back is the backedge between nodes v and w. v is the current node to embed. All visited nodes are marked with value marker. The Function returns the last traversed node.

◆ wNodesExist()

bool ogdf::BoyerMyrvoldPlanar::wNodesExist	(	node	root,
		node	stopx,
		node	stopy
	)		const

inlineprotected

Checks, if one ore more wNodes exist between the two stopping vertices stopx and stopy.

The node root is root of the bicomp containing the stopping vertices

Definition at line 281 of file BoyerMyrvoldPlanar.h.

Friends And Related Function Documentation

◆ boyer_myrvold::BoyerMyrvoldInit

friend class boyer_myrvold::BoyerMyrvoldInit

friend

Definition at line 68 of file BoyerMyrvoldPlanar.h.

◆ BoyerMyrvold

friend class BoyerMyrvold

friend

Definition at line 67 of file BoyerMyrvoldPlanar.h.

◆ ExtractKuratowskis

friend class ExtractKuratowskis

friend

Definition at line 70 of file BoyerMyrvoldPlanar.h.

◆ FindKuratowskis

friend class FindKuratowskis

friend

Definition at line 69 of file BoyerMyrvoldPlanar.h.

Member Data Documentation

◆ DirectionCCW

const static int ogdf::BoyerMyrvoldPlanar::DirectionCCW

static

Direction for counterclockwise traversal.

Definition at line 74 of file BoyerMyrvoldPlanar.h.

◆ DirectionCW

const static int ogdf::BoyerMyrvoldPlanar::DirectionCW

static

Direction for clockwise traversal.

Definition at line 77 of file BoyerMyrvoldPlanar.h.

◆ m_adjParent

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_adjParent

protected

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

Definition at line 407 of file BoyerMyrvoldPlanar.h.

◆ m_avoidE2Minors

const bool ogdf::BoyerMyrvoldPlanar::m_avoidE2Minors

protected

Definition at line 369 of file BoyerMyrvoldPlanar.h.

◆ m_backedgeFlags

NodeArray<SListPure<adjEntry> > ogdf::BoyerMyrvoldPlanar::m_backedgeFlags

protected

Holds information, if node is the source of a backedge.

This information refers to the adjEntries on the targetnode and is used during the walkdown

Definition at line 468 of file BoyerMyrvoldPlanar.h.

◆ m_beforeSCE

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_beforeSCE[2]

protected

Links for short circuit edges.

If short circuit edges are introduced, the former adjEntries to the neighbors have to be saved here for embedding and merging purposes. If there is no short circuit edge, this adjEntry is nullptr.

Definition at line 404 of file BoyerMyrvoldPlanar.h.

◆ m_bundles

const bool ogdf::BoyerMyrvoldPlanar::m_bundles

protected

Definition at line 365 of file BoyerMyrvoldPlanar.h.

◆ m_dfi

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_dfi

protected

The one and only DFI-NodeArray.

Definition at line 389 of file BoyerMyrvoldPlanar.h.

◆ m_edgeCosts

const EdgeArray<int>* ogdf::BoyerMyrvoldPlanar::m_edgeCosts

protected

Definition at line 370 of file BoyerMyrvoldPlanar.h.

◆ m_edgeType

EdgeArray<BoyerMyrvoldEdgeType> ogdf::BoyerMyrvoldPlanar::m_edgeType

protected

Contains the type of each edge.

Definition at line 415 of file BoyerMyrvoldPlanar.h.

◆ m_embeddingGrade

const int ogdf::BoyerMyrvoldPlanar::m_embeddingGrade

protected

Definition at line 366 of file BoyerMyrvoldPlanar.h.

◆ m_extractSubgraph

bool ogdf::BoyerMyrvoldPlanar::m_extractSubgraph = true

protected

Flag for extracting a planar subgraph instead of testing for planarity.

Definition at line 375 of file BoyerMyrvoldPlanar.h.

◆ m_flipped

NodeArray<bool> ogdf::BoyerMyrvoldPlanar::m_flipped

protected

Iff true, the node is the root of a bicomp which has to be flipped.

The DFS-child of every bicomp root vertex is unique. if a bicomp is flipped, this DFS-child is marked to check whether the bicomp has to be flipped or not.

Definition at line 462 of file BoyerMyrvoldPlanar.h.

◆ m_flippedNodes

int ogdf::BoyerMyrvoldPlanar::m_flippedNodes

protected

The whole number of bicomps, which have to be flipped.

Definition at line 378 of file BoyerMyrvoldPlanar.h.

◆ m_g

Graph& ogdf::BoyerMyrvoldPlanar::m_g

protected

Input graph, which can be altered.

Definition at line 361 of file BoyerMyrvoldPlanar.h.

◆ m_highestSubtreeDFI

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_highestSubtreeDFI

protected

The highest DFI in a subtree with node as root.

Definition at line 421 of file BoyerMyrvoldPlanar.h.

◆ m_leastAncestor

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_leastAncestor

protected

The DFI of the least ancestor node over all backedges.

If no backedge exists, the least ancestor is the DFI of that node itself

Definition at line 412 of file BoyerMyrvoldPlanar.h.

◆ m_limitStructures

const bool ogdf::BoyerMyrvoldPlanar::m_limitStructures

protected

Definition at line 367 of file BoyerMyrvoldPlanar.h.

◆ m_link

NodeArray<adjEntry> ogdf::BoyerMyrvoldPlanar::m_link[2]

protected

Links to opposite adjacency entries on external face in clockwise resp. ccw order.

m_link[0]=CCW, m_link[1]=CW

Definition at line 397 of file BoyerMyrvoldPlanar.h.

◆ m_lowPoint

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_lowPoint

protected

The lowpoint of each node.

Definition at line 418 of file BoyerMyrvoldPlanar.h.

◆ m_nodeFromDFI

Array<node> ogdf::BoyerMyrvoldPlanar::m_nodeFromDFI

protected

Returns appropriate node from given DFI.

Definition at line 392 of file BoyerMyrvoldPlanar.h.

◆ m_numUnembeddedBackedgesInBicomp

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_numUnembeddedBackedgesInBicomp

protected

Stores for each (virtual) bicomp root how many backedges to its bicomp still have to be embedded.

The value is set during the walkup, and it is used and decreased while embedding backedges during the walkdown.

Definition at line 455 of file BoyerMyrvoldPlanar.h.

◆ m_output

SListPure<KuratowskiStructure>& ogdf::BoyerMyrvoldPlanar::m_output

protected

Data structure for the Kuratowski subdivisions, which will be returned.

Definition at line 474 of file BoyerMyrvoldPlanar.h.

◆ m_pertinentRoots

NodeArray<SListPure<node> > ogdf::BoyerMyrvoldPlanar::m_pertinentRoots

protected

List of virtual bicomp roots, that are pertinent to the current embedded node.

Definition at line 471 of file BoyerMyrvoldPlanar.h.

◆ m_pNodeInParent

NodeArray<ListIterator<node> > ogdf::BoyerMyrvoldPlanar::m_pNodeInParent

protected

Pointer to node contained in the DFSChildList of his parent, if exists.

If node isn't in list or list doesn't exist, the pointer is set to nullptr.

Definition at line 431 of file BoyerMyrvoldPlanar.h.

◆ m_pointsToRoot

EdgeArray<node> ogdf::BoyerMyrvoldPlanar::m_pointsToRoot

protected

Identifies the rootnode of the child bicomp the given backedge points to.

Definition at line 441 of file BoyerMyrvoldPlanar.h.

◆ m_rand

std::minstd_rand ogdf::BoyerMyrvoldPlanar::m_rand

protected

Definition at line 371 of file BoyerMyrvoldPlanar.h.

◆ m_randomness

const double ogdf::BoyerMyrvoldPlanar::m_randomness

protected

Definition at line 368 of file BoyerMyrvoldPlanar.h.

◆ m_realVertex

NodeArray<node> ogdf::BoyerMyrvoldPlanar::m_realVertex

protected

Link to non-virtual vertex of a virtual Vertex.

A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex

Definition at line 386 of file BoyerMyrvoldPlanar.h.

◆ m_separatedDFSChildList

NodeArray<ListPure<node> > ogdf::BoyerMyrvoldPlanar::m_separatedDFSChildList

protected

A list to all separated DFS-children of node.

The list is sorted by lowpoint values (in linear time)

Definition at line 426 of file BoyerMyrvoldPlanar.h.

◆ m_visited

NodeArray<int> ogdf::BoyerMyrvoldPlanar::m_visited

protected

This Array keeps track of all vertices that are visited by current walkup.

Definition at line 438 of file BoyerMyrvoldPlanar.h.

◆ m_visitedWithBackedge

NodeArray<edge> ogdf::BoyerMyrvoldPlanar::m_visitedWithBackedge

protected

Stores for each (real) non-root vertex v with which backedge it was visited during the walkup.

This is done to later identify the root vertex of the bicomp v belongs to.

Definition at line 448 of file BoyerMyrvoldPlanar.h.

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

include/ogdf/planarity/boyer_myrvold/BoyerMyrvoldPlanar.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Enumeration Documentation

◆ EmbeddingGrade

Constructor & Destructor Documentation

◆ BoyerMyrvoldPlanar() [1/2]

◆ BoyerMyrvoldPlanar() [2/2]

Member Function Documentation

◆ activeSuccessor()

◆ beforeShortCircuitEdge()

◆ constActiveSuccessor()

◆ constSuccessorOnExternalFace()

◆ constSuccessorWithoutShortCircuit()

◆ createShortCircuitEdge()

◆ embed()

◆ embedBackedges()

◆ externallyActive()

◆ flipBicomp()

◆ inactive()

◆ infoAboutNode()

◆ internallyActive()

◆ mergeBiconnectedComponent()

◆ mergeUnprocessedNodes()

◆ operator=()

◆ pertinent()

◆ postProcessEmbedding()

◆ printNodeInfo()

◆ seed()

◆ start()

◆ successorOnExternalFace()

◆ successorWithoutShortCircuit()

◆ walkdown()

◆ walkup()

◆ wNodesExist()

Friends And Related Function Documentation

◆ boyer_myrvold::BoyerMyrvoldInit

◆ BoyerMyrvold

◆ ExtractKuratowskis

◆ FindKuratowskis

Member Data Documentation

◆ DirectionCCW

◆ DirectionCW

◆ m_adjParent

◆ m_avoidE2Minors

◆ m_backedgeFlags

◆ m_beforeSCE

◆ m_bundles

◆ m_dfi

◆ m_edgeCosts

◆ m_edgeType

◆ m_embeddingGrade

◆ m_extractSubgraph

◆ m_flipped

◆ m_flippedNodes

◆ m_g

◆ m_highestSubtreeDFI

◆ m_leastAncestor

◆ m_limitStructures

◆ m_link

◆ m_lowPoint

◆ m_nodeFromDFI

◆ m_numUnembeddedBackedgesInBicomp

◆ m_output

◆ m_pertinentRoots

◆ m_pNodeInParent

◆ m_pointsToRoot

◆ m_rand

◆ m_randomness

◆ m_realVertex

◆ m_separatedDFSChildList

◆ m_visited

◆ m_visitedWithBackedge

Open
Graph Drawing
Framework