Struct DirectedGraph

pub struct DirectedGraph { /* private fields */ }

A mutable, single-threaded directed graph.

Implementations

impl DirectedGraph

pub fn new(vertex_count: Vertex) -> Self

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

pub fn has_edges(&self) -> bool

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

where I: Iterator<Item = (Vertex, Vertex)>,

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

pub fn get_vertex_count(&self) -> Vertex

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

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

pub fn set_edge(&mut self, parent: Vertex, child: Vertex)

pub fn clear_edge(&mut self, parent: Vertex, child: Vertex)

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

Returns None if the graph has more than connected component or there’s no root.

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

Pushes vertices v at the end of children such that there’s an edge (u, v) in the graph.

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

Pushes vertices u at the end of parents such that there’s an edge (u, v) in the graph.

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_post_order( &self, start_vertices: &[Vertex], ) -> 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 have been emitted first.

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

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

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

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

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

Return a sequence of topologically ordered vertices of a digraph, or None if the digraph has a cycle.

pub fn transitive_reduction(&self) -> DirectedGraph

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

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