Skip to content

Module: simulate

File: src/spatial_graph_algorithms/simulate/ Status: Stable.

Purpose

Generate synthetic SpatialGraph objects with known ground truth positions. Used for algorithm benchmarking, testing, and method development.

The public entry point is generate(). Everything else is internal.

Internal Structure

simulate/
├── __init__.py     — generate() + list_shapes() + _validate_inputs()
├── generation.py   — point cloud sampling per shape
├── graphs.py       — edge construction per mode
└── false_edges.py  — noise injection

generate() orchestrates three steps:

generate_points(shape)  →  build_edges(mode)  →  inject_false_edges(fraction)
        ↓                        ↓                          ↓
  positions array          set of edges              all_edges + false_edges set
                                ↓
                      SpatialGraph(adjacency, positions, edge_metadata)

Shapes

Name Dim How it works
circle 2D Rejection sampling inside unit disk
square 2D Uniform random in [0, scale]²
sphere 3D Rejection sampling inside unit sphere
cube 3D Uniform random in [0, scale]³
image / image_2d 2D Sample from black pixels of a binary image (requires image_path)
any name in list_shapes() 2D Auto-resolved bundled image (e.g. "star", "ring", "triangle")

Built-in named shapes

The package ships 18 shape images bundled as package data (in src/spatial_graph_algorithms/data/shapes/). Pass any name directly as the shape argument — no image_path needed:

from spatial_graph_algorithms.simulate import generate, list_shapes

print(list_shapes())
# ['0', '1', '2', ..., 'circle', 'hole', 'porous', 'ring',
#  'spiral', 'square', 'star', 'triangle']

sg = generate(n=500, shape="star", seed=42)
sg = generate(n=500, shape="ring", seed=42)

Named shapes sample from the black pixels of the corresponding PNG, exactly like shape="image". They require dim=2.

Connectivity Modes

Mode Algorithm When to use
delaunay_corrected Delaunay + prune top 5% longest edges + reconnect Default — most realistic
delaunay Standard Delaunay Mathematically clean, may have long outlier edges
knn k nearest neighbours Controlled average degree
epsilon / epsilon-ball All pairs within radius Controlled local neighbourhood
distance_decay Probabilistic power-law decay Soft spatial structure
knn_bipartite k-NN between two partitions Two-population experiments
epsilon_bipartite Epsilon-ball between two partitions Two-population experiments
lattice Regular grid (4-conn 2D, 6-conn 3D) Baseline / sanity checks

False Edge Injection

inject_false_edges samples random non-existing edges and adds them to the graph. Each injected edge is labelled is_false=True in sg.edge_metadata.

The candidates pool respects bipartite structure: for bipartite graphs, false edges are only drawn between the two partitions. For large sparse graphs, candidates are sampled directly instead of materializing the full non-edge set, so false-edge injection scales to large visualization and denoising fixtures.

Either false_edges_number (exact count) or false_edges_fraction (fraction of true edges) can be set, but not both.

How to Add a New Connectivity Mode

  1. Add a function mode_<name>(positions, ...) -> Set[Edge] in simulate/graphs.py. Return a set of (min(i,j), max(i,j)) tuples.
  2. Add a branch in build_edges() in the same file.
  3. Add the string name to SUPPORTED_MODES in simulate/__init__.py.
  4. Add at least one test in tests/test_simulate_modes.py.

Example skeleton:

def mode_gabriel(positions: np.ndarray) -> Set[Edge]:
    """Return edges from the Gabriel graph."""
    # implement here
    ...

Constraints: - The function must be deterministic given the same positions. - For stochastic modes, accept an rng: np.random.Generator parameter. - Modes must handle n=2 without crashing. - Never add to the edge set after the function returns — inject_false_edges handles noise.

How to Add a New Shape

  1. Add a <name>.png binary image to src/spatial_graph_algorithms/data/shapes/. Black pixels are the valid sampling region.
  2. That's it — generate(shape="<name>") will auto-resolve it.
  3. Add a test in tests/test_simulate.py.

Option B — Programmatic shape

  1. Add a _generate_<name> helper function in simulate/generation.py.
  2. Add a branch in generate_points().
  3. Validate dimension compatibility inside the branch.

Tests

tests/test_simulate.py                — generate() basic contracts
tests/test_simulate_modes.py          — every mode produces valid edges
tests/test_simulate_parameterized_modes.py — modes across n, dim, seed
tests/test_simulate_false_edges.py    — noise injection count and labelling
tests/test_simulate_integration.py    — simulate through full pipeline