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 (Graph &G, bool modifyG=false)
	Divides G into triconnected components.

	~Triconnectivity ()

bool	checkComp () const
	Checks if computed triconnected components are correct.

Public Attributes
Array< CompStruct >	m_component
	array of components

int	m_numComp
	number of components

Graph *	m_pG
	modifiable copy of G also containing virtual edges

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

Private Member Functions
	Triconnectivity (Graph *G)

bool	afterRecursivePathSearch (const node v, const int vnum, const int outv, const edge e, const node w, const int wnum, node &s1, node &s2)
	pathSearch() helper for the fail-fast version

void	afterRecursivePathSearch (const node v, const int vnum, const int outv, const ListIterator< edge > it, const edge e, const node w, int wnum)
	pathSearch() helper for the non-fail-fast version

void	assembleTriconnectedComponents ()
	merges split-components into triconnected components

void	buildAcceptableAdjStruct ()
	constructs ordered adjaceny lists

bool	checkSepPair (edge eVirt) const

void	clearStructures ()

void	delHigh (edge e)

void	DFS1 (node v, node u)
	first dfs traversal

void	DFS1 (node v, node u, node &s1)
	special version for triconnectivity test

void	DFS2 ()
	the second dfs traversal

template<typename T >
T	GCoriginal (T n) const
	returns `m_pG.original(n)` if m_pG is a GraphCopySimple, otherwise `n` itself

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 (node v)

bool	pathSearch (node init_v, bool fail_fast, node &s1, node &s2)
	finding of split components

void	printOs (edge e) const
	debugging stuff

void	printStacks () const

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

bool	m_deleteGraph
	whether the Graph(Copy) was created by us and should thus be deleted in the destructor

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 50 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 86 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 158 of file Triconnectivity.h.

Constructor & Destructor Documentation

◆ Triconnectivity() [1/5]

ogdf::Triconnectivity::Triconnectivity ( Graph * G )

explicitprivate

◆ Triconnectivity() [2/5]

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

inlineexplicit

Divides G into triconnected components.

Parameters

G graph

Definition at line 58 of file Triconnectivity.h.

◆ Triconnectivity() [3/5]

ogdf::Triconnectivity::Triconnectivity	(	Graph &	G,
		bool	modifyG = `false`
	)

inlineexplicit

Divides G into triconnected components.

Parameters

G	graph
modifyG	adds virtual edges directly to G if true, otherwise makes a copy first

Definition at line 67 of file Triconnectivity.h.

◆ Triconnectivity() [4/5]

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() [5/5]

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

delete

◆ ~Triconnectivity()

ogdf::Triconnectivity::~Triconnectivity ( )

Member Function Documentation

◆ afterRecursivePathSearch() [1/2]

bool ogdf::Triconnectivity::afterRecursivePathSearch	(	const node	v,
		const int	vnum,
		const int	outv,
		const edge	e,
		const node	w,
		const int	wnum,
		node &	s1,
		node &	s2
	)

private

pathSearch() helper for the fail-fast version

◆ afterRecursivePathSearch() [2/2]

void ogdf::Triconnectivity::afterRecursivePathSearch	(	const node	v,
		const int	vnum,
		const int	outv,
		const ListIterator< edge >	it,
		const edge	e,
		const node	w,
		int	wnum
	)

private

pathSearch() helper for the non-fail-fast version

◆ assembleTriconnectedComponents()

void ogdf::Triconnectivity::assembleTriconnectedComponents ( )

private

merges split-components into triconnected components

◆ buildAcceptableAdjStruct()

void ogdf::Triconnectivity::buildAcceptableAdjStruct ( )

private

constructs ordered adjaceny lists

◆ checkComp()

bool ogdf::Triconnectivity::checkComp ( ) const

Checks if computed triconnected components are correct.

Precondition: checkComp() assumes that the graph is simple

◆ checkSepPair()

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

private

◆ clearStructures()

void ogdf::Triconnectivity::clearStructures ( )

private

◆ delHigh()

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

inlineprivate

Definition at line 194 of file Triconnectivity.h.

◆ DFS1() [1/2]

void ogdf::Triconnectivity::DFS1	(	node	v,
		node	u
	)

private

first dfs traversal

◆ DFS1() [2/2]

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

private

special version for triconnectivity test

◆ DFS2()

void ogdf::Triconnectivity::DFS2 ( )

private

the second dfs traversal

◆ GCoriginal()

template<typename T >

T ogdf::Triconnectivity::GCoriginal ( T n ) const

inlineprivate

returns m_pG.original(n) if m_pG is a GraphCopySimple, otherwise n itself

Definition at line 204 of file Triconnectivity.h.

◆ high()

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

inlineprivate

returns high(v) value

Definition at line 192 of file Triconnectivity.h.

◆ newComp() [1/2]

CompStruct & ogdf::Triconnectivity::newComp ( )

inlineprivate

create a new empty component

Definition at line 148 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 151 of file Triconnectivity.h.

◆ pathFinder()

void ogdf::Triconnectivity::pathFinder ( node v )

private

◆ pathSearch()

bool ogdf::Triconnectivity::pathSearch	(	node	init_v,
		bool	fail_fast,
		node &	s1,
		node &	s2
	)

private

finding of split components

If fail_fast is true, the search will be aborted after finding the first split pair, which will be assigned to s1 and s2. Otherwise, s1 and s2 are unused.

◆ printOs()

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

private

debugging stuff

◆ printStacks()

void ogdf::Triconnectivity::printStacks ( ) const

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 145 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 135 of file Triconnectivity.h.

◆ TSTACK_pushEOS()

