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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
use bevy_utils::{tracing::warn, HashMap, HashSet};
use fixedbitset::FixedBitSet;
use std::{borrow::Cow, fmt::Debug, hash::Hash};
pub enum DependencyGraphError<Labels> {
GraphCycles(Vec<(usize, Labels)>),
}
pub trait GraphNode<Label> {
fn name(&self) -> Cow<'static, str>;
fn labels(&self) -> &[Label];
fn before(&self) -> &[Label];
fn after(&self) -> &[Label];
}
pub fn build_dependency_graph<Node, Label>(
nodes: &[Node],
) -> HashMap<usize, HashMap<usize, HashSet<Label>>>
where
Node: GraphNode<Label>,
Label: Debug + Clone + Eq + Hash,
{
let mut labels = HashMap::<Label, FixedBitSet>::default();
for (label, index) in nodes.iter().enumerate().flat_map(|(index, container)| {
container
.labels()
.iter()
.cloned()
.map(move |label| (label, index))
}) {
labels
.entry(label)
.or_insert_with(|| FixedBitSet::with_capacity(nodes.len()))
.insert(index);
}
let mut graph = HashMap::with_capacity_and_hasher(nodes.len(), Default::default());
for (index, node) in nodes.iter().enumerate() {
let dependencies = graph.entry(index).or_insert_with(HashMap::default);
for label in node.after() {
match labels.get(label) {
Some(new_dependencies) => {
for dependency in new_dependencies.ones() {
dependencies
.entry(dependency)
.or_insert_with(HashSet::default)
.insert(label.clone());
}
}
None => warn!(
"{} wants to be after unknown label: {:?}",
nodes[index].name(),
label
),
}
}
for label in node.before() {
match labels.get(label) {
Some(dependants) => {
for dependant in dependants.ones() {
graph
.entry(dependant)
.or_insert_with(HashMap::default)
.entry(index)
.or_insert_with(HashSet::default)
.insert(label.clone());
}
}
None => warn!(
"{} wants to be before unknown label: {:?}",
nodes[index].name(),
label
),
}
}
}
graph
}
pub fn topological_order<Labels: Clone>(
graph: &HashMap<usize, HashMap<usize, Labels>>,
) -> Result<Vec<usize>, DependencyGraphError<Labels>> {
fn check_if_cycles_and_visit<L>(
node: &usize,
graph: &HashMap<usize, HashMap<usize, L>>,
sorted: &mut Vec<usize>,
unvisited: &mut HashSet<usize>,
current: &mut Vec<usize>,
) -> bool {
if current.contains(node) {
return true;
} else if !unvisited.remove(node) {
return false;
}
current.push(*node);
for dependency in graph.get(node).unwrap().keys() {
if check_if_cycles_and_visit(dependency, &graph, sorted, unvisited, current) {
return true;
}
}
sorted.push(*node);
current.pop();
false
}
let mut sorted = Vec::with_capacity(graph.len());
let mut current = Vec::with_capacity(graph.len());
let mut unvisited = HashSet::with_capacity_and_hasher(graph.len(), Default::default());
unvisited.extend(graph.keys().cloned());
while let Some(node) = unvisited.iter().next().cloned() {
if check_if_cycles_and_visit(&node, graph, &mut sorted, &mut unvisited, &mut current) {
let mut cycle = Vec::new();
let last_window = [*current.last().unwrap(), current[0]];
let mut windows = current
.windows(2)
.chain(std::iter::once(&last_window as &[usize]));
while let Some(&[dependant, dependency]) = windows.next() {
cycle.push((dependant, graph[&dependant][&dependency].clone()));
}
return Err(DependencyGraphError::GraphCycles(cycle));
}
}
Ok(sorted)
}