Yog.Functional.Analysis (YogEx v1.0.0)

Structural analysis for inductive graphs — components, bridges, articulation points, reachability closure, biconnected components, and dominators.

This module analyzes graph structure using the inductive primitives from Yog.Functional.Model. Component extraction uses match/2, while bridge, articulation-point, and biconnected-component detection use Tarjan-style DFS.

Available Analyses

Analysis	Function	Description
Connected Components	`connected_components/1`	Extract components by following outgoing adjacency
Bridges & Articulation Points	`analyze_connectivity/1`	Single-pass Tarjan DFS for undirected graphs
Transitive Closure	`transitive_closure/1`	Compute complete directed reachability
Biconnected Components	`biconnected_components/1`	Find maximal non-separable edge components in undirected graphs
Dominators	`dominators/2`	Compute immediate dominators for reachable flow-graph nodes

Semantics and Caveats

connected_components/1, analyze_connectivity/1, and biconnected_components/1 are intended for undirected graphs. They operate on each context's out_edges; undirected functional graphs store symmetric out-edges, so this represents ordinary adjacency.
On directed graphs, connected_components/1 follows outgoing edges only. It is therefore not a weakly-connected-components or strongly-connected-components algorithm.
transitive_closure/1 and dominators/2 are directed reachability analyses.
dominators/2 returns immediate dominators only for nodes reachable from the provided start node. A missing start node returns an empty map.

Key Concepts

Bridge (cut-edge): An edge whose removal disconnects the graph.
Articulation Point (cut-vertex): A node whose removal disconnects the graph.
Biconnected Component: A maximal edge set that remains connected after removing any single non-articulation vertex.
Components are extracted inductively via match/2, naturally preventing revisits without an explicit visited set.

Complexity

connected_components/1, analyze_connectivity/1, transitive_closure/1, and biconnected_components/1 are O(V + E) over the relevant traversal work, except transitive_closure/1, which performs reachability from every node and is O(V * (V + E)). dominators/2 uses a fixed-point algorithm suitable for small functional flow graphs rather than maximum raw throughput.

References

Summary

Types

bridge()

Functions

analyze_connectivity(graph)

Identifies bridges (cut-edges) and articulation points (cut-vertices) in an undirected graph using a single-pass DFS.

biconnected_components(graph)

Finds the biconnected components of an undirected graph.

connected_components(graph)

Finds all connected components in an undirected graph.

dominators(graph, start)

Finds immediate dominators of all reachable nodes from a start node.

transitive_closure(graph)

Computes the transitive closure of the graph as a map of node reachability.

Types

bridge()

@type bridge() :: {Yog.Functional.Model.node_id(), Yog.Functional.Model.node_id()}

Functions

analyze_connectivity(graph)

@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.

The function assumes undirected adjacency represented by symmetric out_edges, which Yog.Functional.Model maintains for graphs created with Model.new(:undirected).

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]

biconnected_components(graph)

@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}. Isolated nodes do not form edge-biconnected components and therefore do not appear in the result.

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

connected_components(graph)

@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. This function follows out_edges; for an undirected functional graph those edges are symmetric and represent ordinary adjacency. On directed graphs this is an outgoing-reachability component extraction, not weak or strong connectivity.

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]]

dominators(graph, start)

@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}. The start node dominates itself. Nodes that are not reachable from start are omitted. If start is not present in the graph, the result is %{}.

Uses a recursive fixed-point implementation suitable for small functional flow graphs and proof-oriented examples.

transitive_closure(graph)

@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]}. Each reachable list includes the source node itself because reachability is computed via traversal starting at that node.

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]