Yog.Graph (YogEx v0.70.0)

Copy Markdown View Source

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

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() :: integer()

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

new(kind)

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

Creates a new empty graph of the given type.

node_count(graph)

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

Returns the number of nodes in the graph.