Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::Triconnectivity Class Reference

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< CompStructm_component
 array of components More...
 
int m_numComp
 number of components More...
 
GraphCopySimplem_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...
 
CompStructnewComp ()
 create a new empty component More...
 
CompStructnewComp (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< edgem_ESTACK
 stack of currently active edges More...
 
NodeArray< nodem_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< nodem_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< edgem_TREE_ARC
 tree arc entering v More...
 
int * m_TSTACK_a
 
int * m_TSTACK_b
 
int * m_TSTACK_h
 stack of triples More...
 
EdgeArray< EdgeTypem_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

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
Ggraph

◆ Triconnectivity() [2/3]

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

Tests G for triconnectivity.

Parameters
Ggraph
isTrictrue if G is triconnected, false otherwise.
s1first vertex of separation pair if G is biconnected, cut vertex of G if G is not biconnected, nullptr if G is not connected.
s2second 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: