gengraph 1.0.0

A library and command line tool to provide different models for consistently generating graphs
Documentation

Random Graph Generation Library

GenGraph is a library and command line tool to provide different models for consistently generating graphs. In addition, an extensive library for sampling discrete elements via arbitrary functions describing probabilities and continues points from an arbitrary dimensional cube via a Reject Sampling-like approach.

We use petgraph as the underlying graph library.

Provided Graph Models

This library provides methods to generate graphs representing certain scenarios and or characteristics. Provided models:

Erdős-Renyi (Random)

This a an implementation of the G(n, m) Erdős-Renyi graph model. The positions of the vertices are drawn uniformly randomly from the specified continues space. example

Coast Line

These graphs are generated based on the idea that cities (vertices) are settled near a coastline (y-axis) and further cities are land inward. The roads (edges) mostly lie along the coastline. Roads to cities inward mostly run perpendicular to the coastline. Connections between land inward cities are build parallel to the coastline.

Properties of the graph:

  • The probability of a vertex decreases with increasing x-coordinate.
  • Disallow vertices near other vertices.
  • Increased probability for a vertex in an area around a vertex with an offset in the x-direction.
  • Edges tend to be short.
  • Edges should not have shallow angles with each other.

For more detailed information about the specific parameters, check coast_line.rs.

To ensure that the graph is planar and connected, this model uses the sampling method described in Section. example

Mountain Valley

In mountain areas, villages are mostly settled in the valleys and less commonly higher up on the mountains. This graph model tries to capture these properties. The roads also mostly run in the valleys while roads across mountains are less likely.

Properties of the graph:

  • Mountains are modelled as truncated cones.
  • The higher up the mountain, the lower the probability of a vertex. Zero probability if the top is reached.
  • No vertex can be near another vertex.
  • The higher up an edge crosses a mountain, the lower its probability.
  • Edges should not have shallow angles with each other.

For more detailed information about the specific parameters, check mountain_valley.rs.

To ensure that the graph is planar and connected, this model uses the sampling method described in Section. example

1-Center

This graph model tries to capture one large city with multiple cities around it. example

2-Center

This graph model tries to capture two large city with multiple cities around it. example

CLI

The CLI tool provides an interface to generate multiple graphs representing one of the above-mentioned scenarios. Use in the project

$ cargo run -- -h

or after installing

$ gengraph -h

for more information about the usage of the CLI tool.

Sampling Library

Density Functions

The probability of an element of a space is given by a function, which we call Density. Contrary to the mathematical definition of a Density Function, we do not require the probabilities to add up to 1 (the integral over the space to be 1 for continues spaces) and that the probabilities must be at most 1. This will be handled by the sampler. In addition, the Density has access to the previously sampled elements, to further adapt its output probability.

This library provides the Density trait that can be combined easily. For 2D sampling spaces and sets of graph edges, a vast amount of different Densitys are implemented. This includes

  • different continues manipulations of the 2D space,
  • different nearest neighbor based Densitys based on the previously sampled elements,
  • Densitys based on the max degree of vertices in a graph,
  • a Denity for the angle between edges of a graph,
  • and a planarity Density on edges

to name a few.

Discrete Space Sampling

For a given space of elements, provide a function that assigns every element a value greater equal zero. The functions values are normalized resulting in a probability distribution for the element space. In addition, the previously sampled elements are given to the function for iterative changing the function. Based on this density elements will be sampled. After sampling an element the probabilities will be recomputed (can be turned off).

Example for a Sneaky Biased Coin

The first 10 tosses true (head) is twice as probable as false (tails).

use gengraph::sampling::{DiscreteSpaceSampler, Sampler};
use rand::rng;

fn main() {
    println!(
        "{} of 100 are head.",
        DiscreteSpaceSampler::new(
            |current: &bool, chosen: &[bool]| {
                if *current && chosen.len() < 10 {
                    1.0
                } else {
                    0.5
                }
            },
            vec![true, false],
        )
        .sample_iter(&mut rng())
        .take(100)
        .filter(|b| *b)
        .count()
    );
}

