Function topological_sort

pub fn topological_sort<N, E>(graph: &DiGraph<N, E>) -> Option<Vec<&N>>
where
    N: Hash + Eq,

Returns a topological sort of the graph, if one exists.

If the graph contains one or more directed cycles, None is returned.

Example

use rust_dsa::{DiGraph, topological_sort};

//    +---+      +---+      +---+
//    |'a'| ---> |'b'| ---> |'c'|
//    +---+      +---+      +---+
let no_cycle = DiGraph::from([('a', 'b', ()), ('b', 'c', ())]);

assert_eq!(
    topological_sort(&no_cycle),
    Some(vec![&'a', &'b', &'c'])
);


//    +---+      +---+
//    | 1 | ---> | 2 |
//    +---+      +---+
//      ^          |
//      |          v
//      |        +---+      +---+
//      +------- | 3 | ---> | 4 |
//               +---+      +---+
let with_cycle = DiGraph::from([
    (1, 2, ()),
    (2, 3, ()),
    (3, 4, ()),
    (3, 1, ()),
]);

// `with_cycle` contains a cycle so `topological_sort` returns `None`.
assert_eq!(
    topological_sort(&with_cycle),
    None
);

use rust_dsa::is_topological_sort;

let big_graph = DiGraph::from([
    (1, 2, ()),
    (2, 3, ()),
    (4, 3, ()),
    (3, 5, ()),
    (5, 6, ()),
    (6, 7, ()),
    (7, 8, ()),
    (5, 9, ()),
    (9, 10, ()),
    (5, 10, ()),
    (10, 11, ()),
    (10, 8, ()),
    (5, 12, ()),
    (12, 13, ()),
    (12, 14, ()),
    (12, 8, ()),
    (8, 15, ()),
]);

// `big_graph` is acyclic.
let sort = topological_sort(&big_graph).unwrap();

assert!(is_topological_sort(&big_graph, &sort));

Runtime complexity

This function implements Kahn’s algorithm, so it runs in O(N + E) time where N is the number of nodes and E is the number of edges.