yog/model

Core graph data structures and basic operations for the yog library.

This module defines the fundamental Graph type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions.

Graph Types

Directed Graph: Edges have a direction (one-way relationships)
Undirected Graph: Edges are bidirectional (mutual relationships)

Type Parameters

node_data: The type of data stored at each node (e.g., String, City, Task)
edge_data: The type of data stored on edges, typically weights (e.g., Int, Float)

Quick Start

import yog/model

let assert Ok(graph) =
  model.new(model.Undirected)
  |> model.add_node(1, "Alice")
  |> model.add_node(2, "Bob")
  |> model.add_edge(from: 1, to: 2, with: 10)  // weight = 10

Design Notes

The dual-map representation enables O(1) edge existence checks and O(1) transpose operations, at the cost of increased memory usage and slightly more complex edge updates.

Types

Graph

</>

A simple graph data structure that can be directed or undirected.

node_data: The type of data stored at each node
edge_data: The type of data (usually weight) stored on each edge

pub type Graph(node_data, edge_data) {
  Graph(
    kind: GraphType,
    nodes: dict.Dict(Int, node_data),
    out_edges: dict.Dict(Int, dict.Dict(Int, edge_data)),
    in_edges: dict.Dict(Int, dict.Dict(Int, edge_data)),
  )
}

Constructors

Graph(
  kind: GraphType,
  nodes: dict.Dict(Int, node_data),
  out_edges: dict.Dict(Int, dict.Dict(Int, edge_data)),
  in_edges: dict.Dict(Int, dict.Dict(Int, edge_data)),
)

GraphType

</>

The type of graph: directed or undirected.

pub type GraphType {
  Directed
  Undirected
}

Constructors

```
Directed
```
A directed graph where edges have a direction from source to destination.
```
Undirected
```
An undirected graph where edges are bidirectional.

NodeId

</>

Unique identifier for a node in the graph.

pub type NodeId =
  Int

Values

add_edge

</>

pub fn add_edge(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
) -> Result(Graph(n, e), String)

Adds an edge to the graph with the given weight.

For directed graphs, adds a single edge from src to dst. For undirected graphs, adds edges in both directions.

Returns Error if either endpoint node doesn’t exist in graph.nodes. Use add_edge_ensure to auto-create missing nodes with a default value, or add_node to explicitly add nodes before adding edges.

Example

graph
|> model.add_node(1, "A")
|> model.add_node(2, "B")
|> model.add_edge(from: 1, to: 2, with: 10)
// => Ok(graph)

graph
|> model.add_edge(from: 1, to: 2, with: 10)
// => Error("Node 1 does not exist")

add_edge_ensure

</>

pub fn add_edge_ensure(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
  default default: n,
) -> Graph(n, e)

Ensures both endpoint nodes exist, then adds an edge.

If src or dst is not already in the graph, it is created with the supplied default node data before the edge is added. Nodes that already exist are left unchanged.

Always succeeds and returns a Graph (never fails).

Example

// Nodes 1 and 2 are created automatically with data "unknown"
model.new(model.Directed)
|> model.add_edge_ensure(from: 1, to: 2, with: 10, default: "unknown")

// Existing nodes keep their data; only missing ones get the default
model.new(model.Directed)
|> model.add_node(1, "Alice")
|> model.add_edge_ensure(from: 1, to: 2, with: 5, default: "anon")
// Node 1 is still "Alice", node 2 is "anon"

add_edge_with

</>

pub fn add_edge_with(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
  by by: fn(Int) -> n,
) -> Graph(n, e)

Ensures both endpoint nodes exist using a callback, then adds an edge.

If src or dst is not already in the graph, it is created by calling the by function with the node ID to generate the node data. Nodes that already exist are left unchanged.

Always succeeds and returns a Graph (never fails).

Example

// Nodes 1 and 2 are created automatically with value that's the same as NodeId
model.new(model.Directed)
|> model.add_edge_with(from: 1, to: 2, with: 10, by: fn(x) { x })

// Existing nodes keep their data; only missing ones get the default
model.new(model.Directed)
|> model.add_node(1, "1")
|> model.add_edge_with(from: 1, to: 2, with: 5, by: fn(n) { int.to_string(n) <> ":new" })
// Node 1 is still "1", node 2 is "2:new"

add_edge_with_combine

</>

pub fn add_edge_with_combine(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
  using with_combine: fn(e, e) -> e,
) -> Result(Graph(n, e), String)

Adds an edge, but if an edge already exists between src and dst, it combines the new weight with the existing one using with_combine.

The combine function receives (existing_weight, new_weight) and should return the combined weight.

