Struct DirectedAcyclicGraph 

pub struct DirectedAcyclicGraph { /* private fields */ }

A mutable, single-threaded directed acyclic graph.

Implementations

impl DirectedAcyclicGraph

pub fn new(vertex_count: Vertex) -> Self

Constructs a new graph without any edges having at most vertex_count vertices.

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

Constructs a DAG from a iterator of edges.

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

pub fn from_raw_edges(vertex_count: Vertex, edges: &[bool]) -> Self

Assumes edges is a packed representation of the adjacency matrix representing a strictly upper triangular matrix. Such representation has a useful property: (1) Every bit sequence in such a representation corresponds to some valid DAG and (2) Every DAG corresponds to some valid bit sequence in such a representation. Thanks to (1) and (2) taken together, we can be sure proptest will cover the entire search space of random DAGs.

pub fn from_adjacency_matrix( adjacency_matrix: StrictlyUpperTriangularLogicalMatrix, ) -> Self

Construct a DAG from a pre-computed adjacency matrix.

pub fn fully_connected(vertex_count: Vertex) -> Self

Construct a fully connected DAG with given amount of vertices.

pub fn get_vertex_count(&self) -> Vertex

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

Requires u < v. Panics otherwise.

pub fn set_edge(&mut self, u: Vertex, v: Vertex)

Requires u < v. Panics otherwise.

pub fn clear_edge(&mut self, u: Vertex, v: Vertex)

Requires u < v. Panics otherwise.

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

Each emitted pair (u, v) is guaranteed to satisfy u < v.

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

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

pub fn extend_with_children(&self, u: Vertex, children: &mut Vec<Vertex>)

pub fn extend_with_parents(&self, v: Vertex, parents: &mut Vec<Vertex>)

pub fn into_adjacency_matrix(self) -> StrictlyUpperTriangularLogicalMatrix

Consume self and return the underlying adjacency matrix.

pub fn iter_descendants_dfs( &self, start_vertex: Vertex, ) -> Box<dyn Iterator<Item = Vertex> + '_>

Visit all vertices reachable from vertex in a depth-first-search (DFS) order.

pub fn iter_ancestors_dfs( &self, start_vertex: Vertex, ) -> Box<dyn Iterator<Item = Vertex> + '_>

pub fn iter_vertices_dfs(&self) -> Box<dyn Iterator<Item = Vertex> + '_>

Visit all vertices of a DAG in a depth-first-search (DFS) order.

pub fn iter_vertices_dfs_post_order( &self, ) -> Box<dyn Iterator<Item = Vertex> + '_>

Visit all vertices of a DAG in a depth-first-search postorder, i.e. emitting vertices only after all their descendants were emitted first.

pub fn iter_edges_dfs_post_order( &self, ) -> Box<dyn Iterator<Item = (Vertex, Vertex)> + '_>

Visit nodes in a depth-first-search (DFS) emitting edges in postorder, i.e. each node is visited after all its descendants were already visited.

pub fn iter_descendants_dfs_post_order( &self, vertex: Vertex, ) -> Box<dyn Iterator<Item = Vertex> + '_>

Visit all vertices reachable from vertex in a depth-first-search postorder, i.e. emitting vertices only after all their descendants have been emitted first.

pub fn get_topologically_ordered_vertices(&self) -> Vec<Vertex>

Combines Self::iter_vertices_dfs_post_order with slice::reverse() to get a topologically ordered sequence of vertices of a DAG.

pub fn get_descendants(&self) -> Vec<RoaringBitmap>

Computes a mapping: vertex -> set of vertices that are descendants of vertex.

pub fn transitive_reduction(&self) -> DirectedAcyclicGraph

Returns a new DAG that is a transitive reduction of a DAG.

pub fn transitive_closure(&self) -> DirectedAcyclicGraph

Returns a new DAG that is a transitive closure of a DAG.

pub fn get_vertices_without_incoming_edges(&self) -> Vec<Vertex>

Returns a set “seed” vertices of a DAG from which a traversal may start so that the process covers all vertices in the graph.

pub fn iter_descendants_bfs(&self, vertex: Vertex) -> BfsVerticesIterator<'_>

Visit all vertices reachable from vertex in a breadth-first-search (BFS) order.

pub fn iter_vertices_bfs(&self) -> BfsVerticesIterator<'_>

Visit all vertices of a DAG in a breadth-first-search (BFS) order.

pub fn to_dot<W: Write>(&self, output: &mut W) -> Result<(), Error>

Outputs the DAG in the Graphviz DOT format.

pub fn to_dot_file<P: AsRef<Path>>(&self, path: P) -> Result<(), Error>

Trait Implementations

impl Clone for DirectedAcyclicGraph

fn clone(&self) -> DirectedAcyclicGraph

Returns a duplicate 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.

impl PartialEq for DirectedAcyclicGraph

fn eq(&self, other: &DirectedAcyclicGraph) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for DirectedAcyclicGraph

impl StructuralPartialEq for DirectedAcyclicGraph