With the DiscreteSpaceSampler we provide such a sampling process over an arbitrary space of elements. If only unique elements are desired, use the UniqueDiscreteSpaceSampler.

This process gives the bases for vertex and edge sampling process of the Coast Line and Mountain Valley graph sampling process.

Example to Deal a Hand of five Unique Cards

The probability of each card is the same. Note, that we can give a probability of 1.0 instead of chosen.len() as f64 / 52.0 to choose the cards equal probable.

use gengraph::sampling::{Sampler, UniqueDiscreteSpaceSampler};
use itertools::Itertools;
use rand::rng;

fn main() {
    println!(
        "Your hand of five cards: {}",
        UniqueDiscreteSpaceSampler::new(|_: &u8, _: &[u8]| 1.0, (0..52).collect::<Vec<u8>>())
            .sample_iter(rng())
            .take(5)
            .join(",")
    );
}

Continues Space Sampling

Normalizing functions over a continues space requires expensive and complex computations, which we wanted to avoid. Thus, we use a process akin to Reject Sampling. With a given uniform sampler of a continues space and a function over this space, an arbitrary element is kept if the probability of the function is larger than a random number in [0,1].

With the CoutinuesSpaceSampler we provide such a sampling process over an arbitrary dimensional cuconbe.

Sample Distant points from Plane

Samples points from a 4 by 4 plane where the probability of points to be sampled decreases the nearer they are to already sampled points.

use gengraph::{
    model2d::BiasedNearestNeighborDist,
    probability_functions::zero_one_cut_of,
    sampling::{ContinuesSpaceSampler, Sampler},
    Density,
};
use rand::rng;

fn main() {
    ContinuesSpaceSampler::new(
        BiasedNearestNeighborDist::new(1.0, 1.0).chain(zero_one_cut_of),
        [0.0, 0.0],
        [4.0, 4.0],
    )
    .sample_iter(rng());
}

Additional Functionality

Connected and Planar Graphs

Often connected or connected planar graphs are desired. For this purpose, we provide different functions to generate planar connected graphs. First a spanning tree is produced by following Kruskal's algorithm for generating minimum spanning trees. Instead of adding the edge with the minimum edge weight that does not create a cycle, here the edge with the highest probability not creating a cycle is chosen. If the graph should also be planar, edges that would create crossings would also be discarded. During this process the probabilities of the edges is not recomputed based on the previously chosen edges. For graphs in a plane, such a function for checking crossings is already provided.

Visualization

For graphs in a plane (SampleGraph2D), we provide different traits and functions to visualize them via plotpy and therefore matplotlib. These range from simply plotting the graph via the trait VisualizeGraph (and overlaying it with the start contour plot of the probability function with VisualizeContourAndGraphGraph) to visualizing the change of the probability function via contour plots after each sampled vertex with the function visualize_steps.

Example Graph in a Plane

Equal probable vertices on grid where the edges' probability is the inverse Manhatten distance.

use gengraph::Density;
use gengraph::model2d::graph_2d_from;
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = graph_2d_from(
    rand::rng(),
    |_: &[f64; 2], _: &[[f64; 2]]| 1.0, // Vertex probability
    |&([x1, y1], [x2, y2]): &([f64; 2], [f64; 2]), _: &[([f64; 2], [f64; 2])]| 1.0 / ((x1 - x2).abs() + (y1 - y2).abs()), // Probability based on Manhatten distance
    10, // Number vertices
    15, // Number edges
    101, // x-Resolution of the grid from which the nodes are sampled
    101, // y-Resolution of the grid from which the nodes are sampled
    1.0, // Width of the grid
    1.0, // Height of the grid
);

If the graph should be connected.

