yog - v3.1.0

yog

Yog - A comprehensive graph algorithm library for Gleam.

Provides efficient implementations of classic graph algorithms with a clean, functional API.

Quick Start

import yog
import yog/pathfinding/dijkstra as pathfinding
import gleam/int

pub fn main() {
  let graph =
    yog.directed()
    |> yog.add_node(1, "Start")
    |> yog.add_node(2, "Middle")
    |> yog.add_node(3, "End")
    |> yog.add_edge(from: 1, to: 2, with: 5)
    |> yog.add_edge(from: 2, to: 3, with: 3)
    |> yog.add_edge(from: 1, to: 3, with: 10)

  case pathfinding.shortest_path(
    in: graph,
    from: 1,
    to: 3,
    with_zero: 0,
    with_add: int.add,
    with_compare: int.compare
  ) {
    Some(path) -> {
      // Path(nodes: [1, 2, 3], total_weight: 8)
      io.println("Shortest path found!")
    }
    None -> io.println("No path exists")
  }
}

Modules

Core

Algorithms

Data Structures

Transformations

Visualization

Features

Types

Graph

</> 
pub type Graph(node_data, edge_data) =
  model.Graph(node_data, edge_data)

GraphType

</> 
pub type GraphType =
  model.GraphType

NodeId

</> 
pub type NodeId =
  Int

Order

</> 
pub type Order =
  traversal.Order

WalkControl

</> 
pub type WalkControl =
  traversal.WalkControl

WalkMetadata

</> 
pub type WalkMetadata(nid) =
  traversal.WalkMetadata(nid)

Values

add_edge

</> 
pub fn add_edge(
  graph: model.Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
) -> model.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
|> yog.add_edge(from: 1, to: 2, with: 10)

add_edge_ensured

</> 
pub fn add_edge_ensured(
  graph: model.Graph(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
  default default: n,
) -> model.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. Existing nodes are left unchanged.

Example

yog.directed()
|> yog.add_edge_ensured(from: 1, to: 2, with: 10, default: "anon")
// Nodes 1 and 2 are auto-created with data "anon"

add_node

</> 
pub fn add_node(
  graph: model.Graph(n, e),
  id: Int,
  data: n,
) -> model.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
|> yog.add_node(1, "Node A")
|> yog.add_node(2, "Node B")

add_simple_edge

</> 
pub fn add_simple_edge(
  graph: model.Graph(n, Int),
  from src: Int,
  to dst: Int,
) -> model.Graph(n, Int)

Adds a simple edge with weight 1.

This is a convenience function for graphs with integer weights where a default weight of 1 is appropriate (e.g., unweighted graphs, hop counts).

Example

graph
|> yog.add_simple_edge(from: 1, to: 2)
|> yog.add_simple_edge(from: 2, to: 3)
// Both edges have weight 1

add_unweighted_edge

</> 
pub fn add_unweighted_edge(
  graph: model.Graph(n, Nil),
  from src: Int,
  to dst: Int,
) -> model.Graph(n, Nil)

Adds an unweighted edge to the graph.

This is a convenience function for graphs where edges have no meaningful weight. Uses Nil as the edge data type.

Example

let graph: Graph(String, Nil) = yog.directed()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_unweighted_edge(from: 1, to: 2)

all_nodes

</> 
pub fn all_nodes(graph: model.Graph(n, e)) -> List(Int)

Returns all unique node IDs that have edges in the graph.

breadth_first

</> 
pub const breadth_first: traversal.Order

complement

</> 
pub fn complement(
  graph: model.Graph(n, e),
  default_weight default_weight: e,
) -> model.Graph(n, e)

continue

</> 
pub const continue: traversal.WalkControl

contract

</> 
pub fn contract(
  in graph: model.Graph(n, e),
  merge a: Int,
  with b: Int,
  combine_weights with_combine: fn(e, e) -> e,
) -> model.Graph(n, e)

depth_first

</> 
pub const depth_first: traversal.Order

directed

</> 
pub fn directed() -> model.Graph(n, e)

Creates a new empty directed graph.

This is a convenience function that’s equivalent to yog.new(Directed), but requires only a single import.

Example

import yog

let graph =
  yog.directed()
  |> yog.add_node(1, "Start")
  |> yog.add_node(2, "End")
  |> yog.add_edge(from: 1, to: 2, with: 10)

filter_edges

</> 
pub fn filter_edges(
  graph: model.Graph(n, e),
  keeping predicate: fn(Int, Int, e) -> Bool,
) -> model.Graph(n, e)

filter_nodes

</> 
pub fn filter_nodes(
  graph: model.Graph(n, e),
  keeping predicate: fn(n) -> Bool,
) -> model.Graph(n, e)

fold_walk

</> 
pub fn fold_walk(
  over graph: model.Graph(n, e),
  from start: Int,
  using order: traversal.Order,
  initial acc: a,
  with folder: fn(a, Int, traversal.WalkMetadata(Int)) -> #(
    traversal.WalkControl,
    a,
  ),
) -> a

