realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph
More...
#include <ogdf/graphalg/Triconnectivity.h>
|
| 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 More...
|
|
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 More...
|
|
void | assembleTriconnectedComponents () |
| merges split-components into triconnected components More...
|
|
void | buildAcceptableAdjStruct () |
| constructs ordered adjaceny lists More...
|
|
bool | checkSepPair (edge eVirt) const |
|
void | clearStructures () |
|
void | delHigh (edge e) |
|
void | DFS1 (node v, node u) |
| first dfs traversal More...
|
|
void | DFS1 (node v, node u, node &s1) |
| special version for triconnectivity test More...
|
|
void | DFS2 () |
| the second dfs traversal More...
|
|
template<typename T > |
T | GCoriginal (T n) const |
| returns m_pG.original(n) if m_pG is a GraphCopySimple, otherwise n itself 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 (node v) |
|
bool | pathSearch (node init_v, bool fail_fast, node &s1, node &s2) |
| finding of split components More...
|
|
void | printOs (edge e) const |
| debugging stuff More...
|
|
void | printStacks () const |
|
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...
|
|
realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multi-graph
Definition at line 50 of file Triconnectivity.h.
◆ CompType
type of split-components / triconnected components
Enumerator |
---|
bond | |
polygon | |
triconnected | |
Definition at line 86 of file Triconnectivity.h.
◆ EdgeType
type of edges with respect to palm tree
Enumerator |
---|
unseen | |
tree | |
frond | |
removed | |
Definition at line 158 of file Triconnectivity.h.
◆ 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
-
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]
◆ ~Triconnectivity()
ogdf::Triconnectivity::~Triconnectivity |
( |
| ) |
|
◆ 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 |
◆ 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 |
◆ 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 |
◆ DFS1() [1/2]
void ogdf::Triconnectivity::DFS1 |
( |
node |
v, |
|
|
node |
u |
|
) |
| |
|
private |
◆ 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 |
◆ GCoriginal()
template<typename T >
T ogdf::Triconnectivity::GCoriginal |
( |
T |
n | ) |
const |
|
inlineprivate |
◆ high()
int ogdf::Triconnectivity::high |
( |
node |
v | ) |
|
|
inlineprivate |
◆ newComp() [1/2]
◆ newComp() [2/2]
◆ 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 |
◆ 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 |
◆ TSTACK_pushEOS()
void ogdf::Triconnectivity::TSTACK_pushEOS |
( |
| ) |
|
|
inlineprivate |
◆ m_A
◆ m_component
◆ m_DEGREE
NodeArray<int> ogdf::Triconnectivity::m_DEGREE |
|
private |
◆ 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
◆ m_FATHER
◆ m_HIGHPT
list of fronds entering v in the order they are visited
Definition at line 225 of file Triconnectivity.h.
◆ m_IN_ADJ
◆ m_IN_HIGH
◆ m_LOWPT1
NodeArray<int> ogdf::Triconnectivity::m_LOWPT1 |
|
private |
◆ m_LOWPT2
NodeArray<int> ogdf::Triconnectivity::m_LOWPT2 |
|
private |
◆ m_ND
◆ m_NEWNUM
NodeArray<int> ogdf::Triconnectivity::m_NEWNUM |
|
private |
◆ m_newPath
bool ogdf::Triconnectivity::m_newPath |
|
private |
◆ m_NODEAT
◆ m_NUMBER
NodeArray<int> ogdf::Triconnectivity::m_NUMBER |
|
private |
◆ 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 |
◆ 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 |
◆ m_start
node ogdf::Triconnectivity::m_start |
|
private |
◆ m_top
int ogdf::Triconnectivity::m_top |
|
private |
◆ m_TREE_ARC
◆ m_TSTACK_a
int * ogdf::Triconnectivity::m_TSTACK_a |
|
private |
◆ m_TSTACK_b
int * ogdf::Triconnectivity::m_TSTACK_b |
|
private |
◆ m_TSTACK_h
int* ogdf::Triconnectivity::m_TSTACK_h |
|
private |
◆ m_TYPE
The documentation for this class was generated from the following file: