realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph More...

#include <ogdf/graphalg/Triconnectivity.h>

Classes
struct	CompStruct
	representation of a component More...

Public Types
enum	CompType { CompType::bond, CompType::polygon, CompType::triconnected }
	type of split-components / triconnected components More...

Public Member Functions
	Triconnectivity (const Graph &G)
	Divides G into triconnected components. More...

	Triconnectivity (const Graph &G, bool &isTric, node &s1, node &s2)
	Tests G for triconnectivity. More...

	Triconnectivity (const Triconnectivity &)=delete

	~Triconnectivity ()

bool	checkComp ()
	Checks if computed triconnected componets are correct. More...

Public Attributes
Array< CompStruct >	m_component
	array of components More...

int	m_numComp
	number of components More...

GraphCopySimple *	m_pGC
	copy of G containing also virtual edges More...

Private Types
enum	EdgeType { EdgeType::unseen, EdgeType::tree, EdgeType::frond, EdgeType::removed }
	type of edges with respect to palm tree More...

Private Member Functions
void	assembleTriconnectedComponents ()
	merges split-components into triconnected components More...

void	buildAcceptableAdjStruct (const Graph &G)
	constructs ordered adjaceny lists More...

bool	checkSepPair (edge eVirt)

void	delHigh (edge e)

void	DFS1 (const Graph &G, node v, node u)
	first dfs traversal More...

void	DFS1 (const Graph &G, node v, node u, node &s1)
	special version for triconnectivity tes More...

void	DFS2 (const Graph &G)
	the second dfs traversal More...

int	high (node v)
	returns high(v) value More...

CompStruct &	newComp ()
	create a new empty component More...

CompStruct &	newComp (CompType t)
	create a new empty component of type t More...

void	pathFinder (const Graph &G, node v)

void	pathSearch (const Graph &G, node v)
	finding of split components More...

bool	pathSearch (const Graph &G, node v, node &s1, node &s2)

void	printOs (edge e)
	debugging stuff More...

void	printStacks ()

void	splitMultiEdges ()
	splits bundles of multi-edges into bonds and creates a new virtual edge in GC. More...

bool	TSTACK_notEOS ()
	returns true iff end-of-stack marker is not on top of TSTACK More...

void	TSTACK_push (int h, int a, int b)
	push a triple on TSTACK More...

void	TSTACK_pushEOS ()
	push end-of-stack marker on TSTACK More...

Private Attributes
NodeArray< List< edge > >	m_A
	adjacency list of v More...

NodeArray< int >	m_DEGREE
	degree of v More...

ArrayBuffer< edge >	m_ESTACK
	stack of currently active edges More...

NodeArray< node >	m_FATHER
	father of v in palm tree More...

NodeArray< List< int > >	m_HIGHPT
	list of fronds entering v in the order they are visited More...

EdgeArray< ListIterator< edge > >	m_IN_ADJ
	pointer to element in adjacency list containing e More...

EdgeArray< ListIterator< int > >	m_IN_HIGH
	pointer to element in HIGHPT list containing e More...

NodeArray< int >	m_LOWPT1

NodeArray< int >	m_LOWPT2

NodeArray< int >	m_ND
	number of descendants in palm tree More...

NodeArray< int >	m_NEWNUM
	(second) dfs-number of v More...

bool	m_newPath
	true iff we start a new path More...

Array< node >	m_NODEAT
	node with number i More...

NodeArray< int >	m_NUMBER
	(first) dfs-number of v More...

int	m_numCount
	counter for dfs-traversal More...

EdgeArray< bool >	m_START
	edge starts a path More...

node	m_start
	start node of dfs traversal More...

int	m_top

NodeArray< edge >	m_TREE_ARC
	tree arc entering v More...

int *	m_TSTACK_a

int *	m_TSTACK_b

int *	m_TSTACK_h
	stack of triples More...

EdgeArray< EdgeType >	m_TYPE
	type of edge e More...

Detailed Description

realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph

Definition at line 46 of file Triconnectivity.h.

Member Enumeration Documentation

◆ CompType

enum ogdf::Triconnectivity::CompType

strong

type of split-components / triconnected components

Enumerator
bond
polygon
triconnected

Definition at line 69 of file Triconnectivity.h.

◆ EdgeType

enum ogdf::Triconnectivity::EdgeType

strongprivate

type of edges with respect to palm tree

Enumerator
unseen
tree
frond
removed

Definition at line 142 of file Triconnectivity.h.

Constructor & Destructor Documentation

◆ Triconnectivity() [1/3]

ogdf::Triconnectivity::Triconnectivity ( const Graph & G )

explicit

Divides G into triconnected components.

Parameters

G graph

◆ Triconnectivity() [2/3]

ogdf::Triconnectivity::Triconnectivity	(	const Graph &	G,
		bool &	isTric,
		node &	s1,
		node &	s2
	)

Tests G for triconnectivity.

Parameters

