Crate gengraph 

** Random Graph Generation Library **

How it works

For a given space of elements, define a function that assigns every element a value greater equal zero. Such a function also gets the previously sampled elements as an argument which can influence the assigned values These values are then normalized resulting in a probability distribution for the element space. Based on this density elements will be sampled. After sampling an element the probabilities will be recomputed (can be turned off).

Sampling the edges is done in an identical fashion. First the space of edges is constructed, which is given by the combination of each previously sampled element.

Example

Here is an example for generating a graph with 5 nodes that are represented by values from 0 to 10 and 10 vertices. The nodes are chosen uniformly and edges with shorter length are preferred. The node 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,
    |(x, y): &(u8, u8), _: &[(u8, u8)]| 1.0 / dist(x, y) as f64,
    |_| (),
    |(x, y): &(u8, u8)| dist(x, y),
);

An option for constructing connected planar graph is also provided.

use gengraph::{sample_planar_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_planar_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),
    |(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
    },
);

Provided Graph Scenarios

This library provides methods to generate graphs representing certain scenarios. Provided scenarios:

• coast line
• mountain valley

CLI

The cli tool provides an interface to generate multiple graphs representing one of the above mentioned scenarios. Use

$ cargo run -- -h

for more information about the cli tool.

Modules

density

model2d

probability_functions

sampling

spaces

Structs

DensityAdd

DensityChain

Applies a function to the output of Density::probability. See Density::chain.

DensityDiv

DensityMax

DensityMin

DensityMul

DensityMultiAdd

DensityMultiDiv

DensityMultiMax

DensityMultiMin

DensityMultiMul

DensityMultiSub

DensitySub

DensityTransformer

Transforms all input values to Density::probability according to the given function. See Density::transform.

Traits

Density

Describes for each instance of S the probability to take an instance of S if it is considered.

Functions

filtered_spanning_tree_on_edge_density

Implements Kruskal’s algorithm for finding a spanning tree with high probability and while allows for rejecting edges based on previously taken edges. This is archived by simple asserting befor taking an edge if the filter returns true.

graph_from

Turns the nodes and edges into a Graph. The node and edge weights are computed via the provided functions node_weight and edge_weight.

planar_spanning_tree_on_edge_density

Implements Kruskal’s algorithm for finding a spanning tree with high probability and the addition the spanning tree should be planar. This is archived by simple asserting befor taking an edge if it crosses no other previously chosen edge. This algorithm has a runtime of O(E V) O(crossing) due to the check that a new edge does not cross an previously chosen edge (of which only < V can exist).

sample_connected_graph_from

Samples a graph from the given Densitys and ensures that the graph is connected.

sample_graph_from

Samples a graph from the given Densitys.

sample_planar_connected_graph_from

Samples a graph from the given Densitys and ensures that the graph is planar according to the provided crossings function and connected.

spanning_tree_on_edge_density

Implements Kruskal’s algorithm for finding a spanning tree with high probability. This algorithm has a runtime of O(E V).