topo_sort 0.1.2

A 'cycle-safe' topological sort for a set of nodes with dependencies
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

# topo_sort

[![Crate](https://img.shields.io/crates/v/topo_sort?style=for-the-badge)](https://crates.io/crates/topo_sort)
[![Docs](https://img.shields.io/docsrs/topo_sort?style=for-the-badge)](https://docs.rs/topo_sort)

A "cycle-safe" topological sort for a set of nodes with dependencies in Rust.
Basically, it allows sorting a list by its dependencies while checking for
cycles in the graph. If a cycle is detected, a `CycleError` is returned from the
iterator.

## Usage

```toml
[dependencies]
topo_sort = "0.1"
```

A basic example:

```rust
use topo_sort::TopoSort;

fn main() {
    let mut topo_sort = TopoSort::with_capacity(5);
    topo_sort.insert("C", vec!["A", "B"]); // read: "C" depends on "A" and "B"
    topo_sort.insert("E", vec!["B", "C"]);
    topo_sort.insert("A", vec![]);
    topo_sort.insert("D", vec!["A", "C", "E"]);
    topo_sort.insert("B", vec!["A"]);

    assert_eq!(
        vec!["A", "B", "C", "E", "D"],
        topo_sort.to_owned_vec().unwrap()
    );
}
```

...or using iteration:

```rust
use topo_sort::TopoSort;

fn main() {
    let mut topo_sort = TopoSort::with_capacity(5);
    topo_sort.insert("C", vec!["A", "B"]);
    topo_sort.insert("E", vec!["B", "C"]);
    topo_sort.insert("A", vec![]);
    topo_sort.insert("D", vec!["A", "C", "E"]);
    topo_sort.insert("B", vec!["A"]);

    let mut nodes = Vec::with_capacity(5);
    for node in &topo_sort {
        // We check for cycle errors before usage
        match node {
            Ok(node) => nodes.push(*node),
            Err(_) => panic!("Unexpected cycle!"),
        }
    }

    assert_eq!(vec!["A", "B", "C", "E", "D"], nodes);
}
```

Cycle detected:

```rust
use topo_sort::TopoSort;

fn main() {
    let mut topo_sort = TopoSort::with_capacity(3);
    topo_sort.insert(1, vec![2, 3]);
    topo_sort.insert(2, vec![3]);
    topo_sort.insert(3, vec![1]); // cycle

    assert!(topo_sort.to_vec().is_err());
}
```

## Algorithm

This is implemented
using [Kahn's algorithm](https://en.wikipedia.org/wiki/Topological_sorting).
While basic caution was taken not to do anything too egregious performance-wise,
the author's use cases are not performance sensitive, and it has not been
optimized in any way.

## Maintenance

The crate currently meets the needs of the author and probably will not see
significant new features. It will, however, continue to be updated if required
for future compatibility/etc.

## License

This project is licensed optionally under either:

* Apache License, Version 2.0, (LICENSE-APACHE
  or https://www.apache.org/licenses/LICENSE-2.0)
* MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)