@spec binary_tree(integer()) :: Yog.graph()

Generates a binary tree of specified depth.

A complete binary tree where each node (except leaves) has exactly 2 children. Total nodes: 2^(depth+1) - 1

Time Complexity: O(2^depth)

Examples

iex> tree = Yog.Generator.Classic.binary_tree(3)
iex> # Depth-3 binary tree: 1 + 2 + 4 + 8 = 15 nodes
...> Yog.Model.order(tree)
15

Use Cases

• Hierarchical structures
• Decision trees
• Search tree benchmarks

@spec binary_tree_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a binary tree with specified graph type.

@spec complete(integer()) :: Yog.graph()

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

Examples

iex> k5 = Yog.Generator.Classic.complete(5)
iex> Yog.Model.order(k5)
5
iex> # K5 is undirected, each node has 4 neighbors
...> length(Yog.neighbors(k5, 0))
4

Use Cases

• Testing algorithms on dense graphs
• Maximum connectivity scenarios
• Clique detection benchmarks

@spec complete_bipartite(integer(), integer()) :: Yog.graph()

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

In a complete bipartite graph, every node in the first partition connects to every node in the second partition.

Time Complexity: O(mn)

Examples

iex> k34 = Yog.Generator.Classic.complete_bipartite(3, 4)
iex> Yog.Model.order(k34)
7
iex> # First partition nodes (0-2) have degree 4
...> length(Yog.neighbors(k34, 0))
4
iex> # Second partition nodes (3-6) have degree 3
...> length(Yog.neighbors(k34, 3))
3

Use Cases

• Bipartite matching problems
• Assignment problems
• Recommender systems

@spec complete_bipartite_with_type(integer(), integer(), Yog.graph_type()) ::
  Yog.graph()

Generates a complete bipartite graph with specified graph type.

@spec complete_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a complete graph with specified graph type.

Examples

iex> directed_k4 = Yog.Generator.Classic.complete_with_type(4, :directed)
iex> Yog.Model.type(directed_k4)
:directed
iex> Yog.Model.order(directed_k4)
4

@spec cycle(integer()) :: Yog.graph()

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)

Examples

iex> c6 = Yog.Generator.Classic.cycle(6)
iex> Yog.Model.order(c6)
6
iex> # Each node in a cycle has degree 2
...> length(Yog.neighbors(c6, 0))
2

Use Cases

• Ring network topologies
• Circular dependency testing
• Hamiltonian cycle benchmarks

@spec cycle_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a cycle graph with specified graph type.

@spec empty(integer()) :: Yog.graph()

Generates an empty graph with n isolated nodes (no edges).

Time Complexity: O(n)

Examples

iex> empty5 = Yog.Generator.Classic.empty(5)
iex> Yog.Model.order(empty5)
5
iex> # No edges - isolated nodes have degree 0
...> length(Yog.neighbors(empty5, 0))
0

@spec empty_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates an empty graph with specified graph type.

@spec grid_2d(integer(), integer()) :: Yog.graph()

Generates a 2D grid (lattice) graph with specified rows and columns.

Each cell connects to its adjacent neighbors (up, down, left, right).

Time Complexity: O(rows × cols)

Examples

iex> grid = Yog.Generator.Classic.grid_2d(3, 4)
iex> # 3x4 grid has 12 nodes
...> Yog.Model.order(grid)
12
iex> # Corner nodes have degree 2
...> length(Yog.neighbors(grid, 0))
2
iex> # Interior nodes have degree 4
...> length(Yog.neighbors(grid, 5))
4

Use Cases

• Mesh networks
• Image processing
• Spatial simulations

@spec grid_2d_with_type(integer(), integer(), Yog.graph_type()) :: Yog.graph()

Generates a 2D grid with specified graph type.

@spec hypercube(integer()) :: Yog.graph()

Generates an n-dimensional hypercube graph Q_n.

The hypercube is a classic topology where each node represents a binary string of length n, and edges connect nodes that differ in exactly one bit.

Properties:

• Nodes: 2^n
• Edges: n × 2^(n-1)
• Regular degree: n
• Diameter: n
• Bipartite: yes

Time Complexity: O(n × 2^n)

Examples

iex> cube = Yog.Generator.Classic.hypercube(3)
iex> # 3-cube has 8 nodes
...> Yog.Model.order(cube)
8
iex> # Each node has degree 3
...> length(Yog.neighbors(cube, 0))
3
iex> # 3-cube has 12 edges
...> Yog.Model.edge_count(cube)
12

Use Cases

• Distributed systems and parallel computing topologies
• Error-correcting codes
• Testing algorithms on regular, bipartite structures
• Gray code applications

References

• Wikipedia: Hypercube Graph

@spec hypercube_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a hypercube graph with specified graph type.

@spec ladder(integer()) :: Yog.graph()

Generates a ladder graph with n rungs.

A ladder graph consists of two parallel paths (rails) connected by n rungs. It is the Cartesian product of a path P_n and an edge K_2.

