Function pathfinding::directed::topological_sort::topological_sort

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

Find a topological order in a directed graph if one exists.

• roots is a collection of nodes that ought to be explored.
• successors returns a list of successors for a given node, including possibly nodes that were not present in roots.

The function returns an acceptable topological order of nodes given as roots or discovered, or an error if a cycle is detected.

Errors

If a cycle is found, Err(n) is returned with n being an arbitrary node involved in a cycle. In this case case, the strongly connected set can then be found using the strongly_connected_component function, or if only one of the loops is needed the bfs_loop function can be used instead to identify one of the shortest loops involving this node.

Examples

We will sort integers from 1 to 9, each integer having its two immediate greater numbers as successors, starting with two roots 5 and 1:

use pathfinding::prelude::topological_sort;

fn successors(node: &usize) -> Vec<usize> {
  match *node {
    n if n <= 7 => vec![n+1, n+2],
    8 => vec![9],
    _ => vec![],
  }
}

let sorted = topological_sort(&[5, 1], successors);
assert_eq!(sorted, Ok(vec![1, 2, 3, 4, 5, 6, 7, 8, 9]));

If, however, there is a loop in the graph (for example, all nodes but 7 have also 7 has a successor), one of the nodes in the loop will be returned as an error:

use pathfinding::prelude::*;

fn successors(node: &usize) -> Vec<usize> {
  match *node {
    n if n <= 6 => vec![n+1, n+2, 7],
    7 => vec![8, 9],
    8 => vec![7, 9],
    _ => vec![7],
  }
}

let sorted = topological_sort(&[5, 1], successors);
assert!(sorted.is_err());

// Let's assume that the returned node is 8 (it can be any node which is part
// of a loop). We can lookup up one of the shortest loops containing 8
// (8 -> 7 -> 8 is the unique loop with two hops containing 8):

assert_eq!(bfs_loop(&8, successors), Some(vec![8, 7, 8]));

// We can also request the whole strongly connected set containing 8. Here
// 7, 8, and 9 are all reachable from one another.

let mut set = strongly_connected_component(&8, successors);
set.sort();
assert_eq!(set, vec![7, 8, 9]);