daniellemaywood.uk
this repo has no description
gearsco.de
1//! General functions for working with graphs.
2
3use petgraph::{Direction, prelude::NodeIndex, stable_graph::StableGraph};
4
5/// Sort a graph into a sequence from the leaves to the roots.
6///
7/// Nodes are returned in their smallest possible groups, which is either a leaf
8/// or a cycle.
9///
10/// This function is implemented using `pop_leaf_or_cycle`.
11///
12pub fn into_dependency_order<N, E>(mut graph: StableGraph<N, E>) -> Vec<Vec<NodeIndex>> {
13 let mut items = vec![];
14
15 // Remove all self-edges from the graph.
16 graph.retain_edges(|graph, edge| match graph.edge_endpoints(edge) {
17 Some((a, b)) => a != b,
18 None => false,
19 });
20
21 loop {
22 let current = pop_leaf_or_cycle(&mut graph);
23 if current.is_empty() {
24 return items;
25 } else {
26 items.push(current);
27 }
28 }
29}
30
31/// The same as `leaf_or_cycle` but removes the nodes from the graph.
32/// See the docs there for more details.
33///
34/// # Panics
35///
36/// Panics if the graph contains a self-edge.
37///
38fn pop_leaf_or_cycle<N, E>(graph: &mut StableGraph<N, E>) -> Vec<NodeIndex> {
39 let nodes = leaf_or_cycle(graph);
40 for node in &nodes {
41 _ = graph.remove_node(*node);
42 }
43 nodes
44}
45
46/// Return a leaf from the graph. If there are no leaves then the smallest cycle
47/// is returned instead.
48///
49/// If there are no leaves or cycles then an empty vector is returned.
50///
51/// The nodes returned are not removed from the graph.
52///
53/// # Panics
54///
55/// Panics if the graph contains a self-edge.
56///
57fn leaf_or_cycle<N, E>(graph: &StableGraph<N, E>) -> Vec<NodeIndex> {
58 if graph.node_count() == 0 {
59 return vec![];
60 }
61
62 // Find a leaf, returning one if found.
63 for node in graph.node_indices() {
64 let mut outgoing = graph.neighbors_directed(node, Direction::Outgoing);
65 let referenced = outgoing.next();
66
67 if referenced == Some(node) {
68 panic!("Self edge found in graph");
69 }
70
71 // This is a leaf.
72 if referenced.is_none() {
73 return vec![node];
74 }
75 }
76
77 // No leaves were found, so find a cycle.
78 // We use a toposort to find the start of the cycle.
79 let start = petgraph::algo::toposort(&graph, None)
80 .expect_err("Non-empty graph has no leaves or cycles")
81 .node_id();
82
83 // Then traverse the graph to find nodes in the cycle.
84 // This traverses all possible paths to find a cycle, this can likely be
85 // optimised. There's not a large number of functions in a module however so
86 // this is tolerable in this specific instance.
87 #[derive(Debug)]
88 enum Step {
89 Backtrack,
90 Next(NodeIndex),
91 }
92 let mut path = vec![];
93 let mut stack = vec![Step::Next(start)];
94 let mut cycles = vec![];
95
96 while let Some(step) = stack.pop() {
97 let node = match step {
98 // We have processed all the nodes in the branch so backtrack,
99 // popping the node off the path.
100 Step::Backtrack => {
101 _ = path.pop();
102 continue;
103 }
104 Step::Next(node) => node,
105 };
106
107 if path.contains(&node) {
108 continue;
109 }
110
111 // Add this node to the path and record the point at which we need to
112 // backtrack in order to go back up the tree.
113 stack.push(Step::Backtrack);
114 path.push(node);
115
116 // Check each child & add them to the stack if they are not the target.
117 for node in graph.neighbors_directed(node, Direction::Outgoing) {
118 if node == start {
119 cycles.push(path.clone());
120 } else {
121 stack.push(Step::Next(node));
122 }
123 }
124 }
125
126 cycles
127 .into_iter()
128 .min_by(|x, y| x.len().cmp(&y.len()))
129 .expect("Could not find cycle for toposort returned start node")
130}
131
132#[cfg(test)]
133mod tests {
134 use super::*;
135
136 #[test]
137 fn leaf_or_cycle_empty() {
138 let mut graph: StableGraph<(), ()> = StableGraph::new();
139 assert!(pop_leaf_or_cycle(&mut graph).is_empty());
140 }
141
142 #[test]
143 fn leaf_or_cycle_1() {
144 let mut graph: StableGraph<(), ()> = StableGraph::new();
145 let a = graph.add_node(());
146 assert_eq!(into_dependency_order(graph), vec![vec![a]]);
147 }
148
149 #[test]
150 fn leaf_or_cycle_2() {
151 let mut graph: StableGraph<(), ()> = StableGraph::new();
152 let a = graph.add_node(());
153 let b = graph.add_node(());
154
155 assert_eq!(into_dependency_order(graph), vec![vec![a], vec![b]]);
156 }
157
158 #[test]
159 fn leaf_or_cycle_3() {
160 let mut graph: StableGraph<(), ()> = StableGraph::new();
161 // Here a depends on b so b must come before a
162 let a = graph.add_node(());
163 let b = graph.add_node(());
164 let c = graph.add_node(());
165 _ = graph.add_edge(a, b, ());
166
167 assert_eq!(
168 into_dependency_order(graph),
169 vec![vec![b], vec![a], vec![c]]
170 );
171 }
172
173 #[test]
174 fn leaf_or_cycle_4() {
175 let mut graph: StableGraph<(), ()> = StableGraph::new();
176 let a = graph.add_node(());
177 let b = graph.add_node(());
178 let c = graph.add_node(());
179 _ = graph.add_edge(a, b, ());
180 _ = graph.add_edge(a, c, ());
181
182 assert_eq!(
183 into_dependency_order(graph),
184 vec![vec![b], vec![c], vec![a]]
185 );
186 }
187
188 #[test]
189 fn leaf_or_cycle_5() {
190 let mut graph: StableGraph<(), ()> = StableGraph::new();
191 let a = graph.add_node(());
192 let b = graph.add_node(());
193 let c = graph.add_node(());
194 _ = graph.add_edge(a, b, ());
195 _ = graph.add_edge(b, a, ());
196
197 assert_eq!(into_dependency_order(graph), vec![vec![c], vec![b, a]]);
198 }
199
200 #[test]
201 fn leaf_or_cycle_6() {
202 let mut graph: StableGraph<(), ()> = StableGraph::new();
203 let a = graph.add_node(());
204 let b = graph.add_node(());
205 let c = graph.add_node(());
206 let d = graph.add_node(());
207 _ = graph.add_edge(a, b, ());
208 _ = graph.add_edge(b, c, ());
209 _ = graph.add_edge(c, a, ());
210 _ = graph.add_edge(d, a, ());
211
212 assert_eq!(into_dependency_order(graph), vec![vec![c, a, b], vec![d]]);
213 }
214
215 #[test]
216 fn leaf_or_cycle_7() {
217 let mut graph: StableGraph<(), ()> = StableGraph::new();
218 let a = graph.add_node(());
219 let b = graph.add_node(());
220 _ = graph.add_edge(a, a, ());
221 _ = graph.add_edge(a, b, ());
222 _ = graph.add_edge(b, b, ());
223
224 // Here there are no true leafs, only cycles. However, b is in a loop
225 // with itself so counts as a leaf as far as we are concerned.
226
227 assert_eq!(into_dependency_order(graph), vec![vec![b], vec![a]]);
228 }
229
230 #[test]
231 fn leaf_or_cycle_8() {
232 let mut graph: StableGraph<(), ()> = StableGraph::new();
233 let a = graph.add_node(());
234 let b = graph.add_node(());
235 _ = graph.add_edge(a, a, ());
236 _ = graph.add_edge(a, b, ());
237 _ = graph.add_edge(b, b, ());
238 _ = graph.add_edge(b, b, ());
239 _ = graph.add_edge(b, b, ());
240
241 // Here there are no true leafs, only cycles. However, b is in a loop
242 // with itself so counts as a leaf as far as we are concerned.
243 // This is different from the previous test as there are multiple self
244 // references for node b.
245
246 assert_eq!(into_dependency_order(graph), vec![vec![b], vec![a]]);
247 }
248
249 #[test]
250 fn leaf_or_cycle_9() {
251 let mut graph: StableGraph<(), ()> = StableGraph::new();
252 let a = graph.add_node(());
253 let b = graph.add_node(());
254 let c = graph.add_node(());
255
256 _ = graph.add_edge(a, a, ());
257 _ = graph.add_edge(a, b, ());
258
259 _ = graph.add_edge(b, b, ());
260 _ = graph.add_edge(b, c, ());
261
262 _ = graph.add_edge(c, b, ());
263 _ = graph.add_edge(c, c, ());
264
265 // Here there are no true leafs, only cycles. However, b is in a loop
266 // with itself so counts as a leaf as far as we are concerned.
267 // This is different from the previous test as there are multiple self
268 // references for node b.
269
270 assert_eq!(into_dependency_order(graph), vec![vec![c, b], vec![a]]);
271 }
272}