from_adjacency_list

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

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

Example

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

from_edges

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

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

Example

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

from_unweighted_edges

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

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

Example

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

halt

</> 
pub const halt: traversal.WalkControl

is_acyclic

</> 
pub fn is_acyclic(graph: model.Graph(n, e)) -> Bool

Determines if a graph is acyclic (contains no cycles).

This is the logical opposite of is_cyclic. For directed graphs, returning True means the graph is a Directed Acyclic Graph (DAG).

Time Complexity: O(V + E)

Example

yog.is_acyclic(graph)
// => True // Valid DAG or undirected forest

is_cyclic

</> 
pub fn is_cyclic(graph: model.Graph(n, e)) -> Bool

Determines if a graph contains any cycles.

For directed graphs, a cycle exists if there is a path from a node back to itself. For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself, or a self-loop.

Time Complexity: O(V + E)

Example

yog.is_cyclic(graph)
// => True // Cycle detected

map_edges

</> 
pub fn map_edges(
  graph: model.Graph(n, e),
  with fun: fn(e) -> f,
) -> model.Graph(n, f)

map_nodes

</> 
pub fn map_nodes(
  graph: model.Graph(n, e),
  with fun: fn(n) -> m,
) -> model.Graph(m, e)

merge

</> 
pub fn merge(
  base: model.Graph(n, e),
  other: model.Graph(n, e),
) -> model.Graph(n, e)

neighbors

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

Gets all nodes connected to the given node, regardless of direction. For undirected graphs, this is equivalent to successors. For directed graphs, this combines successors and predecessors.

new

</> 
pub fn new(graph_type: model.GraphType) -> model.Graph(n, e)

Creates a new empty graph of the specified type.

Example

import yog
import yog/model.{Directed}

let graph = yog.new(Directed)

predecessors

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

Gets nodes you came FROM to reach the given node (predecessors). Returns a list of tuples containing the source node ID and edge data.

stop

</> 
pub const stop: traversal.WalkControl

subgraph

</> 
pub fn subgraph(
  graph: model.Graph(n, e),
  keeping ids: List(Int),
) -> model.Graph(n, e)

successor_ids

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

Returns just the NodeIds of successors (without edge data). Convenient for traversal algorithms that only need the IDs.

successors

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

Gets nodes you can travel TO from the given node (successors). Returns a list of tuples containing the destination node ID and edge data.

to_directed

</> 
pub fn to_directed(graph: model.Graph(n, e)) -> model.Graph(n, e)

to_undirected

</> 
pub fn to_undirected(
  graph: model.Graph(n, e),
  resolve resolve: fn(e, e) -> e,
) -> model.Graph(n, e)

transpose

</> 
pub fn transpose(graph: model.Graph(n, e)) -> model.Graph(n, e)

undirected

</> 
pub fn undirected() -> model.Graph(n, e)

Creates a new empty undirected graph.

This is a convenience function that’s equivalent to yog.new(Undirected), but requires only a single import.

Example

import yog

let graph =
  yog.undirected()
  |> yog.add_node(1, "A")
  |> yog.add_node(2, "B")
  |> yog.add_edge(from: 1, to: 2, with: 5)

walk

</> 
pub fn walk(
  in graph: model.Graph(n, e),
  from start_id: Int,
  using order: traversal.Order,
) -> List(Int)

walk_until

</> 
pub fn walk_until(
  in graph: model.Graph(n, e),
  from start_id: Int,
  using order: traversal.Order,
  until should_stop: fn(Int) -> Bool,
) -> List(Int)
✨ Search Document