Struct roaring_graphs::digraph::DirectedGraph

pub struct DirectedGraph { /* private fields */ }

Implementations

impl DirectedGraph

pub fn empty(vertex_count: u32) -> Self

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

pub fn from_dag(dag: &DirectedAcyclicGraph) -> Self

pub fn get_vertex_count(&self) -> u32

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

pub fn get_edge(&self, parent: u32, child: u32) -> bool

pub fn set_edge(&mut self, parent: u32, child: u32, exists: bool)

pub fn find_tree_root(&self) -> Option<u32>

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

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

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

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

pub fn has_cycle(&self) -> bool

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 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 get_descendants(&self) -> Vec<RoaringBitmap>

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

pub fn transitive_reduction(&self) -> DirectedGraph

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

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 after all its descendants have been emitted.

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.

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 DirectedGraph

fn clone(&self) -> DirectedGraph

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for DirectedGraph

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

Formats the value using the given formatter.