806 Advanced

806-articulation-points — Articulation Points

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "806-articulation-points — Articulation Points" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. An articulation point (cut vertex) is a vertex whose removal disconnects the graph. Key difference from OCaml: 1. **Two conditions**: The root condition (children > 1) and non

Tutorial

The Problem

An articulation point (cut vertex) is a vertex whose removal disconnects the graph. Finding articulation points in O(V+E) is critical for network reliability analysis: which routers, if removed, would split the internet? Which protein in a protein-protein interaction network is essential? Which road intersection, if closed, disconnects a city? The algorithm also finds bridges (edges whose removal disconnects the graph).

🎯 Learning Outcomes

• Track discovery time and low-link values per vertex during DFS

• Identify articulation points using the root condition (children > 1) and non-root condition (low[child] >= disc[parent])

• Understand the low[v] value: minimum discovery time reachable from v's subtree via back edges

• Extend to bridge detection: an edge (u,v) is a bridge if low[v] > disc[u]

• Apply to network resilience analysis

Code Example

#![allow(clippy::all)]
//! # Articulation Points
pub fn articulation_points(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut disc = vec![0; n];
    let mut low = vec![0; n];
    let mut parent = vec![None; n];
    let mut ap = vec![false; n];
    let mut time = 0;
    let mut visited = vec![false; n];
    fn dfs(
        u: usize,
        adj: &[Vec<usize>],
        disc: &mut [usize],
        low: &mut [usize],
        parent: &mut [Option<usize>],
        ap: &mut [bool],
        time: &mut usize,
        vis: &mut [bool],
    ) {
        vis[u] = true;
        disc[u] = *time;
        low[u] = *time;
        *time += 1;
        let mut children = 0;
        for &v in &adj[u] {
            if !vis[v] {
                children += 1;
                parent[v] = Some(u);
                dfs(v, adj, disc, low, parent, ap, time, vis);
                low[u] = low[u].min(low[v]);
                if parent[u].is_none() && children > 1 {
                    ap[u] = true;
                }
                if parent[u].is_some() && low[v] >= disc[u] {
                    ap[u] = true;
                }
            } else if parent[u] != Some(v) {
                low[u] = low[u].min(disc[v]);
            }
        }
    }
    for v in 0..n {
        if !visited[v] {
            dfs(
                v,
                &adj,
                &mut disc,
                &mut low,
                &mut parent,
                &mut ap,
                &mut time,
                &mut visited,
            );
        }
    }
    (0..n).filter(|&i| ap[i]).collect()
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ap() {
        let ap = articulation_points(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!ap.is_empty());
    }
}

(* Articulation Points and Bridges — O(V+E) DFS *)

let find_aps_bridges adj n =
  let disc   = Array.make n (-1) in
  let low    = Array.make n 0 in
  let is_ap  = Array.make n false in
  let timer  = ref 0 in
  let bridges = ref [] in

  let rec dfs u parent =
    disc.(u) <- !timer;
    low.(u)  <- !timer;
    incr timer;
    let children = ref 0 in
    List.iter (fun v ->
      if disc.(v) = -1 then begin
        incr children;
        dfs v u;
        low.(u) <- min low.(u) low.(v);
        (* Bridge check *)
        if low.(v) > disc.(u) then
          bridges := (u, v) :: !bridges;
        (* Articulation point check for non-root *)
        if parent <> -1 && low.(v) >= disc.(u) then
          is_ap.(u) <- true
      end else if v <> parent then
        low.(u) <- min low.(u) disc.(v)
    ) adj.(u);
    (* Root is AP iff it has >1 DFS children *)
    if parent = -1 && !children > 1 then is_ap.(u) <- true
  in
  for v = 0 to n - 1 do
    if disc.(v) = -1 then dfs v (-1)
  done;
  let aps = Array.to_list (Array.init n (fun i -> (i, is_ap.(i))))
            |> List.filter_map (fun (i, b) -> if b then Some i else None)
  in
  (aps, !bridges)

let () =
  let n   = 7 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 0;  (* triangle 0-1-2 *)
  add 1 3; add 3 4; add 4 5; add 5 3;  (* 1-3, triangle 3-4-5 *)
  add 3 6;  (* pendant from 3 *)
  let (aps, bridges) = find_aps_bridges adj n in
  Printf.printf "Articulation points: [%s]\n"
    (String.concat "," (List.map string_of_int aps));
  Printf.printf "Bridges:\n";
  List.iter (fun (u,v) -> Printf.printf "  %d-%d\n" u v) bridges

Key Differences

Two conditions: The root condition (children > 1) and non-root condition (low[child] >= disc[u]) handle the two cases identically in both languages.

Parent tracking: Both use a parent array to avoid treating the tree edge back to parent as a back edge; the -1 / None sentinel serves the same purpose.

