Yog.Graph (YogEx v1.0.0)

Copy Markdown View Source

Core graph data structure and protocols.

A graph is represented as a %Yog.Graph{} struct with four primary 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}

Dual-Map Representation

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

  • $\mathcal{O}(1)$ Graph Transpose: Transposing a graph is a simple pointer swap (out_edges ↔ in_edges).
  • Fast Predecessor Queries: Finding incoming edges to a node runs in $\mathcal{O}(\text{in-degree})$ time without scanning the entire graph.
  • Fast Bidirectional Lookups: Instant checking for reverse edges or symmetrical relationships.

Constructor & Mutation Guidelines

Direct struct instantiation (%Yog.Graph{...}) or raw field mutation should generally be avoided in application code to prevent index desynchronization between nodes, out_edges, and in_edges. Use the primary Yog facade or Yog.Model functions to build and manipulate graphs safely.

Protocols

Yog.Graph implements the Enumerable and Inspect protocols:

  • Enumerable: Iterates over nodes as {id, data} tuples.
  • Inspect: Compact representation showing graph kind, node count, and edge count.

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

Examples

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)
iex> Yog.Graph.node_count(graph)
2
iex> Yog.Graph.edge_count(graph)
1

Summary

Types

kind()

Type representing whether a graph is directed or undirected.

node_id()

Type representing the unique identifier for a node.

t()

Type representing the Yog.Graph structure.

Functions

edge_count(graph)

Returns the total number of edges in the graph.

new(kind)

Creates a new empty graph of the given kind (:directed or :undirected).

node_count(graph)

Returns the number of nodes in the graph.

Types

kind()

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

Type representing whether a graph is directed or undirected.

node_id()

@type node_id() :: term()

Type representing the unique identifier for a node.

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()}}
}

Type representing the Yog.Graph structure.

Functions

edge_count(graph)

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

Returns the total number of edges in the graph.

For undirected graphs, each edge is counted once (excluding duplicate mirroring). Self-loops are counted as single edges.

Time Complexity: $\mathcal{O}(V)$

Errors

Examples

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

new(kind)

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

Creates a new empty graph of the given kind (:directed or :undirected).

Errors

Examples

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.

Time Complexity: $\mathcal{O}(1)$

Errors

Examples

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)
iex> Yog.Graph.node_count(graph)
2