Yog.Connectivity.Reachability (YogEx v0.97.1)

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

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; } }

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

Summary

Types

direction()

Direction for reachability counting

Functions

counts(graph, direction)

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

counts_estimate(graph, direction)

Estimates the number of ancestors or descendants using HyperLogLog.

Types

direction()

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

Direction for reachability counting

Functions

counts(graph, direction)

@spec counts(Yog.graph(), direction()) :: %{required(Yog.node_id()) => 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(graph, direction)

@spec counts_estimate(Yog.graph(), direction()) :: %{
  required(Yog.node_id()) => 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