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 either Ok with an acceptable topological order of nodes given as roots or discovered, or Err with a node belonging to a cycle. In the latter 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]);