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

pub mod graph {
    use petgraph::Direction;
    use petgraph::visit::{
        FilterNode, IntoEdgesDirected, IntoNodeIdentifiers, NodeFiltered, Visitable, VisitMap,
    };

    fn leaves<G, NodeId>(graph: G) -> Vec<NodeId>
    where
        G: IntoNodeIdentifiers<NodeId = NodeId>,
        G: IntoEdgesDirected<NodeId = NodeId>,
        NodeId: Clone,
    {
        graph
            .node_identifiers()
            .filter(|it| {
                graph
                    .edges_directed(it.clone(), Direction::Incoming)
                    .count()
                    == 0
            })
            .collect()
    }

    pub fn topological_layers<G>(graph: G) -> Vec<Vec<G::NodeId>>
    where
        G: Visitable,
        G::Map: FilterNode<G::NodeId>,
        G: IntoNodeIdentifiers,
        G: IntoEdgesDirected,
    {
        struct InvertedVisitMap<'m, M>(&'m M);

        impl<'m, N, M> FilterNode<N> for InvertedVisitMap<'m, M>
        where
            M: FilterNode<N>,
        {
            fn include_node(&self, node: N) -> bool {
                !self.0.include_node(node)
            }
        }

        let mut map = graph.visit_map();
        let mut layers = vec![];
        loop {
            let filter = NodeFiltered(graph, InvertedVisitMap(&map));
            let leaves = leaves(&filter);
            if leaves.is_empty() {
                break;
            }
            leaves.iter().for_each(|&n| {
                map.visit(n);
            });
            layers.push(leaves);
        }
        layers
    }
}

pub mod progress {
    use indicatif::ProgressBar;

    pub trait ProgressEmitter {
        fn update<F>(&self, f: F)
        where
            F: Fn(&ProgressBar);
    }
}