tpl_cut_nodes.H File Reference

Articulation points (cut nodes), bridges, and biconnected components. More...

#include <tpl_graph_utils.H>

Include dependency graph for tpl_cut_nodes.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Compute_Cut_Nodes< GT, SA >
	Computation of cut nodes (articulation points) of a graph. More...
class	Aleph::Compute_Bridges< GT, SA >
	Find bridge edges (isthmuses) of a connected undirected graph. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Arc * >	Aleph::find_bridges (const GT &g, typename GT::Node *start, SA sa=SA())
	Find all bridge edges in a connected undirected graph.
template<class GT >
DynList< typename GT::Arc * >	Aleph::find_bridges (const GT &g)

Detailed Description

Articulation points (cut nodes), bridges, and biconnected components.

Provides two related algorithms for connectivity analysis of undirected graphs, both based on Tarjan's DFS low-link technique (O(V + E)):

Cut nodes (articulation points)

A cut node is a vertex whose removal disconnects the graph.

Symbol	Meaning
df[v]	DFS discovery time of v
low[v]	minimum df reachable from v's subtree via ≤1 back-edge

Condition (non-root): v is a cut node if ∃ child c with low[c] >= df[v].

API

• Compute_Cut_Nodes<GT,SA>: class — compute, then optionally paint biconnected blocks and extract mapped subgraphs.
• compute_cut_nodes(g) / compute_cut_nodes(g, start): free functions returning DynList<Node*>.

Bridges (cut edges / isthmuses)

A bridge is an edge whose removal disconnects the graph.

Condition: tree edge (u → v) is a bridge iff low[v] > df[u] (no back-edge from v's subtree escapes above u).

Parallel edges are handled correctly: only the exact parent arc (by pointer identity) is skipped; a second parallel arc acts as a back-edge.

API

• Compute_Bridges<GT,SA>: class with find_bridges(start), find_bridges(), operator()(start), operator()().
• find_bridges(g) / find_bridges(g, start): free functions returning DynList<Arc*>.

Biconnected components

After calling Compute_Cut_Nodes::cut_nodes(), call paint_subgraphs() to colour each biconnected block, then map_subgraph() or compute_blocks() to extract mapped copies.

Note

Both algorithms require an undirected, connected graph. A std::domain_error is thrown for digraphs.

Complexity: O(V + E) time and O(V) extra space.

See also

tpl_components.H Connected components

tpl_graph_utils.H Low-level graph utilities (df<GT>, low<GT>)

Author

Leandro Rabindranath León

Definition in file tpl_cut_nodes.H.