G	graph
isTric	true if G is triconnected, false otherwise.
s1	first vertex of separation pair if G is biconnected, cut vertex of G if G is not biconnected, nullptr if G is not connected.
s2	second vertex of separation pair if G is biconnected, nullptr otherwise.

◆ Triconnectivity() [3/3]

ogdf::Triconnectivity::Triconnectivity ( const Triconnectivity & )

delete

◆ ~Triconnectivity()

ogdf::Triconnectivity::~Triconnectivity ( )

Member Function Documentation

◆ assembleTriconnectedComponents()

void ogdf::Triconnectivity::assembleTriconnectedComponents ( )

private

merges split-components into triconnected components

◆ buildAcceptableAdjStruct()

void ogdf::Triconnectivity::buildAcceptableAdjStruct ( const Graph & G )

private

constructs ordered adjaceny lists

◆ checkComp()

bool ogdf::Triconnectivity::checkComp ( )

Checks if computed triconnected componets are correct.

Precondition: checkComp() assumes that the graph is simple!

◆ checkSepPair()

bool ogdf::Triconnectivity::checkSepPair ( edge eVirt )

private

◆ delHigh()

void ogdf::Triconnectivity::delHigh ( edge e )

inlineprivate

Definition at line 172 of file Triconnectivity.h.

◆ DFS1() [1/2]

void ogdf::Triconnectivity::DFS1	(	const Graph &	G,
		node	v,
		node	u
	)

private

first dfs traversal

◆ DFS1() [2/2]

void ogdf::Triconnectivity::DFS1	(	const Graph &	G,
		node	v,
		node	u,
		node &	s1
	)

private

special version for triconnectivity tes

◆ DFS2()

void ogdf::Triconnectivity::DFS2 ( const Graph & G )

private

the second dfs traversal

◆ high()

int ogdf::Triconnectivity::high ( node v )

inlineprivate

returns high(v) value

Definition at line 168 of file Triconnectivity.h.

◆ newComp() [1/2]

CompStruct& ogdf::Triconnectivity::newComp ( )

inlineprivate

create a new empty component

Definition at line 130 of file Triconnectivity.h.

◆ newComp() [2/2]

CompStruct& ogdf::Triconnectivity::newComp ( CompType t )

inlineprivate

create a new empty component of type t

Definition at line 135 of file Triconnectivity.h.

◆ pathFinder()

void ogdf::Triconnectivity::pathFinder	(	const Graph &	G,
		node	v
	)

private

◆ pathSearch() [1/2]

void ogdf::Triconnectivity::pathSearch	(	const Graph &	G,
		node	v
	)

private

finding of split components

◆ pathSearch() [2/2]

bool ogdf::Triconnectivity::pathSearch	(	const Graph &	G,
		node	v,
		node &	s1,
		node &	s2
	)

private

◆ printOs()

void ogdf::Triconnectivity::printOs ( edge e )

private

debugging stuff

◆ printStacks()

void ogdf::Triconnectivity::printStacks ( )

private

◆ splitMultiEdges()

void ogdf::Triconnectivity::splitMultiEdges ( )

private

splits bundles of multi-edges into bonds and creates a new virtual edge in GC.

◆ TSTACK_notEOS()

bool ogdf::Triconnectivity::TSTACK_notEOS ( )

inlineprivate

returns true iff end-of-stack marker is not on top of TSTACK

Definition at line 125 of file Triconnectivity.h.

◆ TSTACK_push()

void ogdf::Triconnectivity::TSTACK_push	(	int	h,
		int	a,
		int	b
	)

inlineprivate

push a triple on TSTACK

Definition at line 113 of file Triconnectivity.h.

◆ TSTACK_pushEOS()

void ogdf::Triconnectivity::TSTACK_pushEOS ( )

inlineprivate

push end-of-stack marker on TSTACK

Definition at line 120 of file Triconnectivity.h.

Member Data Documentation

◆ m_A

NodeArray<List<edge> > ogdf::Triconnectivity::m_A

private

adjacency list of v

Definition at line 188 of file Triconnectivity.h.

◆ m_component

Array<CompStruct> ogdf::Triconnectivity::m_component

array of components

Definition at line 90 of file Triconnectivity.h.

◆ m_DEGREE

NodeArray<int> ogdf::Triconnectivity::m_DEGREE

private

degree of v

Definition at line 184 of file Triconnectivity.h.

◆ m_ESTACK

ArrayBuffer<edge> ogdf::Triconnectivity::m_ESTACK

private

stack of currently active edges

Definition at line 195 of file Triconnectivity.h.

◆ m_FATHER

NodeArray<node> ogdf::Triconnectivity::m_FATHER

private

father of v in palm tree

Definition at line 186 of file Triconnectivity.h.

◆ m_HIGHPT

NodeArray<List<int> > ogdf::Triconnectivity::m_HIGHPT

private

list of fronds entering v in the order they are visited

Definition at line 192 of file Triconnectivity.h.

◆ m_IN_ADJ

EdgeArray<ListIterator<edge> > ogdf::Triconnectivity::m_IN_ADJ

