scc

Stongly connected components

This library provides a simple implementation of a SCC algorithm. It is parametrized over the Node type, which must be comparable. (The algorithm uses the RBTree from base internally).

import SCC "mo:scc/scc";

assert(
  SCC.scc<Text>(Text.compare, [
    ("A", ["C"].vals()),
    ("B", ["B", "A"].vals()),
    ("C", ["A"].vals()),
  ].vals())
  == [["B"],["A", "C"]);

`public func scc<Node>(compareTo : (Node, Node) -> Order.Order, edges : Iter.Iter<(Node, Iter.Iter<Node>)>) : [[Node]]`

Calculates the list of strongly connected components of the graph described by the parameter edges.

The edges parameter lists each node, together with its outgoing edges. It uses iterators, so that the caller can flexibly use various data structures.

The result is the list of strongly connected components, in topological order.