Struct Graph 

pub struct Graph { /* private fields */ }

Represents the graph on which SCC decomposition will be done. Consists of Nodes, connected by directed edges.

let mut graph = Graph::new();
let v0 = graph.new_node();
let v1 = graph.new_node();
let v2 = graph.new_node();
let v3 = graph.new_node();
graph.new_edge(v0, v1);
graph.new_edge(v1, v3);
graph.new_edge(v1, v1);
// Graph looks like this:
// ┌───┐  ┌───┐  ┌───┐ ┌───┐
// │ 0 ├─►│ 1 ├─►│ 3 │ │ 2 │
// └───┘  └▲─┬┘  └───┘ └───┘
//         └─┘

Implementations

impl Graph

pub fn new() -> Self

Creates an empty graph with no nodes and no edges. Nodes can be added by calling Graph::new_node. Edges can be added by calling Graph::new_edge.

pub fn new_node(&mut self) -> Node

Creates a new node of the graph with no incoming/outgoing edges. Edges can be added by calling Graph::new_edge.

pub fn new_edge(&mut self, from: Node, to: Node)

Creates a new directed edge between two nodes.

pub fn find_sccs(&self) -> SccDecomposition

Computes the Strongly Connected Components decomposition of this graph. Uses Tarjan’s algorithm which runs in O(|N| + |E|) time and uses O(|N| + |E|) memory.

pub fn len(&self) -> usize

Returns the number of nodes in this graph.

pub fn is_empty(&self) -> bool

Returns true if the graph has no nodes.

pub fn iter_nodes(&self) -> impl Iterator<Item = Node>

Iterates over all nodes that belong to this graph, in no particular order.

pub fn iter_successors(&self, node: Node) -> impl Iterator<Item = Node>

Iterates over all successors of the given node, in no particular order.

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Default for Graph

fn default() -> Graph

Returns the “default value” for a type.