Struct dograph::DirectedAcyclicGraph

pub struct DirectedAcyclicGraph { /* private fields */ }

A mutable, single-threaded directed acyclic graph.

Implementations

impl DirectedAcyclicGraph

pub fn empty(vertex_count: usize) -> Self

pub fn from_edges_iter<I: Iterator<Item = (usize, usize)>>(
    vertex_count: usize,
    edges: I
) -> Self

Constructs a DAG from an iterator of edges.

Requires u < vertex_count && v < vertex_count && u < v for every edge (u, v) in edges. Panics otherwise.

pub fn random<R: Rng, D: Distribution<bool> + Copy>(
    vertex_count: usize,
    rng: &mut R,
    edges_distribution: D
) -> Self

Generate a random DAG sampling edges from edges_distribution.

For example, to generate a random DAG with a probability 1/2 of having an edge between any two of 321 vertices, do:

use crate::DirectedAcyclicGraph;
use rand::rngs::StdRng;
use rand::SeedableRng;
use rand::distributions::Bernoulli;

let mut rng = StdRng::seed_from_u64(123);
let dag = DirectedAcyclicGraph::random(321, &mut rng, Bernoulli::new(0.5).unwrap());

pub fn from_adjacency_matrix(
    adjacency_matrix: StrictlyUpperTriangularLogicalMatrix
) -> Self

Construct a DAG from an pre-computed adjacency matrix.

pub fn get_vertex_count(&self) -> usize

pub fn get_edge(&self, u: usize, v: usize) -> bool

Requires u < v. Panics otherwise.

pub fn set_edge(&mut self, u: usize, v: usize, exists: bool)

Requires u < v. Panics otherwise.

pub fn iter_edges(&self) -> impl Iterator<Item = (usize, usize)> + '_

Iterates over the edges in an order that favors CPU cache locality.

pub fn iter_children(&self, u: usize) -> impl Iterator<Item = usize> + '_

Iterates over vertices v such that there’s an edge (u, v) in the DAG.

pub fn into_adjacency_matrix(self) -> StrictlyUpperTriangularLogicalMatrix

Consume self and return the underlying adjacency matrix.

Trait Implementations

impl Arbitrary for DirectedAcyclicGraph

fn arbitrary(g: &mut Gen) -> Self

Return an arbitrary value.

fn shrink(&self) -> Box<dyn Iterator<Item = DirectedAcyclicGraph>>

Return an iterator of values that are smaller than itself.

impl Clone for DirectedAcyclicGraph

fn clone(&self) -> DirectedAcyclicGraph

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DirectedAcyclicGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.