use gengraph::Density;
use gengraph::model2d::connected_graph_2d_from;
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = connected_graph_2d_from(
    rand::rng(),
    |_: &[f64; 2], _: &[[f64; 2]]| 1.0, // Vertex probability
    |&([x1, y1], [x2, y2]): &([f64; 2], [f64; 2]), _: &[([f64; 2], [f64; 2])]| 1.0 / ((x1 - x2).abs() + (y1 - y2).abs()), // Probability based on Manhatten distance
    10, // Number vertices
    15, // Number edges
    101, // x-Resolution of the grid from which the nodes are sampled
    101, // y-Resolution of the grid from which the nodes are sampled
    1.0, // Width of the grid
    1.0, // Height of the grid
);

If the graph should be connected and planar.

use gengraph::Density;
use gengraph::model2d::planar_connected_graph_2d_from;
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = planar_connected_graph_2d_from(
    rand::rng(),
    |_: &[f64; 2], _: &[[f64; 2]]| 1.0, // Vertex probability
    |&([x1, y1], [x2, y2]): &([f64; 2], [f64; 2]), _: &[([f64; 2], [f64; 2])]| 1.0 / ((x1 - x2).abs() + (y1 - y2).abs()), // Probability based on Manhatten distance
    10, // Number vertices
    15, // Number edges
    101, // x-Resolution of the grid from which the nodes are sampled
    101, // y-Resolution of the grid from which the nodes are sampled
    1.0, // Width of the grid
    1.0, // Height of the grid
);

Example Graph on a Line

This examples generates a graph with 5 vertices and 10 edges whose vertices have integer coordinates in [0, 9]. The vertices are chosen uniformly and edges with shorter length are preferred. The vertices weights are set to () and the edge weights are the absolute difference between the two nodes values.

use gengraph::{sample_graph_from, Density};
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = sample_graph_from(
    rand::rng(),
    (0..10).collect::<Vec<u8>>(),
    5,
    10,
    |_: &u8, _: &[u8]| 1.0, // Vertex probability
    |(x, y): &(u8, u8), _: &[(u8, u8)]| 1.0 / dist(x, y) as f64, // Edge probability
    |_| (), // Vertex weight
    |(x, y): &(u8, u8)| dist(x, y), // Edge weight
);

If you want a guaranteed connected graph, use sample_connected_graph_from.

use gengraph::{sample_connected_graph_from, Density};
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = sample_connected_graph_from(
    rand::rng(),
    (0..10).collect::<Vec<u8>>(),
    5,
    10,
    |_: &u8, _: &[u8]| 1.0,
    |(x, y): &(u8, u8), _: &[(u8, u8)]| 1.0 / dist(x, y) as f64,
    |_| (),
    |(x, y): &(u8, u8)| dist(x, y),
);

If the graph should also be planar, use sample_planar_spanning_graph_from with a provided function for checking for crossing edges.

use gengraph::{sample_planar_spanning_graph_from, Density};
let rng = rand::rng();
let dist = |x: &u8, y: &u8| if x > y {x - y} else {y - x};
let graph = sample_planar_spanning_graph_from(
    rand::rng(),
    (0..10).collect::<Vec<u8>>(),
    5,
    10,
    |_: &u8, _: &Vec<u8>| 1.0,
    |(x, y): &(u8, u8), _: &Vec<(u8, u8)>| 1.0 / dist(x, y) as f64,
    |_| (),
    |(x, y): &(u8, u8)| dist(x, y),
    |(x1, y1), (x2, y2)| {
        x1 < x2 && x2 < y1 && y1 < y2
        || x2 < x1 && x1 < y2 && y2 < y1
        || y1 < y2 && y2 < x1 && x1 < x2
        || y2 < y1 && y1 < x2 && x2 < x1
    },
);

Citation

@software{neugebauer2026gengraph,
    author = {Neugebauer, Aaron},
    title = {GenGraph: A Graph Generation Library},
    url = {https://gitlab2.informatik.uni-wuerzburg.de/aan99ru/gengraph},
    version = {1.0.0},
    year = {2026},
}