Yog.Graph (YogEx v0.97.1)

Core graph data structure.

A graph is represented as a struct with four fields:

kind: Either :directed or :undirected
nodes: Map of node_id => node_data
out_edges: Map of node_id => %{neighbor_id => weight}
in_edges: Map of node_id => %{neighbor_id => weight}

The dual-map representation (storing both out_edges and in_edges) enables:

O(1) graph transpose (just swap out_edges ↔ in_edges)
Efficient predecessor queries without traversing the entire graph
Fast bidirectional edge lookups

Examples

iex> %Yog.Graph{
...>   kind: :directed,
...>   nodes: %{1 => "A", 2 => "B"},
...>   out_edges: %{1 => %{2 => 10}},
...>   in_edges: %{2 => %{1 => 10}}
...> }

Protocols

Yog.Graph implements the Enumerable and Inspect protocols:

Enumerable: Iterates over nodes as {id, data} tuples
Inspect: Compact representation showing graph type and statistics

Visual Showcase

digraph G { rankdir=LR; bgcolor="transparent"; node [fontname="inherit", shape=box, style=rounded, penwidth=1.5]; edge [fontname="inherit", fontsize=10, penwidth=1.2]; subsystem [label="Core System", shape=hexagon, color="#6366f1"]; node1 [label="Logic A", color="#10b981"]; node2 [label="Logic B", color="#10b981"]; node3 [label="Logic C", color="#10b981"]; storage [label="Storage", shape=cylinder, color="#f59e0b"]; user [label="User", shape=doublecircle, color="#ef4444"]; subsystem -> node1 [label="invokes", color="#6366f1"]; subsystem -> node2 [label="invokes", color="#6366f1"]; node1 -> node3 [label="calls", style=dashed, color="#10b981"]; node2 -> node3 [label="calls", style=dashed, color="#10b981"]; node3 -> storage [label="writes", color="#f59e0b"]; user -> subsystem [label="triggers", color="#ef4444", penwidth=2.5]; }

iex> graph = Yog.directed()
...> |> Yog.add_edge_ensure("User", "Core System", "triggers")
...> |> Yog.add_edge_ensure("Core System", "Logic A", "invokes")
...> |> Yog.add_edge_ensure("Core System", "Logic B", "invokes")
...> |> Yog.add_edge_ensure("Logic A", "Logic C", "calls")
...> |> Yog.add_edge_ensure("Logic B", "Logic C", "calls")
...> |> Yog.add_edge_ensure("Logic C", "Storage", "writes")
iex> Yog.node_count(graph)
6
iex> Yog.edge_count(graph)
6

Summary

Types

kind()

node_id()

t()

Functions

edge_count(graph)

Returns the total number of edges in the graph.

new(kind)

Creates a new empty graph of the given type.

node_count(graph)

Returns the number of nodes in the graph.

Types

kind()

@type kind() :: :directed | :undirected

node_id()

@type node_id() :: term()

t()

@type t() :: %Yog.Graph{
  in_edges: %{required(node_id()) => %{required(node_id()) => number()}},
  kind: kind(),
  nodes: %{required(node_id()) => any()},
  out_edges: %{required(node_id()) => %{required(node_id()) => number()}}
}

Functions

edge_count(graph)

@spec edge_count(t()) :: non_neg_integer()

Returns the total number of edges in the graph.

For undirected graphs, this counts each edge once (not twice).

Performance Note

This function traverses all nodes' outgoing edges, making it O(V) where V is the number of vertices. If you need the edge count multiple times, consider caching the result:

edge_count = Yog.Graph.edge_count(graph)
# Use edge_count in subsequent calculations...

Example

iex> graph = Yog.Graph.new(:directed)
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
iex> Yog.Graph.edge_count(graph)
2

iex> graph = Yog.Graph.new(:undirected)
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
iex> Yog.Graph.edge_count(graph)
2

new(kind)

@spec new(kind()) :: t()

Creates a new empty graph of the given type.

Example

iex> Yog.Graph.new(:directed)
%Yog.Graph{kind: :directed, in_edges: %{}, nodes: %{}, out_edges: %{}}

iex> Yog.Graph.new(:undirected)
%Yog.Graph{kind: :undirected, in_edges: %{}, nodes: %{}, out_edges: %{}}

node_count(graph)

@spec node_count(t()) :: non_neg_integer()

Returns the number of nodes in the graph.

Example

iex> graph = Yog.Graph.new(:directed)
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
iex> Yog.Graph.node_count(graph)
3

iex> graph = Yog.Graph.new(:undirected)
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
iex> Yog.Graph.node_count(graph)
3