# `Yog.Functional.Analysis`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.0/lib/yog/functional/analysis.ex#L1)

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

- [Wikipedia: Bridge (Graph Theory)](https://en.wikipedia.org/wiki/Bridge_(graph_theory))
- [Wikipedia: Biconnected Component](https://en.wikipedia.org/wiki/Biconnected_component)

# `bridge`

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

# `analyze_connectivity`

```elixir
@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]

# `biconnected_components`

```elixir
@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

# `connected_components`

```elixir
@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]]

# `dominators`

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

# `transitive_closure`

```elixir
@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]

---

*Consult [api-reference.md](api-reference.md) for complete listing*