# 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](https://en.wikipedia.org/wiki/Rejection_sampling)-like approach.
We use [petgraph](https://github.com/petgraph/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](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) graph model.
The positions of the vertices are drawn uniformly randomly from the specified continues space.
### *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](src/model2d/coast_line.rs).
To ensure that the graph is planar and connected, this model uses the sampling method described in [Section](#connected-and-planar-graphs).
### *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](src/model2d/mountain_valley.rs).
To ensure that the graph is planar and connected, this model uses the sampling method described in [Section](#connected-and-planar-graphs).
### *1-Center*
This graph model tries to capture one large city with multiple cities around it.
### *2-Center*
This graph model tries to capture two large city with multiple cities around it.
## CLI
The CLI tool provides an interface to generate multiple graphs representing one of the above-mentioned scenarios. Use in the project
```console
$ cargo run -- -h
```
or after installing
```console
$ 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](https://en.wikipedia.org/wiki/Probability_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 `Density`s are implemented.
This includes
- different continues manipulations of the 2D space,
- different nearest neighbor based `Density`s based on the previously sampled elements,
- `Density`s 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).
```rust
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.
```rust
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](https://en.wikipedia.org/wiki/Rejection_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.
```rust
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](https://en.wikipedia.org/wiki/Kruskal%27s_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](https://github.com/cpmech/plotpy) and therefore [matplotlib](https://matplotlib.org).
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.
```rust
use gengraph::Density;
use gengraph::model2d::graph_2d_from;
let rng = rand::rng();
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.
```rust
use gengraph::Density;
use gengraph::model2d::connected_graph_2d_from;
let rng = rand::rng();
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.
```rust
use gengraph::Density;
use gengraph::model2d::planar_connected_graph_2d_from;
let rng = rand::rng();
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.
```rust
use gengraph::{sample_graph_from, Density};
let rng = rand::rng();
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`.
```rust
use gengraph::{sample_connected_graph_from, Density};
let rng = rand::rng();
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.
```rust
use gengraph::{sample_planar_spanning_graph_from, Density};
let rng = rand::rng();
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
```bib
@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},
}
```