Returns Error if either endpoint node doesn’t exist in graph.nodes.

Time Complexity: O(1)

Example

let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)
let assert Ok(graph) = model.add_edge_with_combine(graph, from: 1, to: 2, with: 5, using: int.add)
// Edge 1->2 now has weight 15 (10 + 5)

add_edges

</>

pub fn add_edges(
  graph: Graph(n, e),
  edges: List(#(Int, Int, e)),
) -> Result(Graph(n, e), String)

Adds multiple edges to the graph in a single operation.

Fails fast on the first edge that references non-existent nodes. Returns Error if any endpoint node doesn’t exist.

This is more ergonomic than chaining multiple add_edge calls as it only requires unwrapping a single Result.

Example

let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edges([
    #(1, 2, 10),
    #(2, 3, 5),
    #(1, 3, 15),
  ])

add_node

</>

pub fn add_node(
  graph: Graph(n, e),
  id: Int,
  data: n,
) -> Graph(n, e)

Adds a node to the graph with the given ID and data. If a node with this ID already exists, its data will be replaced.

Example

graph
|> model.add_node(1, "Node A")
|> model.add_node(2, "Node B")

add_simple_edges

</>

pub fn add_simple_edges(
  graph: Graph(n, Int),
  edges: List(#(Int, Int)),
) -> Result(Graph(n, Int), String)

Adds multiple simple edges (weight = 1) to the graph.

Fails fast on the first edge that references non-existent nodes. Convenient for unweighted graphs where all edges have weight 1.

Example

let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_simple_edges([
    #(1, 2),
    #(2, 3),
    #(1, 3),
  ])

add_unweighted_edges

</>

pub fn add_unweighted_edges(
  graph: Graph(n, Nil),
  edges: List(#(Int, Int)),
) -> Result(Graph(n, Nil), String)

Adds multiple unweighted edges (weight = Nil) to the graph.

Fails fast on the first edge that references non-existent nodes. Convenient for graphs where edges carry no weight information.

Example

let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_unweighted_edges([
    #(1, 2),
    #(2, 3),
    #(1, 3),
  ])

all_edges

</>

pub fn all_edges(graph: Graph(n, e)) -> List(#(Int, Int, e))

Returns all edges in the graph as triplets #(from, to, weight).

For directed graphs, returns all edges. For undirected graphs, returns each edge only once where from <= to.

all_nodes

</>

pub fn all_nodes(graph: Graph(n, e)) -> List(Int)

Returns all node IDs in the graph. This includes all nodes, even isolated nodes with no edges.

Example

model.new(model.Directed)
|> model.add_node(1, "A")
|> model.add_node(2, "B")
|> model.all_nodes
// => [1, 2]

degree

</>

pub fn degree(graph: Graph(n, e), id: Int) -> Int

Returns the total degree of a node.

For directed graphs, this is the sum of in-degree and out-degree. For undirected graphs, self-loops count as 2.

Time Complexity: O(1)

edge_count

</>

pub fn edge_count(graph: Graph(n, e)) -> Int

Returns the number of edges in the graph.

For undirected graphs, each edge is counted once (the pair {u, v}). For directed graphs, each directed edge (u -> v) is counted once.

Time Complexity: O(V)

Example

let assert Ok(graph) =
  model.new(model.Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)

model.edge_count(graph)
// => 1

edge_data

</>

pub fn edge_data(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
) -> Result(e, Nil)

Gets the weight/data of an edge between two nodes.

from_adjacency_list

</>

pub fn from_adjacency_list(
  graph_type: GraphType,
  adj_list: List(#(Int, List(#(Int, e)))),
) -> Graph(Nil, e)

Creates a graph from an adjacency list #(src, List(#(dst, weight))).

Example

let graph = model.from_adjacency_list(Directed, [#(1, [#(2, 10), #(3, 5)])])

from_edges

</>

pub fn from_edges(
  graph_type: GraphType,
  edges: List(#(Int, Int, e)),
) -> Graph(Nil, e)

Creates a graph from a list of edges #(src, dst, weight).

Example

let graph = model.from_edges(Directed, [#(1, 2, 10), #(2, 3, 5)])

from_unweighted_edges

</>

pub fn from_unweighted_edges(
  graph_type: GraphType,
  edges: List(#(Int, Int)),
) -> Graph(Nil, Nil)

Creates a graph from a list of unweighted edges #(src, dst).

Example

let graph = model.from_unweighted_edges(Directed, [#(1, 2), #(2, 3)])

has_edge

</>

pub fn has_edge(
  graph: Graph(n, e),
  from src: Int,
  to dst: Int,
) -> Bool

Checks if the graph contains an edge between src and dst.

Time Complexity: O(1)

has_node

</>

pub fn has_node(graph: Graph(n, e), id: Int) -> Bool

Checks if the graph contains a node with the given ID.

Time Complexity: O(1)

in_degree

</>

pub fn in_degree(graph: Graph(n, e), id: Int) -> Int

Returns the in-degree of a node.

For undirected graphs, this returns the total degree.

Time Complexity: O(1)

kind

</>

pub fn kind(graph: Graph(n, e)) -> GraphType

Gets the type of the graph (Directed or Undirected).

neighbor_ids

</>

pub fn neighbor_ids(graph: Graph(n, e), id: Int) -> List(Int)

Returns all neighbor node IDs (without weights).

neighbors

</>

pub fn neighbors(graph: Graph(n, e), id: Int) -> List(#(Int, e))

Gets everyone connected to the node, regardless of direction. Useful for algorithms like finding “connected connectivity.”

Example

let assert Ok(graph) =
  model.new(model.Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 10)
  |> model.add_edge(from: 3, to: 1, with: 5)

model.neighbors(graph, 1)
// => [#(2, 10), #(3, 5)]

new

</>

pub fn new(graph_type: GraphType) -> Graph(n, e)

Creates a new empty graph of the specified type.

Example

let graph = model.new(Directed)

node

</>

pub fn node(graph: Graph(n, e), id: Int) -> Result(n, Nil)

Gets the data associated with a node.

node_count

</>

pub fn node_count(graph: Graph(n, e)) -> Int

Returns the number of nodes in the graph. Equivalent to order(graph).

Time Complexity: O(1)

Example

model.new(model.Directed)
|> model.add_node(1, "A")
|> model.add_node(2, "B")
|> model.node_count
// => 2

nodes

</>

pub fn nodes(graph: Graph(n, e)) -> dict.Dict(Int, n)

Returns all nodes data in the graph as a Dict.

order

</>

pub fn order(graph: Graph(n, e)) -> Int

Returns the number of nodes in the graph (graph order).

Time Complexity: O(1)

Example

model.new(model.Directed)
|> model.add_node(1, "A")
|> model.add_node(2, "B")
|> model.order
// => 2

out_degree

</>

pub fn out_degree(graph: Graph(n, e), id: Int) -> Int

Returns the out-degree of a node.

For undirected graphs, this returns the total degree.

Time Complexity: O(1)

predecessor_ids

</>

pub fn predecessor_ids(graph: Graph(n, e), id: Int) -> List(Int)

Returns all predecessor node IDs (without weights).

predecessors

</>

pub fn predecessors(
  graph: Graph(n, e),
  id: Int,
) -> List(#(Int, e))

Gets nodes you came FROM (Predecessors).

Example

let assert Ok(graph) =
  model.new(model.Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)

model.predecessors(graph, 2)
// => [#(1, 10)]

remove_edge

</>

pub fn remove_edge(
  graph: Graph(node_data, edge_data),
  src: Int,
  dst: Int,
) -> Graph(node_data, edge_data)

Removes a directed edge from src to dst.

For directed graphs, this removes the single directed edge from src to dst. For undirected graphs, this removes the edges in both directions (from src to dst and from dst to src).

Time Complexity: O(1)

Example

// Directed graph - removes single directed edge
let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)
let graph = model.remove_edge(graph, 1, 2)
// Edge 1->2 is removed

remove_node

</>

pub fn remove_node(graph: Graph(n, e), id: Int) -> Graph(n, e)

Removes a node and all its connected edges (incoming and outgoing).

Time Complexity: O(deg(v)) - proportional to the number of edges connected to the node, not the whole graph.

Example

let assert Ok(graph) =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edges([#(1, 2, 10), #(2, 3, 20)])

let graph = model.remove_node(graph, 2)
// Node 2 is removed, along with edges 1->2 and 2->3

successor_ids

</>

pub fn successor_ids(graph: Graph(n, e), id: Int) -> List(Int)

Returns all successor node IDs (without weights). Convenient for traversal algorithms that only need the IDs.

Example

let assert Ok(graph) =
  model.new(model.Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)

model.successor_ids(graph, 1)
// => [2]

successors

</>

pub fn successors(graph: Graph(n, e), id: Int) -> List(#(Int, e))

Gets nodes you can travel TO (Successors).

Example

let assert Ok(graph) =
  model.new(model.Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_edge(from: 1, to: 2, with: 10)

model.successors(graph, 1)
// => [#(2, 10)]