Skip to content

articulation_points.md

Latest commit

 

History

History
241 lines (180 loc) · 7.63 KB

articulation_points.md

File metadata and controls

241 lines (180 loc) · 7.63 KB
graph-v3 logo

Articulation Points

← Back to Algorithm Catalog

Table of Contents

Overview

An articulation point (cut vertex) is a vertex whose removal disconnects the graph (or increases the number of connected components). The algorithm uses the iterative Hopcroft-Tarjan approach with discovery times and low-link values.

The graph must satisfy adjacency_list<G> — both index-based (contiguous integer-indexed) and map-based (sparse vertex ID) graphs are supported.

Each articulation point is emitted exactly once to the output iterator, though the order is unspecified.

When to Use

  • Network vulnerability analysis — identify single points of failure in communication, transportation, or power networks.
  • Graph connectivity hardening — after finding articulation points, add redundant links to eliminate them and make the graph biconnected.
  • Fast structural check — at O(V + E), this is a cheap way to verify whether a graph is 2-connected (biconnected): if no articulation points exist, the graph is biconnected.

Consider alternatives when:

Include

#include <graph/algorithm/articulation_points.hpp>

Signature

void articulation_points(G&& g, OutputIterator cut_vertices);

Parameters

Parameter Description
g Graph satisfying adjacency_list
cut_vertices Output iterator receiving vertex IDs of articulation points. Each vertex appears exactly once.

Supported Graph Properties

Directedness:

  • ✅ Undirected graphs (each edge stored bidirectionally)
  • ❌ Directed graphs — algorithm is defined for undirected graphs only

Edge Properties:

  • ✅ Unweighted edges (weights ignored)
  • ✅ Weighted edges (weights ignored)
  • ✅ Multi-edges (parallel edges do not affect result)
  • ✅ Self-loops (ignored — do not affect detection)

Graph Structure:

  • ✅ Connected graphs
  • ✅ Disconnected graphs (each component processed independently)
  • ✅ Empty graphs (returns no articulation points)

Container Requirements:

  • Required: adjacency_list<G>
  • Output: std::output_iterator<OutputIterator, vertex_id_t<G>>

Examples

Example 1: Finding Cut Vertices

Find all vertices whose removal would disconnect the graph.

#include <graph/algorithm/articulation_points.hpp>
#include <graph/container/dynamic_graph.hpp>
#include <vector>

using Graph = container::dynamic_graph<void, void, void, uint32_t, false,
    container::vov_graph_traits<void>>;

// Bridge graph: two triangles connected by a bridge at vertices 2-3
//   0 - 1     3 - 4
//    \ |  --- |  /
//     2  ---- 3
Graph g({{0,1},{1,0}, {1,2},{2,1}, {0,2},{2,0},
         {2,3},{3,2},
         {3,4},{4,3}, {3,5},{5,3}, {4,5},{5,4}});

std::vector<uint32_t> cuts;
articulation_points(g, std::back_inserter(cuts));

// cuts = {2, 3} (order may vary)
// Removing vertex 2 disconnects {0,1} from {3,4,5}
// Removing vertex 3 disconnects {0,1,2} from {4,5}

Example 2: Star Graph — Single Articulation Point

In a star topology the center vertex is the sole articulation point, since every leaf communicates only through the center.

// Star: center vertex 0 connected to leaves 1, 2, 3, 4
Graph star({{0,1},{1,0}, {0,2},{2,0}, {0,3},{3,0}, {0,4},{4,0}});

std::vector<uint32_t> cuts;
articulation_points(star, std::back_inserter(cuts));
// cuts = {0}  — only the center is a cut vertex

Example 3: Path Graph vs. Cycle

In a path graph, every interior vertex is an articulation point. Adding one edge to close the path into a cycle eliminates all of them.

// Path: 0 - 1 - 2 - 3
Graph path({{0,1},{1,0}, {1,2},{2,1}, {2,3},{3,2}});

std::vector<uint32_t> cuts;
articulation_points(path, std::back_inserter(cuts));
// cuts = {1, 2}  — both interior vertices are cut vertices
// Leaf vertices 0 and 3 are not articulation points

// Closing the path into a cycle removes all articulation points:
// 0 - 1 - 2 - 3 - 0
Graph cycle({{0,1},{1,0}, {1,2},{2,1}, {2,3},{3,2}, {3,0},{0,3}});

std::vector<uint32_t> cuts2;
articulation_points(cycle, std::back_inserter(cuts2));
// cuts2 is empty — every vertex can be removed without disconnection

Example 4: Complete Graph — No Articulation Points

A complete graph (K_n) with n ≥ 3 has no articulation points. This is a quick litmus test: if the algorithm returns an empty result, the graph is biconnected.

// K4: complete graph on 4 vertices (all pairs connected)
Graph k4({{0,1},{1,0}, {0,2},{2,0}, {0,3},{3,0},
          {1,2},{2,1}, {1,3},{3,1}, {2,3},{3,2}});

std::vector<uint32_t> cuts;
articulation_points(k4, std::back_inserter(cuts));
// cuts is empty — K4 is biconnected
// Removing any single vertex still leaves a connected graph

Example 5: Disconnected Graph

Articulation points are identified independently within each connected component. Isolated vertices are never articulation points.

// Component A: path 0-1-2 (interior vertex 1 is an AP)
// Component B: triangle 3-4-5 (no APs)
// Vertex 6: isolated
Graph g({{0,1},{1,0}, {1,2},{2,1},
         {3,4},{4,3}, {4,5},{5,4}, {3,5},{5,3}});
// Vertex 6 exists but has no edges

std::vector<uint32_t> cuts;
articulation_points(g, std::back_inserter(cuts));
// cuts = {1}  — only the interior vertex of the path component
// Isolated vertex 6 is not an articulation point
// The triangle has no articulation points

Mandates

  • G must satisfy adjacency_list<G>
  • OutputIterator must satisfy std::output_iterator<vertex_id_t<G>>

Preconditions

  • For undirected graphs, both directions of each edge must be stored (or use undirected_adjacency_list).
  • Self-loops do not affect the result.
  • Parallel edges: a vertex connecting two otherwise-disconnected subgraphs via parallel edges is still considered an articulation point.

Effects

  • Writes articulation point vertex IDs to the output iterator
  • Does not modify the graph g

Throws

  • std::bad_alloc if internal allocations fail
  • Exception guarantee: Basic. Graph g remains unchanged; output may be partial.

Complexity

Metric Value
Time O(V + E)
Space O(V) for discovery times, low-link values, and the DFS stack

See Also