Properties:

• Nodes: 2n
• Edges: 3n - 2
• Planar: yes
• Equivalent to grid_2d(2, n)

Time Complexity: O(n)

Examples

iex> ladder = Yog.Generator.Classic.ladder(4)
iex> # 4-rung ladder has 8 nodes
...> Yog.Model.order(ladder)
8
iex> # End nodes have degree 2
...> length(Yog.neighbors(ladder, 0))
2
iex> # Interior nodes have degree 3
...> length(Yog.neighbors(ladder, 2))
3

Use Cases

• Basic network topologies
• DNA and molecular structure modeling
• Pathfinding benchmarks

@spec ladder_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a ladder graph with specified graph type.

@spec path(integer()) :: Yog.graph()

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

A path graph connects n nodes in a line: 0 -> 1 -> 2 -> ... -> (n-1). End nodes have degree 1, interior nodes have degree 2.

Time Complexity: O(n)

Examples

iex> p5 = Yog.Generator.Classic.path(5)
iex> Yog.Model.order(p5)
5
iex> # End nodes have degree 1
...> length(Yog.neighbors(p5, 0))
1
iex> # Middle nodes have degree 2
...> length(Yog.neighbors(p5, 2))
2

Use Cases

• Linear network topologies
• Linked list representations
• Pathfinding benchmarks

@spec path_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a path graph with specified graph type.

@spec petersen() :: Yog.graph()

Generates the Petersen graph - a famous graph in graph theory.

The Petersen graph has 10 nodes, 15 edges, diameter 2, girth 5. It's a common counterexample in graph theory.

Time Complexity: O(1)

Examples

iex> p = Yog.Generator.Classic.petersen()
iex> # Petersen graph has 10 nodes
...> Yog.Model.order(p)
10
iex> # All nodes have degree 3
...> length(Yog.neighbors(p, 0))
3

Properties

• Non-planar
• Non-Hamiltonian
• Vertex-transitive
• Chromatic number 3

@spec petersen_with_type(Yog.graph_type()) :: Yog.graph()

Generates the Petersen graph with specified graph type.

@spec star(integer()) :: Yog.graph()

Generates a star graph S_n with one central hub.

A star graph has one central node (0) connected to all n-1 outer nodes. The center has degree n-1, outer nodes have degree 1.

Time Complexity: O(n)

Examples

iex> s5 = Yog.Generator.Classic.star(5)
iex> Yog.Model.order(s5)
5
iex> # Center (node 0) has degree 4
...> length(Yog.neighbors(s5, 0))
4
iex> # Leaf nodes have degree 1
...> length(Yog.neighbors(s5, 1))
1

Use Cases

• Hub-and-spoke networks
• Client-server architectures
• Broadcast scenarios

@spec star_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a star graph with specified graph type.

@spec turan(integer(), integer()) :: Yog.graph()

Generates the Turán graph T(n, r).

The Turán graph is a complete r-partite graph with n vertices where partitions are as equal as possible. It maximizes the number of edges among all n-vertex graphs that do not contain K_{r+1} as a subgraph.

Properties:

• Complete r-partite with balanced partitions
• Maximum edge count without containing K_{r+1}
• Chromatic number: r (for n >= r)
• Turán's theorem: extremal graph for forbidden cliques

Time Complexity: O(n²)

Examples

iex> turan = Yog.Generator.Classic.turan(10, 3)
iex> # T(10, 3) has 10 nodes
...> Yog.Model.order(turan)
10
iex> # Partition sizes are balanced: 4, 3, 3
iex> # No edges within partitions, all edges between

iex> # T(n, 2) is the complete bipartite graph
...> k33 = Yog.Generator.Classic.turan(6, 2)
...> Yog.Model.order(k33)
6

Use Cases

• Extremal graph theory testing
• Chromatic number benchmarks
• Anti-clique (independence number) studies
• Balanced multi-partite networks

References

• Wikipedia: Turán Graph
• Turán's Theorem

@spec turan_with_type(integer(), integer(), Yog.graph_type()) :: Yog.graph()

Generates a Turán graph with specified graph type.

@spec wheel(integer()) :: Yog.graph()

Generates a wheel graph W_n - a cycle with a central hub.

A wheel graph combines a star and a cycle: center (0) connects to all rim nodes (1..n-1), and rim nodes form a cycle.

Time Complexity: O(n)

Examples

iex> w6 = Yog.Generator.Classic.wheel(6)
iex> Yog.Model.order(w6)
6
iex> # Center has degree 5 (connected to all rim nodes)
...> length(Yog.neighbors(w6, 0))
5
iex> # Rim nodes have degree 3 (center + 2 neighbors in cycle)
...> length(Yog.neighbors(w6, 1))
3

Use Cases

• Wheel network topologies
• Centralized routing with backup paths
• Spoke-hub distribution

@spec wheel_with_type(integer(), Yog.graph_type()) :: Yog.graph()

Generates a wheel graph with specified graph type.