Undirected graphs: Both add edges in both directions for undirected graphs; the parent check prevents incorrectly counting the parent as a back edge.

Network analysis: ISP engineers use articulation point algorithms to identify single points of failure; tools like traceroute data combined with this algorithm maps internet topology.

OCaml Approach

OCaml implements with ref cells for time and mutable arrays for disc, low, parent, ap. Recursive DFS uses let rec dfs u = ... List.iter (fun v -> ...) adj.(u). The Ocamlgraph.Components.articulation_points function provides a ready-made implementation. Bridge finding changes the condition from >= to >.

Full Source

#![allow(clippy::all)]
//! # Articulation Points
pub fn articulation_points(n: usize, edges: &[(usize, usize)]) -> Vec<usize> {
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut disc = vec![0; n];
    let mut low = vec![0; n];
    let mut parent = vec![None; n];
    let mut ap = vec![false; n];
    let mut time = 0;
    let mut visited = vec![false; n];
    fn dfs(
        u: usize,
        adj: &[Vec<usize>],
        disc: &mut [usize],
        low: &mut [usize],
        parent: &mut [Option<usize>],
        ap: &mut [bool],
        time: &mut usize,
        vis: &mut [bool],
    ) {
        vis[u] = true;
        disc[u] = *time;
        low[u] = *time;
        *time += 1;
        let mut children = 0;
        for &v in &adj[u] {
            if !vis[v] {
                children += 1;
                parent[v] = Some(u);
                dfs(v, adj, disc, low, parent, ap, time, vis);
                low[u] = low[u].min(low[v]);
                if parent[u].is_none() && children > 1 {
                    ap[u] = true;
                }
                if parent[u].is_some() && low[v] >= disc[u] {
                    ap[u] = true;
                }
            } else if parent[u] != Some(v) {
                low[u] = low[u].min(disc[v]);
            }
        }
    }
    for v in 0..n {
        if !visited[v] {
            dfs(
                v,
                &adj,
                &mut disc,
                &mut low,
                &mut parent,
                &mut ap,
                &mut time,
                &mut visited,
            );
        }
    }
    (0..n).filter(|&i| ap[i]).collect()
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ap() {
        let ap = articulation_points(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!ap.is_empty());
    }
}

(* Articulation Points and Bridges — O(V+E) DFS *)

let find_aps_bridges adj n =
  let disc   = Array.make n (-1) in
  let low    = Array.make n 0 in
  let is_ap  = Array.make n false in
  let timer  = ref 0 in
  let bridges = ref [] in

  let rec dfs u parent =
    disc.(u) <- !timer;
    low.(u)  <- !timer;
    incr timer;
    let children = ref 0 in
    List.iter (fun v ->
      if disc.(v) = -1 then begin
        incr children;
        dfs v u;
        low.(u) <- min low.(u) low.(v);
        (* Bridge check *)
        if low.(v) > disc.(u) then
          bridges := (u, v) :: !bridges;
        (* Articulation point check for non-root *)
        if parent <> -1 && low.(v) >= disc.(u) then
          is_ap.(u) <- true
      end else if v <> parent then
        low.(u) <- min low.(u) disc.(v)
    ) adj.(u);
    (* Root is AP iff it has >1 DFS children *)
    if parent = -1 && !children > 1 then is_ap.(u) <- true
  in
  for v = 0 to n - 1 do
    if disc.(v) = -1 then dfs v (-1)
  done;
  let aps = Array.to_list (Array.init n (fun i -> (i, is_ap.(i))))
            |> List.filter_map (fun (i, b) -> if b then Some i else None)
  in
  (aps, !bridges)

let () =
  let n   = 7 in
  let adj = Array.make n [] in
  let add u v = adj.(u) <- v :: adj.(u); adj.(v) <- u :: adj.(v) in
  add 0 1; add 1 2; add 2 0;  (* triangle 0-1-2 *)
  add 1 3; add 3 4; add 4 5; add 5 3;  (* 1-3, triangle 3-4-5 *)
  add 3 6;  (* pendant from 3 *)
  let (aps, bridges) = find_aps_bridges adj n in
  Printf.printf "Articulation points: [%s]\n"
    (String.concat "," (List.map string_of_int aps));
  Printf.printf "Bridges:\n";
  List.iter (fun (u,v) -> Printf.printf "  %d-%d\n" u v) bridges

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_ap() {
        let ap = articulation_points(5, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)]);
        assert!(!ap.is_empty());
    }
}

Deep Comparison

OCaml vs Rust: Articulation Points

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement find_bridges(n, edges) -> Vec<(usize, usize)> using the same DFS with the modified condition low[v] > disc[u].

Compute the 2-vertex-connected components: groups of vertices that remain connected after removing any single vertex.

Apply to a social network: find "bridge users" whose profiles, if deleted, would disconnect communities. Visualize the result.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust