Crate strongly_connected_components 

Decomposes a graph into Strongly Connected Components and to sorts them in topological order.

Usage

1. Define the Graph structure:

// ┌───┐  ┌───┐  ┌───┐
// │ a ├─►│ b ├─►│ c │
// └───┘  └─▲─┘  └─┬─┘
//          └──────┘
let mut graph = Graph::new();
let a: Node = graph.new_node();
let b: Node = graph.new_node();
let c: Node = graph.new_node();
graph.new_edge(a, b);
graph.new_edge(b, c);
graph.new_edge(c, b);

2. Run the algorithm and create the SccDecomposition:

let decomp: SccDecomposition = graph.find_sccs();
// There are 2 SCCs in the example graph: `[a]` and `[b, c]`.
assert_eq!(decomp.len(), 2);

3. Check whether two nodes belong to the same Scc:

let a_scc: &Scc = decomp.scc_of_node(a);
let b_scc: &Scc = decomp.scc_of_node(b);
let c_scc: &Scc = decomp.scc_of_node(c);

// Node `a` belongs to a different SCC than `b` and `c`.
assert_ne!(a_scc, b_scc);
assert_ne!(a_scc, c_scc);

// Nodes `b` and `c` belong to the same SCC.
assert_eq!(b_scc, c_scc);

4. List all nodes belonging to Scc:

assert_eq!(a_scc.len(), 1);
let a_scc_all: Vec<Node> = a_scc.iter_nodes().collect();
assert_eq!(a_scc_all, vec![a]);

assert_eq!(b_scc.len(), 2);
let b_scc_all: Vec<Node> = b_scc.iter_nodes().collect();
assert_eq!(b_scc_all, vec![b, c]);

5. List Sccs in topological order:

let sccs: Vec<&Scc> = decomp.iter_sccs().collect();
assert_eq!(sccs, vec![b_scc, a_scc]);

6. List Nodes in topological order (with arbitrary order within Sccs):

let nodes: Vec<Node> = decomp.iter_nodes().collect();
// Either of those would be a valid order,
// because `b` and `c` belong to the same SCC.
assert!(nodes == vec![c, b, a] || nodes == vec![b, c, a]);

Structs

Graph

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

Node

Represents a single node of the graph. A node can be created by calling Graph::new_node().

Scc

Represents a single Strongly Connected Component (SCC) of a Graph.

SccDecomposition

Represents the decomposition of a Graph into Strongly Connected Components (SCC).