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 class	CompType { bond , polygon , triconnected }
	type of split-components / triconnected components More...

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

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

	Triconnectivity (const Triconnectivity &)=delete

	~Triconnectivity ()

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

Public Attributes
Array< CompStruct >	m_component
	array of components

int	m_numComp
	number of components

GraphCopySimple *	m_pGC
	copy of G containing also virtual edges

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

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

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

bool	checkSepPair (edge eVirt)

void	delHigh (edge e)

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

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

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

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

CompStruct &	newComp ()
	create a new empty component

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

void	pathFinder (const Graph &G, node v)

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

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

void	printOs (edge e)
	debugging stuff

void	printStacks ()

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

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

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

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

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

NodeArray< int >	m_DEGREE
	degree of v

ArrayBuffer< edge >	m_ESTACK
	stack of currently active edges

NodeArray< node >	m_FATHER
	father of v in palm tree

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

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

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

NodeArray< int >	m_LOWPT1

NodeArray< int >	m_LOWPT2

NodeArray< int >	m_ND
	number of descendants in palm tree

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

bool	m_newPath
	true iff we start a new path

Array< node >	m_NODEAT
	node with number i

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

int	m_numCount
	counter for dfs-traversal

EdgeArray< bool >	m_START
	edge starts a path

node	m_start
	start node of dfs traversal

int	m_top

NodeArray< edge >	m_TREE_ARC
	tree arc entering v

int *	m_TSTACK_a

int *	m_TSTACK_b

int *	m_TSTACK_h
	stack of triples

EdgeArray< EdgeType >	m_TYPE
	type of edge e

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 class ogdf::Triconnectivity::CompType

strong

type of split-components / triconnected components

Enumerator
bond
polygon
triconnected

Definition at line 68 of file Triconnectivity.h.

◆ EdgeType

enum class ogdf::Triconnectivity::EdgeType

strongprivate

type of edges with respect to palm tree

Enumerator
unseen
tree
frond
removed

Definition at line 135 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 163 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 161 of file Triconnectivity.h.

◆ newComp() [1/2]

CompStruct & ogdf::Triconnectivity::newComp ( )

inlineprivate

create a new empty component

Definition at line 125 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 128 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 122 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 112 of file Triconnectivity.h.

◆ TSTACK_pushEOS()

void ogdf::Triconnectivity::TSTACK_pushEOS ( )

inlineprivate

push end-of-stack marker on TSTACK

Definition at line 119 of file Triconnectivity.h.

Member Data Documentation

◆ m_A

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

private

adjacency list of v

Definition at line 179 of file Triconnectivity.h.

◆ m_component

Array<CompStruct> ogdf::Triconnectivity::m_component

array of components

Definition at line 89 of file Triconnectivity.h.

◆ m_DEGREE

NodeArray<int> ogdf::Triconnectivity::m_DEGREE

private

degree of v

Definition at line 175 of file Triconnectivity.h.

◆ m_ESTACK

ArrayBuffer<edge> ogdf::Triconnectivity::m_ESTACK

private

stack of currently active edges

Definition at line 186 of file Triconnectivity.h.

◆ m_FATHER

NodeArray<node> ogdf::Triconnectivity::m_FATHER

private

father of v in palm tree

Definition at line 177 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 183 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 184 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 185 of file Triconnectivity.h.

◆ m_LOWPT1

NodeArray<int> ogdf::Triconnectivity::m_LOWPT1

private

Definition at line 172 of file Triconnectivity.h.

◆ m_LOWPT2

NodeArray<int> ogdf::Triconnectivity::m_LOWPT2

private

Definition at line 173 of file Triconnectivity.h.

◆ m_ND

NodeArray<int> ogdf::Triconnectivity::m_ND

private

number of descendants in palm tree

Definition at line 174 of file Triconnectivity.h.

◆ m_NEWNUM

NodeArray<int> ogdf::Triconnectivity::m_NEWNUM

private

(second) dfs-number of v

Definition at line 180 of file Triconnectivity.h.

◆ m_newPath

bool ogdf::Triconnectivity::m_newPath

private

true iff we start a new path

Definition at line 190 of file Triconnectivity.h.

◆ m_NODEAT

Array<node> ogdf::Triconnectivity::m_NODEAT

private

node with number i

Definition at line 176 of file Triconnectivity.h.

◆ m_NUMBER

NodeArray<int> ogdf::Triconnectivity::m_NUMBER

private

(first) dfs-number of v

Definition at line 171 of file Triconnectivity.h.

◆ m_numComp

int ogdf::Triconnectivity::m_numComp

number of components

Definition at line 91 of file Triconnectivity.h.

◆ m_numCount

int ogdf::Triconnectivity::m_numCount

private

counter for dfs-traversal

Definition at line 189 of file Triconnectivity.h.

◆ m_pGC

GraphCopySimple* ogdf::Triconnectivity::m_pGC

copy of G containing also virtual edges

Definition at line 87 of file Triconnectivity.h.

◆ m_START

EdgeArray<bool> ogdf::Triconnectivity::m_START

private

edge starts a path

Definition at line 181 of file Triconnectivity.h.

◆ m_start

node ogdf::Triconnectivity::m_start

private

start node of dfs traversal

Definition at line 188 of file Triconnectivity.h.

◆ m_top

int ogdf::Triconnectivity::m_top

private

Definition at line 109 of file Triconnectivity.h.

◆ m_TREE_ARC

NodeArray<edge> ogdf::Triconnectivity::m_TREE_ARC

private

tree arc entering v

Definition at line 182 of file Triconnectivity.h.

◆ m_TSTACK_a

int * ogdf::Triconnectivity::m_TSTACK_a

private

Definition at line 108 of file Triconnectivity.h.

◆ m_TSTACK_b

int * ogdf::Triconnectivity::m_TSTACK_b

private

Definition at line 108 of file Triconnectivity.h.

◆ m_TSTACK_h

int* ogdf::Triconnectivity::m_TSTACK_h

private

stack of triples

Definition at line 108 of file Triconnectivity.h.

◆ m_TYPE

EdgeArray<EdgeType> ogdf::Triconnectivity::m_TYPE

private

type of edge e

Definition at line 178 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