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

Generates a complete binary tree with specified graph type.

Generates the book graph B_n.

The book graph consists of n triangles (or 4-cycles in some definitions) all sharing a common edge (the “spine”).

Example

let book = classic.book(3)
// B_3 has 5 nodes (2 spine + 3 page vertices)
// B_3 has 7 edges

Properties

• Vertices: n + 2 (2 spine vertices + n page vertices)
• Edges: 2n + 1 (n triangles sharing the spine edge)
• Planar
• Outerplanar

Use Cases

• Graph drawing and book embeddings
• Outerplanar graph studies
• Pagenumber of graphs

Generates a book graph with specified graph type.

Generates a caterpillar tree.

A caterpillar is a tree where removing all leaves leaves a path (the “spine”).

Options

• n - Total number of nodes
• spine_length - Length of central path (default: max(1, n/3))

Example

let cat = classic.caterpillar(20, spine_length: 5)
// Caterpillar with 20 nodes, 5 nodes on spine

Properties

• All vertices are within distance 1 of the central path
• Interpolates between paths (spine_length = n) and stars (spine_length = 1)

Generates a caterpillar tree with specified graph type.

Generates a circular ladder graph (prism graph) with n rungs.

The circular ladder CL_n consists of two concentric n-cycles with corresponding vertices connected by rungs. It’s equivalent to the Cartesian product C_n × K_2 (cycle × edge).

Example

let cl = classic.circular_ladder(5)
// CL_5 has 10 nodes

// CL_4 is the cube graph (isomorphic to hypercube(3))
let cl4 = classic.circular_ladder(4)

Properties

• Vertices: 2n
• Edges: 3n (2n cycle edges + n rungs)
• 3-regular (cubic) for n > 2
• Planar (can be drawn on a cylinder)
• Hamiltonian
• Bipartite when n is even

Use Cases

• Prism graphs in chemistry (molecular structures)
• Network topologies with wraparound
• Topological graph theory (cylindrical embeddings)

Generates a circular ladder graph with specified graph type.

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

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

Generates a complete bipartite graph with specified graph type.

Generates a complete m-ary tree with exactly n nodes.

Creates a tree that is as complete as possible - all levels are fully filled except possibly the last, which is filled from left to right.

Options

• n - Number of nodes
• arity - Branching factor (default: 2)

Example

let tree = classic.complete_kary(20, arity: 3)
// Complete 3-ary tree with 20 nodes

Generates a complete m-ary tree with specified graph type.

Generates a complete graph with specified graph type.

Example

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

Generates the crown graph S_n^0 with 2n vertices.

The crown graph is the complete bipartite graph K_{n,n} minus a perfect matching. It has important applications in edge coloring and extremal graph theory.

Example

let crown = classic.crown(4)
// S_4^0 has 8 nodes
// S_4^0 has 12 edges (16 - 4)

// crown(2) is C_4 (cycle on 4 vertices)
let c2 = classic.crown(2)

Properties

• Vertices: 2n
• Edges: n(n-1) = n² - n
• (n-1)-regular (each vertex has degree n-1)
• Bipartite
• Diameter: 3 for n ≥ 3
• Girth: 4 for n ≥ 3

Special Cases

• crown(2) = C₄ (4-cycle)
• crown(3) is the utility graph (K_{3,3} minus a perfect matching)

Use Cases

• Edge coloring tests (chromatic index demonstrations)
• Extremal graph theory examples
• Bipartite graph testing with symmetric structure

Generates a crown graph with specified graph type.

Generates the cube graph Q₃ (3-dimensional hypercube).

The cube has 8 vertices and 12 edges. Each vertex has degree 3. It is bipartite, planar, and is the 3D hypercube.

Example

let cube = classic.cube()
// Cube has 8 nodes and 12 edges

Properties

• Vertices: 8
• Edges: 12
• Degree: 3 (regular)
• Diameter: 3
• Girth: 4
• Chromatic number: 2 (bipartite)

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

Generates a cycle graph with specified graph type.

Generates the dodecahedron graph.

The dodecahedron has 20 vertices and 30 edges. Each vertex has degree 3. Famous as the basis of Hamilton’s “Icosian game” and Hamiltonian cycle puzzles. It has girth 5 (smallest cycle has 5 edges).

Example

let dodec = classic.dodecahedron()
// Dodecahedron has 20 nodes and 30 edges

Properties

• Vertices: 20
• Edges: 30
• Degree: 3 (regular)
• Diameter: 5
• Girth: 5
• Chromatic number: 3

Generates an empty graph with n nodes and no edges.

Time Complexity: O(n)

Example

let empty = classic.empty(10)

Generates an empty graph with specified graph type.

Generates the friendship graph F_n with n triangles.

The friendship graph consists of n triangles all sharing a common vertex. Also known as the Dutch windmill graph.

Famous for the Friendship Theorem: if every pair of vertices in a finite graph has exactly one common neighbor, then the graph must be a friendship graph.

Example

let f3 = classic.friendship(3)
// F_3 has 7 nodes (1 center + 6 outer)
// F_3 has 9 edges (3 triangles)

