Testing Triconnectivity ( TriconnectivityTest )

Baseclasses

Definition

The class TriconnectivityTest represents the triconnectivity test algorithm according to Hopcroft and Tarjan [HT73]. It tests if a graph G is triconnected and returns a witness (cut vertex, separation pair) if not. There are no restrictions on the input graph G, i.e., G may contain multiple edges or self loops.

General Information

Algorithm
name	Triconnectivity Test
long name	Triconnectivity Test (Hopcroft/Tarjan)
author	J. E. Hopcroft, R. E. Tarjan

Implementation
author	C. Gutwenger
date	Novembre 1998
version	1.0

Pre- and Postcondition

precondition

=

$\emptyset$

#include < AGD/TriconnectivityTest.h >

Creation

TriconnectivityTest

T

creates an instance T of type TriconnectivityTest.

Operations

bool	T.call(const leda_graph& G)
		calls T for graph G. Returns true iff G is triconnected.
bool	T.call(const leda_graph& G, leda_node& s1, leda_node& s2)
		calls T for graph G. Returns true iff G is triconnected. Returns in s1 and s2 nodes whose deletion disconnect the graph, i.e. s1 = nil and s2 = nil $\Rightarrow$ G is not connected, s1! = nil and s2 = nil $\Rightarrow$ s1 is a cut vertex, s1! = nil and s2! = nil $\Rightarrow$ (s1, s2) is a separation pair.

Implementation

Testing a graph G = (V, E) for triconnectivity takes time $\protectO$(| V| + | E|).