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 a collection of groups if there are no cycles in the graph and an error otherwise.

Errors

A tuple (groups, remaining) containing a (possibly empty) partial list of groups, and a list of remaining nodes that could not be grouped due to cycles. In this case, the strongly connected set(s) can then be found using the strongly_connected_components function on the list of remaining nodes.