classic

Deterministic graph generators for common graph structures.

Example

import yog/generators/classic

pub fn main() {
  // Generate a cycle graph with 5 nodes
  let cycle = classic.cycle(5)

  // Generate a complete graph with 4 nodes
  let complete = classic.complete(4)

  // Generate a binary tree of depth 3
  let tree = classic.binary_tree(3)
}

Values

binary_tree

</>

pub fn binary_tree(depth: Int) -> model.Graph(Nil, Int)

Generates a complete binary tree of given depth.

Node 0 is the root. For node i: left child is 2i+1, right child is 2i+2. Total nodes: 2^(depth+1) - 1.

Time Complexity: O(2^depth)

Example

let tree = classic.binary_tree(3)

binary_tree_with_type

</>

pub fn binary_tree_with_type(
  depth: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a complete binary tree with specified graph type.

complete

</>

pub fn complete(n: Int) -> model.Graph(Nil, Int)

Generates a complete graph K_n where every node connects to every other.

In a complete graph with n nodes, there are n(n-1)/2 edges for undirected graphs and n(n-1) edges for directed graphs. All edges have unit weight (1).

Time Complexity: O(n²)

Example

let k5 = classic.complete(5)

complete_bipartite

</>

pub fn complete_bipartite(
  m: Int,
  n: Int,
) -> model.Graph(Nil, Int)

Generates a complete bipartite graph K_{m,n}.

Time Complexity: O(mn)

Example

let k33 = classic.complete_bipartite(3, 3)

complete_bipartite_with_type

</>

pub fn complete_bipartite_with_type(
  m: Int,
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a complete bipartite graph with specified graph type.

complete_with_type

</>

pub fn complete_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a complete graph with specified graph type.

Example

let directed_k4 = generate.complete_with_type(4, model.Directed)

cycle

</>

pub fn cycle(n: Int) -> model.Graph(Nil, Int)

Generates a cycle graph C_n where nodes form a ring.

A cycle graph connects n nodes in a circular pattern: 0 -> 1 -> 2 -> … -> (n-1) -> 0. All edges have unit weight (1).

Time Complexity: O(n)

Example

let c6 = classic.cycle(6)

cycle_with_type

</>

pub fn cycle_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a cycle graph with specified graph type.

empty

</>

pub fn empty(n: Int) -> model.Graph(Nil, Int)

Generates an empty graph with n nodes and no edges.

Time Complexity: O(n)

Example

let empty = classic.empty(10)

empty_with_type

</>

pub fn empty_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates an empty graph with specified graph type.

grid_2d

</>

pub fn grid_2d(rows: Int, cols: Int) -> model.Graph(Nil, Int)

Generates a 2D grid graph (lattice).

Creates a grid of rows × cols nodes arranged in a rectangular lattice. Node IDs are assigned row-major: node_id = row * cols + col.

Time Complexity: O(rows * cols)

Example

let grid = classic.grid_2d(3, 4)

grid_2d_with_type

</>

pub fn grid_2d_with_type(
  rows: Int,
  cols: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a 2D grid graph with specified graph type.

path

</>

pub fn path(n: Int) -> model.Graph(Nil, Int)

Generates a path graph P_n where nodes form a linear chain.

Time Complexity: O(n)

Example

let p5 = classic.path(5)

path_with_type

</>

pub fn path_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a path graph with specified graph type.

petersen

</>

pub fn petersen() -> model.Graph(Nil, Int)

Generates a Petersen graph.

The Petersen graph has 10 nodes and 15 edges.

Time Complexity: O(1)

Example

let petersen = classic.petersen()

petersen_with_type

</>

pub fn petersen_with_type(
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a Petersen graph with specified graph type.

star

</>

pub fn star(n: Int) -> model.Graph(Nil, Int)

Generates a star graph where one central node is connected to all others.

Node 0 is the center, connected to nodes 1 through n-1. All edges have unit weight (1).

Time Complexity: O(n)

Example

let s6 = classic.star(6)

star_with_type

</>

pub fn star_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a star graph with specified graph type.

wheel

</>

pub fn wheel(n: Int) -> model.Graph(Nil, Int)

Generates a wheel graph: a cycle with a central hub.

A wheel graph is a cycle of n-1 nodes with an additional central node connected to all nodes in the cycle. Node 0 is the center.

Time Complexity: O(n)

Example

let w6 = classic.wheel(6)

wheel_with_type

</>

pub fn wheel_with_type(
  n: Int,
  graph_type: model.GraphType,
) -> model.Graph(Nil, Int)

Generates a wheel graph with specified graph type.