yog/model

Types

Graph

A 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,
) -> Graph(n, e)

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.

Note: If src or dst have not been added via add_node, the edge will still be created in the edge dictionaries but the nodes will be missing from graph.nodes. This creates “ghost nodes” that are traversable but invisible to functions that iterate over nodes (e.g. order, filter_nodes). Use add_edge_ensured to auto-create missing endpoints with a default value.

Example

graph
|> model.add_edge(from: 1, to: 2, with: 10)

add_edge_ensured

</>

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

Like add_edge, but ensures both endpoint nodes exist first.

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.

Example

// Nodes 1 and 2 are created automatically with data "unknown"
model.new(model.Directed)
|> model.add_edge_ensured(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_ensured(from: 1, to: 2, with: 5, default: "anon")
// Node 1 is still "Alice", node 2 is "anon"

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,
) -> Graph(n, e)

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.

Time Complexity: O(1)

Example

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

Use Cases

Edge contraction in graph algorithms (Stoer-Wagner min-cut)
Multi-graph support (adding parallel edges with combined weights)
Incremental graph building (accumulating weights from multiple sources)

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

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.

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 components.”

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)

order

</>

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

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

Time Complexity: O(1)

predecessors

</>

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

Gets nodes you came FROM (Predecessors).

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 graph =
  model.new(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: 2, to: 3, with: 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 just the NodeIds of successors (without edge weights). Convenient for traversal algorithms that only need the IDs.

successors

</>

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

Gets nodes you can travel TO (Successors).