private

pointer to element in adjacency list containing e

Definition at line 193 of file Triconnectivity.h.

◆ m_IN_HIGH

EdgeArray<ListIterator<int> > ogdf::Triconnectivity::m_IN_HIGH

private

pointer to element in HIGHPT list containing e

Definition at line 194 of file Triconnectivity.h.

◆ m_LOWPT1

NodeArray<int> ogdf::Triconnectivity::m_LOWPT1

private

Definition at line 181 of file Triconnectivity.h.

◆ m_LOWPT2

NodeArray<int> ogdf::Triconnectivity::m_LOWPT2

private

Definition at line 182 of file Triconnectivity.h.

◆ m_ND

NodeArray<int> ogdf::Triconnectivity::m_ND

private

number of descendants in palm tree

Definition at line 183 of file Triconnectivity.h.

◆ m_NEWNUM

NodeArray<int> ogdf::Triconnectivity::m_NEWNUM

private

(second) dfs-number of v

Definition at line 189 of file Triconnectivity.h.

◆ m_newPath

bool ogdf::Triconnectivity::m_newPath

private

true iff we start a new path

Definition at line 199 of file Triconnectivity.h.

◆ m_NODEAT

Array<node> ogdf::Triconnectivity::m_NODEAT

private

node with number i

Definition at line 185 of file Triconnectivity.h.

◆ m_NUMBER

NodeArray<int> ogdf::Triconnectivity::m_NUMBER

private

(first) dfs-number of v

Definition at line 180 of file Triconnectivity.h.

◆ m_numComp

int ogdf::Triconnectivity::m_numComp

number of components

Definition at line 92 of file Triconnectivity.h.

◆ m_numCount

int ogdf::Triconnectivity::m_numCount

private

counter for dfs-traversal

Definition at line 198 of file Triconnectivity.h.

◆ m_pGC

GraphCopySimple* ogdf::Triconnectivity::m_pGC

copy of G containing also virtual edges

Definition at line 88 of file Triconnectivity.h.

◆ m_START

EdgeArray<bool> ogdf::Triconnectivity::m_START

private

edge starts a path

Definition at line 190 of file Triconnectivity.h.

◆ m_start

node ogdf::Triconnectivity::m_start

private

start node of dfs traversal

Definition at line 197 of file Triconnectivity.h.

◆ m_top

int ogdf::Triconnectivity::m_top

private

Definition at line 110 of file Triconnectivity.h.

◆ m_TREE_ARC

NodeArray<edge> ogdf::Triconnectivity::m_TREE_ARC

private

tree arc entering v

Definition at line 191 of file Triconnectivity.h.

◆ m_TSTACK_a

int * ogdf::Triconnectivity::m_TSTACK_a

private

Definition at line 109 of file Triconnectivity.h.

◆ m_TSTACK_b

int * ogdf::Triconnectivity::m_TSTACK_b

private

Definition at line 109 of file Triconnectivity.h.

◆ m_TSTACK_h

int* ogdf::Triconnectivity::m_TSTACK_h

private

stack of triples

Definition at line 109 of file Triconnectivity.h.

◆ m_TYPE

EdgeArray<EdgeType> ogdf::Triconnectivity::m_TYPE

private

type of edge e

Definition at line 187 of file Triconnectivity.h.

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

include/ogdf/graphalg/Triconnectivity.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ CompType

◆ EdgeType

Constructor & Destructor Documentation

◆ Triconnectivity() [1/3]

◆ Triconnectivity() [2/3]

◆ Triconnectivity() [3/3]

◆ ~Triconnectivity()

Member Function Documentation

◆ assembleTriconnectedComponents()

◆ buildAcceptableAdjStruct()

◆ checkComp()

◆ checkSepPair()

◆ delHigh()

◆ DFS1() [1/2]

◆ DFS1() [2/2]

◆ DFS2()

◆ high()

◆ newComp() [1/2]

◆ newComp() [2/2]

◆ pathFinder()

◆ pathSearch() [1/2]

◆ pathSearch() [2/2]

◆ printOs()

◆ printStacks()

◆ splitMultiEdges()

◆ TSTACK_notEOS()

◆ TSTACK_push()

◆ TSTACK_pushEOS()

Member Data Documentation

◆ m_A

◆ m_component

◆ m_DEGREE

◆ m_ESTACK

◆ m_FATHER

◆ m_HIGHPT

◆ m_IN_ADJ

◆ m_IN_HIGH

◆ m_LOWPT1

◆ m_LOWPT2

◆ m_ND

◆ m_NEWNUM

◆ m_newPath

◆ m_NODEAT

◆ m_NUMBER

◆ m_numComp

◆ m_numCount

◆ m_pGC

◆ m_START

◆ m_start

◆ m_top

◆ m_TREE_ARC

◆ m_TSTACK_a

◆ m_TSTACK_b

◆ m_TSTACK_h

◆ m_TYPE

Open
Graph Drawing
Framework