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

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

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

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`

```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}`. 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`

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

```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}`. 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`

```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]}`. 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]

---

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