Structural analysis for inductive graphs — components, bridges, and articulation points.
This module analyzes connectivity and vulnerability in graphs using the inductive
match/2 operation for component extraction and Tarjan's DFS for bridge/cut-vertex
detection.
Available Analyses
| Analysis | Function | Description |
|---|---|---|
| Connected Components | connected_components/1 | Find all connected components |
| Bridges & Articulation Points | analyze_connectivity/1 | Single-pass Tarjan DFS |
| Transitive Closure | transitive_closure/1 | Compute complete reachability |
| Biconnected Components | biconnected_components/1 | Find maximal non-separable subgraphs |
| Dominators | dominators/2 | Compute node dominance for flow graphs |
Key Concepts
- Bridge (cut-edge): An edge whose removal disconnects the graph
- Articulation Point (cut-vertex): A node whose removal disconnects the graph
- Components are extracted inductively via
match/2, naturally preventing revisits without an explicit visited set
References
Summary
Functions
Identifies bridges (cut-edges) and articulation points (cut-vertices) in an undirected graph using a single-pass DFS.
Finds the biconnected components of an undirected graph.
Each component is represented as a list of edge tuples {u, v}.
Finds all connected components in an undirected graph. Returns a list of lists of node IDs.
Finds immediate dominators of all reachable nodes from a start node.
Returns %{node_id => idom_id}.
Computes the transitive closure of the graph as a map of node reachability.
Returns %{node_id => [reachable_node_ids]}.
Types
@type bridge() :: {Yog.Functional.Model.node_id(), Yog.Functional.Model.node_id()}
Functions
@spec analyze_connectivity(Yog.Functional.Model.t()) :: %{ bridges: [bridge()], points: [Yog.Functional.Model.node_id()] }
Identifies bridges (cut-edges) and articulation points (cut-vertices) in an undirected graph using a single-pass DFS.
Examples
iex> alias Yog.Functional.{Model, Analysis}
iex> graph = Model.new(:undirected)
...> |> Model.put_node(1, "A") |> Model.put_node(2, "B") |> Model.put_node(3, "C")
...> |> Model.add_edge!(1, 2) |> Model.add_edge!(2, 3)
iex> result = Analysis.analyze_connectivity(graph)
iex> result.bridges |> Enum.sort()
[{1, 2}, {2, 3}]
iex> result.points |> Enum.sort()
[2]@spec biconnected_components(Yog.Functional.Model.t()) :: [ [{Yog.Functional.Model.node_id(), Yog.Functional.Model.node_id()}] ]
Finds the biconnected components of an undirected graph.
Each component is represented as a list of edge tuples {u, v}.
Examples
iex> alias Yog.Functional.{Model, Analysis}
iex> graph = Model.new(:undirected)
...> |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.put_node(3, "C") |> Model.add_edge!(1, 2)
...> |> Model.add_edge!(2, 3)
iex> bccs = Analysis.biconnected_components(graph)
iex> length(bccs)
2@spec connected_components(Yog.Functional.Model.t()) :: [ [Yog.Functional.Model.node_id()] ]
Finds all connected components in an undirected graph. Returns a list of lists of node IDs.
Examples
iex> alias Yog.Functional.{Model, Analysis}
iex> graph = Model.new(:undirected)
...> |> Model.put_node(1, "A")
...> |> Model.put_node(2, "B")
...> |> Model.put_node(3, "C")
...> |> Model.add_edge!(1, 2)
iex> components = Analysis.connected_components(graph)
iex> Enum.map(components, &Enum.sort/1) |> Enum.sort()
[[1, 2], [3]]@spec dominators(Yog.Functional.Model.t(), Yog.Functional.Model.node_id()) :: %{ required(Yog.Functional.Model.node_id()) => Yog.Functional.Model.node_id() }
Finds immediate dominators of all reachable nodes from a start node.
Returns %{node_id => idom_id}.
Uses a recursive fixed-point implementation suitable for functional graphs. The start node dominates itself.
@spec transitive_closure(Yog.Functional.Model.t()) :: %{ required(Yog.Functional.Model.node_id()) => [Yog.Functional.Model.node_id()] }
Computes the transitive closure of the graph as a map of node reachability.
Returns %{node_id => [reachable_node_ids]}.
Examples
iex> alias Yog.Functional.{Model, Analysis}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> tc = Analysis.transitive_closure(graph)
iex> tc[1] |> Enum.sort()
[1, 2]