void ogdf::Triconnectivity::TSTACK_pushEOS ( )

inlineprivate

push end-of-stack marker on TSTACK

Definition at line 142 of file Triconnectivity.h.

Member Data Documentation

◆ m_A

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

private

adjacency list of v

Definition at line 221 of file Triconnectivity.h.

◆ m_component

Array<CompStruct> ogdf::Triconnectivity::m_component

array of components

Definition at line 107 of file Triconnectivity.h.

◆ m_DEGREE

NodeArray<int> ogdf::Triconnectivity::m_DEGREE

private

degree of v

Definition at line 217 of file Triconnectivity.h.

◆ m_deleteGraph

bool ogdf::Triconnectivity::m_deleteGraph

private

whether the Graph(Copy) was created by us and should thus be deleted in the destructor

Definition at line 233 of file Triconnectivity.h.

◆ m_ESTACK

ArrayBuffer<edge> ogdf::Triconnectivity::m_ESTACK

private

stack of currently active edges

Definition at line 228 of file Triconnectivity.h.

◆ m_FATHER

NodeArray<node> ogdf::Triconnectivity::m_FATHER

private

father of v in palm tree

Definition at line 219 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 225 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 226 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 227 of file Triconnectivity.h.

◆ m_LOWPT1

NodeArray<int> ogdf::Triconnectivity::m_LOWPT1

private

Definition at line 214 of file Triconnectivity.h.

◆ m_LOWPT2

NodeArray<int> ogdf::Triconnectivity::m_LOWPT2

private

Definition at line 215 of file Triconnectivity.h.

◆ m_ND

NodeArray<int> ogdf::Triconnectivity::m_ND

private

number of descendants in palm tree

Definition at line 216 of file Triconnectivity.h.

◆ m_NEWNUM

NodeArray<int> ogdf::Triconnectivity::m_NEWNUM

private

(second) dfs-number of v

Definition at line 222 of file Triconnectivity.h.

◆ m_newPath

bool ogdf::Triconnectivity::m_newPath

private

true iff we start a new path

Definition at line 232 of file Triconnectivity.h.

◆ m_NODEAT

Array<node> ogdf::Triconnectivity::m_NODEAT

private

node with number i

Definition at line 218 of file Triconnectivity.h.

◆ m_NUMBER

NodeArray<int> ogdf::Triconnectivity::m_NUMBER

private

(first) dfs-number of v

Definition at line 213 of file Triconnectivity.h.

◆ m_numComp

int ogdf::Triconnectivity::m_numComp

number of components

Note that m_component may have size bigger than m_numComp, in which case all later components should be ignored. Additionally, all components before m_numComp that have zero edges shall be ignored.

Definition at line 113 of file Triconnectivity.h.

◆ m_numCount

int ogdf::Triconnectivity::m_numCount

private

counter for dfs-traversal

Definition at line 231 of file Triconnectivity.h.

◆ m_pG

Graph* ogdf::Triconnectivity::m_pG

modifiable copy of G also containing virtual edges

Definition at line 105 of file Triconnectivity.h.

◆ m_START

EdgeArray<bool> ogdf::Triconnectivity::m_START

private

edge starts a path

Definition at line 223 of file Triconnectivity.h.

◆ m_start

node ogdf::Triconnectivity::m_start

private

start node of dfs traversal

Definition at line 230 of file Triconnectivity.h.

◆ m_top

int ogdf::Triconnectivity::m_top

private

Definition at line 132 of file Triconnectivity.h.

◆ m_TREE_ARC

NodeArray<edge> ogdf::Triconnectivity::m_TREE_ARC

private

tree arc entering v

Definition at line 224 of file Triconnectivity.h.

◆ m_TSTACK_a

int * ogdf::Triconnectivity::m_TSTACK_a

private

Definition at line 131 of file Triconnectivity.h.

◆ m_TSTACK_b

int * ogdf::Triconnectivity::m_TSTACK_b

private

Definition at line 131 of file Triconnectivity.h.

◆ m_TSTACK_h

int* ogdf::Triconnectivity::m_TSTACK_h

private

stack of triples

Definition at line 131 of file Triconnectivity.h.

◆ m_TYPE

EdgeArray<EdgeType> ogdf::Triconnectivity::m_TYPE

private

type of edge e

Definition at line 220 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/5]

◆ Triconnectivity() [2/5]

◆ Triconnectivity() [3/5]

◆ Triconnectivity() [4/5]

◆ Triconnectivity() [5/5]

◆ ~Triconnectivity()

Member Function Documentation

◆ afterRecursivePathSearch() [1/2]

◆ afterRecursivePathSearch() [2/2]

◆ assembleTriconnectedComponents()

◆ buildAcceptableAdjStruct()

◆ checkComp()

◆ checkSepPair()

◆ clearStructures()

◆ delHigh()

◆ DFS1() [1/2]

◆ DFS1() [2/2]

◆ DFS2()

◆ GCoriginal()

◆ high()

◆ newComp() [1/2]

◆ newComp() [2/2]

◆ pathFinder()

◆ pathSearch()

◆ printOs()

◆ printStacks()

◆ splitMultiEdges()

◆ TSTACK_notEOS()

◆ TSTACK_push()

◆ TSTACK_pushEOS()

Member Data Documentation

◆ m_A

◆ m_component

◆ m_DEGREE

◆ m_deleteGraph

◆ 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_pG

◆ m_START

◆ m_start

◆ m_top

◆ m_TREE_ARC

◆ m_TSTACK_a

◆ m_TSTACK_b

◆ m_TSTACK_h

◆ m_TYPE

Open
Graph Drawing
Framework