# `Yog.Connectivity.Reachability`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/connectivity/reachability.ex#L1)

Algorithms for analyzing node reachability in directed and undirected graphs.

## Memory Warning

The `counts/2` function builds complete reachability sets which requires O(V²)
memory in the worst case (dense graphs). For large graphs (>10,000 nodes),
consider using `counts_estimate/2` which uses HyperLogLog for approximate
counting with O(V) memory.

## Reachability Visualization

Reachability analysis identifies the set of all nodes that can be visited starting from a specific source node (descendants) or that can visit a specific node (ancestors).

<div class="graphviz">
digraph G {
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];

  Source [label="Source", color="#6366f1", penwidth=2.5, style=bold];
  
  // Reachable set
  Source -> A [color="#6366f1"];
  A -> B [color="#6366f1"];
  Source -> C [color="#6366f1"];
  
  // Unreachable from Source
  X -> Y;
  X -> Source [style=dashed, label="ancestor"];
  
  subgraph cluster_reachable {
    label="Reachability Set (Descendants)"; color="#6366f1"; style=rounded;
    A; B; C;
  }
}
</div>

    iex> alias Yog.Connectivity.Reachability
    iex> graph = Yog.from_edges(:directed, [
    ...>   {"Source", "A", 1}, {"A", "B", 1}, {"Source", "C", 1},
    ...>   {"X", "Y", 1}, {"X", "Source", 1}
    ...> ])
    iex> Reachability.counts(graph, :descendants)["Source"]
    3

# `direction`

```elixir
@type direction() :: :ancestors | :descendants
```

Direction for reachability counting

# `counts`

```elixir
@spec counts(Yog.graph(), direction()) :: %{required(Yog.node_id()) =&gt; integer()}
```

Counts the number of ancestors or descendants for every node in the graph.

For each node, returns how many other nodes are reachable from it
(`:descendants`) or can reach it (`:ancestors`).

In a directed graph, this counts nodes in the reachability set.
In an undirected graph, this is equivalent to the size of the connected component
minus the node itself.

## Algorithm

- If the graph is acyclic, it uses an optimized dynamic programming approach
  on the topological order (O(V * E)).
- If the graph contains cycles, it simplifies the graph into its condensation
  (the DAG of strongly connected components) to maintain efficiency.

## Memory Warning

This function builds complete reachability sets requiring O(V²) memory.
For large graphs, use `counts_estimate/2` instead.

## Examples

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> counts = Yog.Connectivity.Reachability.counts(graph, :descendants)
    iex> counts[1]
    2
    iex> counts[3]
    0

# `counts_estimate`

```elixir
@spec counts_estimate(Yog.graph(), direction()) :: %{
  required(Yog.node_id()) =&gt; integer()
}
```

Estimates the number of ancestors or descendants using HyperLogLog.

This is a memory-efficient alternative to `counts/2` that uses approximately
O(V) memory instead of O(V²). The trade-off is approximate results with
~3.25% standard error.

## When to Use

- Large graphs (>10,000 nodes) where memory is constrained
- When approximate counts are acceptable
- Streaming or online analysis scenarios

## Examples

    iex> graph = Yog.directed()
    ...> |> Yog.add_node(1, nil)
    ...> |> Yog.add_node(2, nil)
    ...> |> Yog.add_node(3, nil)
    ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
    ...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
    iex> counts = Yog.Connectivity.Reachability.counts_estimate(graph, :descendants)
    iex> counts[1] > 0
    true

---

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