classic

Deterministic graph generators for common graph structures.

Deterministic generators produce identical graphs given the same parameters, useful for testing algorithms, benchmarking, and creating known structures.

Available Generators

Generator	Graph Type	Complexity	Edges
`complete`	K_n	O(n²)	n(n-1)/2
`cycle`	C_n	O(n)	n
`path`	P_n	O(n)	n-1
`star`	S_n	O(n)	n-1
`wheel`	W_n	O(n)	2(n-1)
`grid_2d`	Lattice	O(mn)	(m-1)n + m(n-1)
`complete_bipartite`	K_{m,n}	O(mn)	mn
`binary_tree`	Tree	O(2^d)	2^(d+1) - 2
`petersen`	Petersen	O(1)	15
`empty`	Isolated	O(n)	0

Quick Start

import yog/generator/classic
import yog/model

pub fn main() {
  // Classic structures
  let cycle = classic.cycle(5)                    // C5 cycle graph
  let complete = classic.complete(4)              // K4 complete graph
  let grid = classic.grid_2d(3, 4)                // 3x4 lattice mesh
  let tree = classic.binary_tree(3)               // Depth-3 binary tree
  let bipartite = classic.complete_bipartite(3, 4) // K_{3,4}
  let petersen = classic.petersen()               // Famous Petersen graph
}

Use Cases

Algorithm testing: Verify correctness on known structures
Benchmarking: Compare performance across standard graphs
Network modeling: Represent specific topologies (star, grid, tree)
Graph theory: Study properties of well-known graphs

References

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. All edges have unit weight (1).

Time Complexity: O(2^depth)

Example

let tree = classic.binary_tree(3)
// Complete binary tree with depth 3, total 15 nodes

Use Cases

Hierarchical structures
Binary search tree modeling
Heap data structure visualization
Tournament brackets

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)
// K5 has 5 nodes and 10 edges

Use Cases

Testing algorithms on dense graphs
Maximum connectivity scenarios
Clique detection benchmarks

complete_bipartite

</>

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

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

A complete bipartite graph has two disjoint sets of nodes (left and right partitions), where every node in the left partition connects to every node in the right partition. Left partition: nodes 0..(m-1), Right partition: nodes m..(m+n-1).

Time Complexity: O(mn)

Example

let k33 = classic.complete_bipartite(3, 3)
// K_{3,3}: 3 nodes in each partition, 9 edges

Use Cases

Matching problems (job assignment, pairing)
Bipartite graph algorithms
Network flow modeling

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. Each node has degree 2.

Returns an empty graph if n < 3 (cycles require at least 3 nodes).

Time Complexity: O(n)

Example

let c6 = classic.cycle(6)
// C6: 0-1-2-3-4-5-0 (a hexagon)

Use Cases

Ring network topologies
Circular dependency testing
Hamiltonian cycle benchmarks

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 rectangular grid where each node is connected to its orthogonal neighbors (up, down, left, right). Nodes are numbered row by row: node at (r, c) has ID = r * cols + c.

Time Complexity: O(rows * cols)

Example

let grid = classic.grid_2d(3, 4)
// 3x4 grid with 12 nodes
// Node numbering: 0-1-2-3
//                 | | | |
//                 4-5-6-7
//                 | | | |
//                 8-9-10-11

Use Cases

Mesh network topologies
Spatial/grid-based algorithms
Image processing graph models
Game board representations

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 the Petersen graph.

The Petersen graph is a famous undirected graph with 10 nodes and 15 edges. It is often used as a counterexample in graph theory due to its unique properties.

Time Complexity: O(1)

Example

let petersen = classic.petersen()
// 10 nodes, 15 edges

Properties

3-regular (every node has degree 3)
Diameter 2
Not planar
Not Hamiltonian

Use Cases

Graph theory counterexamples
Algorithm testing
Theoretical research

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 combines a star and a cycle: node 0 is the hub, and nodes 1..(n-1) form a cycle.

Returns an empty graph if n < 4 (wheels require at least 4 nodes).

Time Complexity: O(n)

Example

let w6 = classic.wheel(6)
// W6: hub 0 connected to cycle 1-2-3-4-5-1

Use Cases

Hybrid network topologies
Fault-tolerant network design
Routing algorithm benchmarks

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.