Struct roaring_graphs::dag::DirectedAcyclicGraph

pub struct DirectedAcyclicGraph { /* private fields */ }

A mutable, single-threaded directed acyclic graph.

Implementations

impl DirectedAcyclicGraph

pub fn empty(vertex_count: u32) -> Self

pub fn from_edges_iter<I: Iterator<Item = (u32, u32)>>( vertex_count: u32, 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 from_raw_edges(vertex_count: u32, 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 an pre-computed adjacency matrix.

pub fn get_vertex_count(&self) -> u32

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

Requires u < v. Panics otherwise.

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

Requires u < v. Panics otherwise.

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

Requires u < v. Panics otherwise.

pub fn set_edge_to(&mut self, u: u32, v: u32, exists: bool)

Requires u < v. Panics otherwise.

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

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

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

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

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

pub fn into_adjacency_matrix(self) -> StrictlyUpperTriangularLogicalMatrix

Consume self and return the underlying adjacency matrix.

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

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

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

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

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 = u32> + '_>

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

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

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

Note that when a DAG represents a partially ordered set, this function iterates over pairs of that poset. It may be necessary to first compute either a Self::transitive_reduction of a DAG, to only get the minimal set of pairs spanning the entire poset, or a Self::transitive_closure to get all the pairs of that poset.

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

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<u32>

Combines Self::iter_vertices_dfs_post_order, Iterator::collect() and 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<u32>

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: u32) -> 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 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.