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.

Example

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

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