Generators Module
Graph generators for creating common graph structures and random network models.
This module provides both deterministic and stochastic graph generators, useful for: - Testing graph algorithms with known structures - Modeling real-world networks - Benchmarking and performance analysis - Generating synthetic datasets
Module Structure
Module |
Type |
Generators |
|---|---|---|
Deterministic |
Complete, Cycle, Path, Star, Wheel, Grid, Binary Tree, Bipartite, Petersen |
|
Stochastic |
Erdős-Rényi (G(n,p) and G(n,m)), Barabási-Albert, Watts-Strogatz, Random Tree |
Quick Start
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: |
|
Classic Generators
Deterministic generators produce identical graphs given the same parameters:
- complete - K_n: Every node connects to every other (O(n²))
- cycle - C_n: Nodes form a ring (O(n))
- path - P_n: Linear chain of nodes (O(n))
- star - S_n: Hub connected to all others (O(n))
- wheel - W_n: Cycle with central hub (O(n))
- grid2D - m×n lattice mesh (O(mn))
- completeBipartite - K_{m,n}: Two complete partitions (O(mn))
- binaryTree - Complete binary tree (O(2^depth))
- petersenGraph - Famous 3-regular graph (O(1))
- emptyGraph - n isolated nodes (O(n))
Random Generators
Stochastic generators use randomness to model real-world networks:
- erdosRenyiGnp - G(n,p): Each edge independently with probability p
- erdosRenyiGnm - G(n,m): Exactly m random edges
- barabasiAlbert - Scale-free via preferential attachment (power-law degree distribution)
- wattsStrogatz - Small-world via ring lattice + rewiring (high clustering, short paths)
- randomTree - Uniformly random spanning tree
References
- Wikipedia: Graph Generators
- NetworkX Documentation
- Erdős-Rényi Model
- Barabási-Albert Model
- Watts-Strogatz Model
namespace Yog
module Generators
from Yog
<summary> Graph generators for creating common graph structures and random network models. This module provides both deterministic and stochastic graph generators, useful for: - Testing graph algorithms with known structures - Modeling real-world networks - Benchmarking and performance analysis - Generating synthetic datasets ## Module Structure | Module | Type | Generators | |--------|------|------------| | `Classic` | Deterministic | Complete, Cycle, Path, Star, Wheel, Grid, Binary Tree, Bipartite, Petersen | | `Random` | Stochastic | Erdős-Rényi (G(n,p) and G(n,m)), Barabási-Albert, Watts-Strogatz, Random Tree | ## Quick Start ```fsharp open Yog.Generators open Yog.Model // Classic deterministic graphs let cycle = Classic.cycle 5 Undirected // C5 cycle graph let complete = Classic.complete 4 Undirected // K4 complete graph let grid = Classic.grid2D 3 4 Undirected // 3x4 grid lattice let tree = Classic.binaryTree 3 Undirected // Depth-3 binary tree let petersen = Classic.petersenGraph Undirected // Famous Petersen graph // Random network models let sparse = Random.erdosRenyiGnp 100 0.05 Undirected // Sparse random let exact = Random.erdosRenyiGnm 50 100 Undirected // Exactly 100 edges let scaleFree = Random.barabasiAlbert 1000 3 Undirected // Scale-free network let smallWorld = Random.wattsStrogatz 100 6 0.1 Undirected // Small-world network let randTree = Random.randomTree 50 Undirected // Random spanning tree ``` ## Classic Generators Deterministic generators produce identical graphs given the same parameters: - **complete** - K_n: Every node connects to every other (O(n²)) - **cycle** - C_n: Nodes form a ring (O(n)) - **path** - P_n: Linear chain of nodes (O(n)) - **star** - S_n: Hub connected to all others (O(n)) - **wheel** - W_n: Cycle with central hub (O(n)) - **grid2D** - m×n lattice mesh (O(mn)) - **completeBipartite** - K_{m,n}: Two complete partitions (O(mn)) - **binaryTree** - Complete binary tree (O(2^depth)) - **petersenGraph** - Famous 3-regular graph (O(1)) - **emptyGraph** - n isolated nodes (O(n)) ## Random Generators Stochastic generators use randomness to model real-world networks: - **erdosRenyiGnp** - G(n,p): Each edge independently with probability p - **erdosRenyiGnm** - G(n,m): Exactly m random edges - **barabasiAlbert** - Scale-free via preferential attachment (power-law degree distribution) - **wattsStrogatz** - Small-world via ring lattice + rewiring (high clustering, short paths) - **randomTree** - Uniformly random spanning tree ## References - [Wikipedia: Graph Generators](https://en.wikipedia.org/wiki/Graph_theory#Graph_generators) - [NetworkX Documentation](https://networkx.org/documentation/stable/reference/generators.html) - [Erdős-Rényi Model](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) - [Barabási-Albert Model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model) - [Watts-Strogatz Model](https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model) </summary>
<summary> Graph generators for creating common graph structures and random network models. This module provides both deterministic and stochastic graph generators, useful for: - Testing graph algorithms with known structures - Modeling real-world networks - Benchmarking and performance analysis - Generating synthetic datasets ## Module Structure | Module | Type | Generators | |--------|------|------------| | `Classic` | Deterministic | Complete, Cycle, Path, Star, Wheel, Grid, Binary Tree, Bipartite, Petersen | | `Random` | Stochastic | Erdős-Rényi (G(n,p) and G(n,m)), Barabási-Albert, Watts-Strogatz, Random Tree | ## Quick Start ```fsharp open Yog.Generators open Yog.Model // Classic deterministic graphs let cycle = Classic.cycle 5 Undirected // C5 cycle graph let complete = Classic.complete 4 Undirected // K4 complete graph let grid = Classic.grid2D 3 4 Undirected // 3x4 grid lattice let tree = Classic.binaryTree 3 Undirected // Depth-3 binary tree let petersen = Classic.petersenGraph Undirected // Famous Petersen graph // Random network models let sparse = Random.erdosRenyiGnp 100 0.05 Undirected // Sparse random let exact = Random.erdosRenyiGnm 50 100 Undirected // Exactly 100 edges let scaleFree = Random.barabasiAlbert 1000 3 Undirected // Scale-free network let smallWorld = Random.wattsStrogatz 100 6 0.1 Undirected // Small-world network let randTree = Random.randomTree 50 Undirected // Random spanning tree ``` ## Classic Generators Deterministic generators produce identical graphs given the same parameters: - **complete** - K_n: Every node connects to every other (O(n²)) - **cycle** - C_n: Nodes form a ring (O(n)) - **path** - P_n: Linear chain of nodes (O(n)) - **star** - S_n: Hub connected to all others (O(n)) - **wheel** - W_n: Cycle with central hub (O(n)) - **grid2D** - m×n lattice mesh (O(mn)) - **completeBipartite** - K_{m,n}: Two complete partitions (O(mn)) - **binaryTree** - Complete binary tree (O(2^depth)) - **petersenGraph** - Famous 3-regular graph (O(1)) - **emptyGraph** - n isolated nodes (O(n)) ## Random Generators Stochastic generators use randomness to model real-world networks: - **erdosRenyiGnp** - G(n,p): Each edge independently with probability p - **erdosRenyiGnm** - G(n,m): Exactly m random edges - **barabasiAlbert** - Scale-free via preferential attachment (power-law degree distribution) - **wattsStrogatz** - Small-world via ring lattice + rewiring (high clustering, short paths) - **randomTree** - Uniformly random spanning tree ## References - [Wikipedia: Graph Generators](https://en.wikipedia.org/wiki/Graph_theory#Graph_generators) - [NetworkX Documentation](https://networkx.org/documentation/stable/reference/generators.html) - [Erdős-Rényi Model](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) - [Barabási-Albert Model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model) - [Watts-Strogatz Model](https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model) </summary>
module Model
from Yog
<summary> Core graph data structures and basic operations for the yog library. This module defines the fundamental `Graph` type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions. </summary>
<summary> Core graph data structures and basic operations for the yog library. This module defines the fundamental `Graph` type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions. </summary>
val cycle: Graph<unit,int>
module Classic
from Yog.Generators
<summary> Deterministic graph generators for classic graph structures. </summary>
<summary> Deterministic graph generators for classic graph structures. </summary>
val cycle: n: int -> kind: GraphType -> Graph<unit,int>
<summary> 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 ```fsharp let c5 = Classic.cycle 5 Undirected // C5: 0-1-2-3-4-0 (a pentagon) ``` ## Use Cases - Ring network topologies - Circular dependency testing - Hamiltonian cycle benchmarks </summary>
<summary> 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 ```fsharp let c5 = Classic.cycle 5 Undirected // C5: 0-1-2-3-4-0 (a pentagon) ``` ## Use Cases - Ring network topologies - Circular dependency testing - Hamiltonian cycle benchmarks </summary>
union case GraphType.Undirected: GraphType
<summary> An undirected graph where edges are bidirectional. </summary>
<summary> An undirected graph where edges are bidirectional. </summary>
val complete: Graph<unit,int>
val complete: n: int -> kind: GraphType -> Graph<unit,int>
<summary> 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 ```fsharp let k5 = Classic.complete 5 Undirected // K5 has 5 nodes and 10 edges ``` ## Use Cases - Testing algorithms on dense graphs - Maximum connectivity scenarios - Clique detection benchmarks </summary>
<summary> 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 ```fsharp let k5 = Classic.complete 5 Undirected // K5 has 5 nodes and 10 edges ``` ## Use Cases - Testing algorithms on dense graphs - Maximum connectivity scenarios - Clique detection benchmarks </summary>
val grid: Graph<unit,int>
val grid2D: rows: int32 -> cols: int32 -> kind: GraphType -> Graph<unit,int>
<summary> Generates a 2D grid graph (lattice) of rows x cols. 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 ```fsharp let grid = Classic.grid2D 3 4 Undirected // 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 </summary>
<summary> Generates a 2D grid graph (lattice) of rows x cols. 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 ```fsharp let grid = Classic.grid2D 3 4 Undirected // 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 </summary>
val tree: Graph<unit,int>
val binaryTree: depth: int -> kind: GraphType -> Graph<unit,int>
<summary> 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 ```fsharp let tree = Classic.binaryTree 3 Undirected // Complete binary tree with depth 3, total 15 nodes ``` ## Use Cases - Hierarchical structures - Binary search tree modeling - Heap data structure visualization - Tournament brackets </summary>
<summary> 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 ```fsharp let tree = Classic.binaryTree 3 Undirected // Complete binary tree with depth 3, total 15 nodes ``` ## Use Cases - Hierarchical structures - Binary search tree modeling - Heap data structure visualization - Tournament brackets </summary>
val petersen: Graph<unit,int>
val petersenGraph: kind: GraphType -> Graph<unit,int>
<summary> Generates the Petersen graph. The [Petersen graph](https://en.wikipedia.org/wiki/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 ```fsharp let petersen = Classic.petersenGraph Undirected // 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 </summary>
<summary> Generates the Petersen graph. The [Petersen graph](https://en.wikipedia.org/wiki/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 ```fsharp let petersen = Classic.petersenGraph Undirected // 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 </summary>
val sparse: Graph<unit,int>
module Random
from Yog.Generators
<summary> Random graph generators for stochastic network models. </summary>
<summary> Random graph generators for stochastic network models. </summary>
val erdosRenyiGnp: n: int -> p: float -> kind: GraphType -> Graph<unit,int>
<summary> Erdős-Rényi G(n, p) model: each edge exists with probability p. Generates a random graph where each possible edge is included independently with probability p. For undirected graphs, each unordered pair is considered once. **Time Complexity:** O(n²) ## Parameters - `n`: Number of nodes - `p`: Edge probability (0.0 to 1.0) - `kind`: Directed or Undirected ## Example ```fsharp // Sparse random graph let sparse = Random.erdosRenyiGnp 100 0.05 Undirected // Dense random graph let dense = Random.erdosRenyiGnp 50 0.8 Directed ``` ## Properties - Expected number of edges: p * n(n-1)/2 (undirected) or p * n(n-1) (directed) - Phase transition at p = 1/n (giant component emerges) ## Use Cases - Random network modeling - Percolation studies - Average-case algorithm analysis </summary>
<summary> Erdős-Rényi G(n, p) model: each edge exists with probability p. Generates a random graph where each possible edge is included independently with probability p. For undirected graphs, each unordered pair is considered once. **Time Complexity:** O(n²) ## Parameters - `n`: Number of nodes - `p`: Edge probability (0.0 to 1.0) - `kind`: Directed or Undirected ## Example ```fsharp // Sparse random graph let sparse = Random.erdosRenyiGnp 100 0.05 Undirected // Dense random graph let dense = Random.erdosRenyiGnp 50 0.8 Directed ``` ## Properties - Expected number of edges: p * n(n-1)/2 (undirected) or p * n(n-1) (directed) - Phase transition at p = 1/n (giant component emerges) ## Use Cases - Random network modeling - Percolation studies - Average-case algorithm analysis </summary>
val exact: Graph<unit,int>
val erdosRenyiGnm: n: int -> m: int -> kind: GraphType -> Graph<unit,int>
<summary> Erdős-Rényi G(n, m) model: exactly m edges are added uniformly at random. Unlike G(n, p) which includes each edge independently with probability p, G(n, m) guarantees exactly m edges in the resulting graph. **Time Complexity:** O(m) expected ## Parameters - `n`: Number of nodes - `m`: Exact number of edges to add - `kind`: Directed or Undirected ## Example ```fsharp // Random graph with 50 nodes and exactly 100 edges let graph = Random.erdosRenyiGnm 50 100 Undirected ``` ## Properties - Exactly m edges (unlike G(n,p) which has expected m edges) - Uniform distribution over all graphs with n nodes and m edges ## Use Cases - Fixed edge count requirements - Random graph benchmarking - Testing with specific densities </summary>
<summary> Erdős-Rényi G(n, m) model: exactly m edges are added uniformly at random. Unlike G(n, p) which includes each edge independently with probability p, G(n, m) guarantees exactly m edges in the resulting graph. **Time Complexity:** O(m) expected ## Parameters - `n`: Number of nodes - `m`: Exact number of edges to add - `kind`: Directed or Undirected ## Example ```fsharp // Random graph with 50 nodes and exactly 100 edges let graph = Random.erdosRenyiGnm 50 100 Undirected ``` ## Properties - Exactly m edges (unlike G(n,p) which has expected m edges) - Uniform distribution over all graphs with n nodes and m edges ## Use Cases - Fixed edge count requirements - Random graph benchmarking - Testing with specific densities </summary>
val scaleFree: Graph<unit,int>
val barabasiAlbert: n: int -> m: int -> kind: GraphType -> Graph<unit,int>
<summary> Barabási-Albert model: creates scale-free networks via preferential attachment. Generates a random graph with a power-law degree distribution (scale-free). New nodes preferentially attach to existing high-degree nodes ("rich get richer"). **Time Complexity:** O(n * m * average_degree) ## Parameters - `n`: Total number of nodes - `m`: Number of edges each new node creates (must be < n) - `kind`: Directed or Undirected ## Example ```fsharp // Scale-free network with 1000 nodes, each connecting to 3 existing nodes let ba = Random.barabasiAlbert 1000 3 Undirected ``` ## Properties - Power-law degree distribution: P(k) ~ k^(-3) - Hub nodes with very high degree - Small-world properties ## Use Cases - Social network modeling - Citation network analysis - Web graph simulation </summary>
<summary> Barabási-Albert model: creates scale-free networks via preferential attachment. Generates a random graph with a power-law degree distribution (scale-free). New nodes preferentially attach to existing high-degree nodes ("rich get richer"). **Time Complexity:** O(n * m * average_degree) ## Parameters - `n`: Total number of nodes - `m`: Number of edges each new node creates (must be < n) - `kind`: Directed or Undirected ## Example ```fsharp // Scale-free network with 1000 nodes, each connecting to 3 existing nodes let ba = Random.barabasiAlbert 1000 3 Undirected ``` ## Properties - Power-law degree distribution: P(k) ~ k^(-3) - Hub nodes with very high degree - Small-world properties ## Use Cases - Social network modeling - Citation network analysis - Web graph simulation </summary>
val smallWorld: Graph<unit,int>
val wattsStrogatz: n: int -> k: int -> p: float -> kind: GraphType -> Graph<unit,int>
<summary> Watts-Strogatz model: small-world network (ring lattice + rewiring). Generates a graph with both high clustering (like regular lattices) and short path lengths (like random graphs). Starts with a ring lattice and rewires edges with probability p. **Time Complexity:** O(n * k) ## Parameters - `n`: Number of nodes (must be >= 3) - `k`: Each node connects to k nearest neighbors (must be even, < n) - `p`: Rewiring probability (0.0 = regular lattice, 1.0 = random) - `kind`: Directed or Undirected ## Example ```fsharp // Small-world network: 100 nodes, 6 neighbors each, 10% rewiring let sw = Random.wattsStrogatz 100 6 0.1 Undirected ``` ## Properties - High clustering coefficient - Short average path length - p=0: regular lattice, p=1: random graph ## Use Cases - Social network modeling (six degrees of separation) - Neural network topology - Epidemic spread modeling </summary>
<summary> Watts-Strogatz model: small-world network (ring lattice + rewiring). Generates a graph with both high clustering (like regular lattices) and short path lengths (like random graphs). Starts with a ring lattice and rewires edges with probability p. **Time Complexity:** O(n * k) ## Parameters - `n`: Number of nodes (must be >= 3) - `k`: Each node connects to k nearest neighbors (must be even, < n) - `p`: Rewiring probability (0.0 = regular lattice, 1.0 = random) - `kind`: Directed or Undirected ## Example ```fsharp // Small-world network: 100 nodes, 6 neighbors each, 10% rewiring let sw = Random.wattsStrogatz 100 6 0.1 Undirected ``` ## Properties - High clustering coefficient - Short average path length - p=0: regular lattice, p=1: random graph ## Use Cases - Social network modeling (six degrees of separation) - Neural network topology - Epidemic spread modeling </summary>
val randTree: Graph<unit,int>
val randomTree: n: int -> kind: GraphType -> Graph<unit,int>
<summary> Generates a uniformly random tree on n nodes. Creates a tree by starting with node 0 and repeatedly connecting new nodes to random nodes already in the tree. This produces a uniform distribution over all labeled trees. **Time Complexity:** O(n²) expected ## Example ```fsharp let tree = Random.randomTree 50 Undirected // Random tree with 50 nodes, 49 edges ``` ## Properties - Exactly n-1 edges (tree property) - Connected - Acyclic - Uniform distribution over all labeled trees ## Use Cases - Random spanning tree generation - Tree algorithm testing - Network topology generation - Phylogenetic tree simulation </summary>
<summary> Generates a uniformly random tree on n nodes. Creates a tree by starting with node 0 and repeatedly connecting new nodes to random nodes already in the tree. This produces a uniform distribution over all labeled trees. **Time Complexity:** O(n²) expected ## Example ```fsharp let tree = Random.randomTree 50 Undirected // Random tree with 50 nodes, 49 edges ``` ## Properties - Exactly n-1 edges (tree property) - Connected - Acyclic - Uniform distribution over all labeled trees ## Use Cases - Random spanning tree generation - Tree algorithm testing - Network topology generation - Phylogenetic tree simulation </summary>