Function pathfinding::directed::topological_sort::topological_sort_into_groups

pub fn topological_sort_into_groups<N, FN, IN>(
    nodes: &[N], 
    successors: FN
) -> Result<Vec<Vec<N>>, (Vec<Vec<N>>, Vec<N>)> where
    N: Eq + Hash + Clone,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>, 

Topologically sort a directed graph into groups of independent nodes.

• nodes is a collection of nodes.
• successors returns a list of successors for a given node.

This function works like topological_sort, but rather than producing a single ordering of nodes, this function partitions the nodes into groups: the first group contains all nodes with no dependencies, the second group contains all nodes whose only dependencies are in the first group, and so on. Concatenating the groups produces a valid topological sort regardless of how the nodes within each group are reordered. No guarantees are made about the order of nodes within each group. Also, the list of nodes must be exhaustive, new nodes must not be returned by the successors function.

The function returns either Ok with a valid list of groups, or Err with a (groups, remaining) tuple containing a (possibly empty) partial list of groups, and a list of remaining nodes that could not be grouped due to cycles. In the error case, the strongly connected set(s) can then be found using the strongly_connected_components function on the list of remaining nodes.

The current implementation uses a variation of Kahn’s algorithm, and runs in O(|V| + |E|) time.