Properties

• Vertices: 2n + 1 (1 center + 2n outer vertices)
• Edges: 3n (n triangles, each with 3 edges)
• Center has degree 2n, outer vertices have degree 2
• Chromatic number: 3
• Diameter: 2, Radius: 1
• Planar

Use Cases

• Graph theory education (Friendship Theorem)
• Testing graphs with specific local properties
• Social network models (hub with triadic closure)

Generates a friendship graph with specified graph type.

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

Generates a 2D grid graph with specified graph type.

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)

Example

let cube = classic.hypercube(3)
// 3-cube has 8 nodes, each with degree 3

Use Cases

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

Generates a hypercube graph with specified graph type.

Generates the icosahedron graph.

The icosahedron has 12 vertices and 30 edges. Each vertex has degree 5. It is the dual of the dodecahedron.

Example

let icosa = classic.icosahedron()
// Icosahedron has 12 nodes and 30 edges

Properties

• Vertices: 12
• Edges: 30
• Degree: 5 (regular)
• Diameter: 3
• Girth: 3
• Chromatic number: 4

Generates a complete k-ary tree of given depth.

A complete k-ary tree where each node has exactly k children (except leaves). Total nodes = (k^(depth+1) - 1) / (k - 1) for k > 1. For k = 1, this is a path with depth+1 nodes.

Options

• depth - The depth of the tree (root is at depth 0)
• arity - The branching factor k (default: 2, binary tree)

Example

// Ternary tree (arity 3) of depth 2
let tree = classic.kary_tree(2, arity: 3)
// 1 + 3 + 9 = 13 nodes

Properties

• Node i has parent at (i-1)/k
• Node i has children at ki+1 through ki+k

Generates a k-ary tree with specified graph type.

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)

Example

let ladder = classic.ladder(4)
// 4-rung ladder has 8 nodes

Use Cases

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

Generates a ladder graph with specified graph type.

Generates a Möbius ladder graph with n rungs.

The Möbius ladder ML_n is formed from a circular ladder by giving it a half-twist before connecting the ends, creating a Möbius strip topology.

Example

let ml = classic.mobius_ladder(6)
// ML_6 has 12 nodes

// ML_4 is K_{3,3} (complete bipartite graph)
let ml4 = classic.mobius_ladder(4)

Properties

• Vertices: 2n
• Edges: 3n
• 3-regular (cubic)
• Non-planar for n ≥ 3
• ML_4 = K_{3,3} (canonical non-planar graph)
• ML_3 = 6-vertex utility graph (K_{3,3} minus an edge)
• Bipartite when n is odd

Use Cases

• Non-orientable embeddings in topological graph theory
• Planarity testing (contains K_{3,3} minor)
• Chemical graph theory (Möbius molecules)
• Network design with twisted topology

Generates a Möbius ladder graph with specified graph type.

Generates the octahedron graph.

The octahedron has 6 vertices and 12 edges. Each vertex has degree 4. It is the dual of the cube.

Example

let octa = classic.octahedron()
// Octahedron has 6 nodes and 12 edges

Properties

• Vertices: 6
• Edges: 12
• Degree: 4 (regular)
• Diameter: 2
• Girth: 3
• Chromatic number: 3

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

Time Complexity: O(n)

Example

let p5 = classic.path(5)

Generates a path graph with specified graph type.

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

Generates a Petersen graph with specified graph type.

Alias for circular_ladder/1.

The n-sided prism graph is exactly the circular ladder CL_n.

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)

Generates a star graph with specified graph type.

Generates the tetrahedron graph K₄.

The tetrahedron is the simplest Platonic solid with 4 vertices and 6 edges. Each vertex has degree 3. It is a complete graph K₄.

Example

let tetra = classic.tetrahedron()
// Tetrahedron has 4 nodes and 6 edges

Properties

• Vertices: 4
• Edges: 6
• Degree: 3 (regular)
• Diameter: 1
• Girth: 3
• Chromatic number: 4

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

Example

let turan = classic.turan(10, 3)
// T(10, 3) has 10 nodes with balanced partitions: 4, 3, 3

// T(n, 2) is the complete bipartite graph
let k33 = classic.turan(6, 2)

Use Cases

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

Generates a Turán graph with specified graph type.

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

Generates a wheel graph with specified graph type.

Generates the windmill graph W_n^{(k)}.

Generalization of the friendship graph where n copies of K_k (complete graph on k vertices) share a common vertex. The friendship graph is W_n^{(3)}.

Options

• n - Number of cliques
• clique_size - Size k of the cliques (default: 3)

Example

// Windmill of 4 triangles (same as friendship(4))
let w4 = classic.windmill(4, clique_size: 3)

// Windmill of 3 squares (4-cliques sharing a vertex)
let w3_4 = classic.windmill(3, clique_size: 4)

Properties

• Vertices: 1 + n(k-1)
• Edges: n × C(k,2) = n × k(k-1)/2
• Center has degree n(k-1)

Use Cases

• Generalized friendship graphs
• Intersection graph theory
• Clique decomposition studies

Generates a windmill graph with specified graph type.