]>
Commit | Line | Data |
---|---|---|
8faf50e0 XL |
1 | //! A graph module for use in dataflow, region resolution, and elsewhere. |
2 | //! | |
3 | //! # Interface details | |
4 | //! | |
5 | //! You customize the graph by specifying a "node data" type `N` and an | |
6 | //! "edge data" type `E`. You can then later gain access (mutable or | |
7 | //! immutable) to these "user-data" bits. Currently, you can only add | |
8 | //! nodes or edges to the graph. You cannot remove or modify them once | |
9 | //! added. This could be changed if we have a need. | |
10 | //! | |
11 | //! # Implementation details | |
12 | //! | |
13 | //! The main tricky thing about this code is the way that edges are | |
14 | //! stored. The edges are stored in a central array, but they are also | |
15 | //! threaded onto two linked lists for each node, one for incoming edges | |
16 | //! and one for outgoing edges. Note that every edge is a member of some | |
9fa01778 | 17 | //! incoming list and some outgoing list. Basically you can load the |
8faf50e0 XL |
18 | //! first index of the linked list from the node data structures (the |
19 | //! field `first_edge`) and then, for each edge, load the next index from | |
20 | //! the field `next_edge`). Each of those fields is an array that should | |
21 | //! be indexed by the direction (see the type `Direction`). | |
22 | ||
9fa01778 | 23 | use crate::snapshot_vec::{SnapshotVec, SnapshotVecDelegate}; |
dfeec247 | 24 | use rustc_index::bit_set::BitSet; |
8faf50e0 | 25 | use std::fmt::Debug; |
8faf50e0 XL |
26 | |
27 | #[cfg(test)] | |
28 | mod tests; | |
29 | ||
30 | pub struct Graph<N, E> { | |
31 | nodes: SnapshotVec<Node<N>>, | |
32 | edges: SnapshotVec<Edge<E>>, | |
33 | } | |
34 | ||
35 | pub struct Node<N> { | |
36 | first_edge: [EdgeIndex; 2], // see module comment | |
37 | pub data: N, | |
38 | } | |
39 | ||
40 | #[derive(Debug)] | |
41 | pub struct Edge<E> { | |
42 | next_edge: [EdgeIndex; 2], // see module comment | |
43 | source: NodeIndex, | |
44 | target: NodeIndex, | |
45 | pub data: E, | |
46 | } | |
47 | ||
48 | impl<N> SnapshotVecDelegate for Node<N> { | |
49 | type Value = Node<N>; | |
50 | type Undo = (); | |
51 | ||
52 | fn reverse(_: &mut Vec<Node<N>>, _: ()) {} | |
53 | } | |
54 | ||
55 | impl<N> SnapshotVecDelegate for Edge<N> { | |
56 | type Value = Edge<N>; | |
57 | type Undo = (); | |
58 | ||
59 | fn reverse(_: &mut Vec<Edge<N>>, _: ()) {} | |
60 | } | |
61 | ||
e74abb32 | 62 | #[derive(Copy, Clone, PartialEq, Debug)] |
8faf50e0 XL |
63 | pub struct NodeIndex(pub usize); |
64 | ||
e74abb32 | 65 | #[derive(Copy, Clone, PartialEq, Debug)] |
8faf50e0 XL |
66 | pub struct EdgeIndex(pub usize); |
67 | ||
68 | pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX); | |
69 | ||
70 | // Use a private field here to guarantee no more instances are created: | |
71 | #[derive(Copy, Clone, Debug, PartialEq)] | |
72 | pub struct Direction { | |
73 | repr: usize, | |
74 | } | |
75 | ||
76 | pub const OUTGOING: Direction = Direction { repr: 0 }; | |
77 | ||
78 | pub const INCOMING: Direction = Direction { repr: 1 }; | |
79 | ||
80 | impl NodeIndex { | |
9fa01778 | 81 | /// Returns unique ID (unique with respect to the graph holding associated node). |
b7449926 | 82 | pub fn node_id(self) -> usize { |
8faf50e0 XL |
83 | self.0 |
84 | } | |
85 | } | |
86 | ||
87 | impl<N: Debug, E: Debug> Graph<N, E> { | |
88 | pub fn new() -> Graph<N, E> { | |
dfeec247 | 89 | Graph { nodes: SnapshotVec::new(), edges: SnapshotVec::new() } |
8faf50e0 XL |
90 | } |
91 | ||
92 | pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> { | |
dfeec247 | 93 | Graph { nodes: SnapshotVec::with_capacity(nodes), edges: SnapshotVec::with_capacity(edges) } |
8faf50e0 XL |
94 | } |
95 | ||
96 | // # Simple accessors | |
97 | ||
98 | #[inline] | |
99 | pub fn all_nodes(&self) -> &[Node<N>] { | |
100 | &self.nodes | |
101 | } | |
102 | ||
103 | #[inline] | |
104 | pub fn len_nodes(&self) -> usize { | |
105 | self.nodes.len() | |
106 | } | |
107 | ||
108 | #[inline] | |
109 | pub fn all_edges(&self) -> &[Edge<E>] { | |
110 | &self.edges | |
111 | } | |
112 | ||
113 | #[inline] | |
114 | pub fn len_edges(&self) -> usize { | |
115 | self.edges.len() | |
116 | } | |
117 | ||
118 | // # Node construction | |
119 | ||
120 | pub fn next_node_index(&self) -> NodeIndex { | |
121 | NodeIndex(self.nodes.len()) | |
122 | } | |
123 | ||
124 | pub fn add_node(&mut self, data: N) -> NodeIndex { | |
125 | let idx = self.next_node_index(); | |
dfeec247 | 126 | self.nodes.push(Node { first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX], data }); |
8faf50e0 XL |
127 | idx |
128 | } | |
129 | ||
130 | pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N { | |
131 | &mut self.nodes[idx.0].data | |
132 | } | |
133 | ||
134 | pub fn node_data(&self, idx: NodeIndex) -> &N { | |
135 | &self.nodes[idx.0].data | |
136 | } | |
137 | ||
138 | pub fn node(&self, idx: NodeIndex) -> &Node<N> { | |
139 | &self.nodes[idx.0] | |
140 | } | |
141 | ||
142 | // # Edge construction and queries | |
143 | ||
144 | pub fn next_edge_index(&self) -> EdgeIndex { | |
145 | EdgeIndex(self.edges.len()) | |
146 | } | |
147 | ||
148 | pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex { | |
149 | debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data); | |
150 | ||
151 | let idx = self.next_edge_index(); | |
152 | ||
153 | // read current first of the list of edges from each node | |
154 | let source_first = self.nodes[source.0].first_edge[OUTGOING.repr]; | |
155 | let target_first = self.nodes[target.0].first_edge[INCOMING.repr]; | |
156 | ||
157 | // create the new edge, with the previous firsts from each node | |
158 | // as the next pointers | |
dfeec247 | 159 | self.edges.push(Edge { next_edge: [source_first, target_first], source, target, data }); |
8faf50e0 XL |
160 | |
161 | // adjust the firsts for each node target be the next object. | |
162 | self.nodes[source.0].first_edge[OUTGOING.repr] = idx; | |
163 | self.nodes[target.0].first_edge[INCOMING.repr] = idx; | |
164 | ||
b7449926 | 165 | idx |
8faf50e0 XL |
166 | } |
167 | ||
168 | pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> { | |
169 | &self.edges[idx.0] | |
170 | } | |
171 | ||
172 | // # Iterating over nodes, edges | |
173 | ||
174 | pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> { | |
dfeec247 | 175 | self.nodes.iter().enumerate().map(|(idx, n)| (NodeIndex(idx), n)) |
8faf50e0 XL |
176 | } |
177 | ||
178 | pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> { | |
dfeec247 | 179 | self.edges.iter().enumerate().map(|(idx, e)| (EdgeIndex(idx), e)) |
8faf50e0 XL |
180 | } |
181 | ||
182 | pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool { | |
183 | //! Iterates over all edges defined in the graph. | |
dfeec247 | 184 | self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node)) |
8faf50e0 XL |
185 | } |
186 | ||
187 | pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool { | |
188 | //! Iterates over all edges defined in the graph | |
dfeec247 | 189 | self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge)) |
8faf50e0 XL |
190 | } |
191 | ||
9fa01778 | 192 | pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { |
8faf50e0 XL |
193 | self.adjacent_edges(source, OUTGOING) |
194 | } | |
195 | ||
9fa01778 | 196 | pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<'_, N, E> { |
8faf50e0 XL |
197 | self.adjacent_edges(source, INCOMING) |
198 | } | |
199 | ||
9fa01778 XL |
200 | pub fn adjacent_edges( |
201 | &self, | |
202 | source: NodeIndex, | |
dfeec247 | 203 | direction: Direction, |
9fa01778 | 204 | ) -> AdjacentEdges<'_, N, E> { |
8faf50e0 | 205 | let first_edge = self.node(source).first_edge[direction.repr]; |
dfeec247 | 206 | AdjacentEdges { graph: self, direction, next: first_edge } |
8faf50e0 XL |
207 | } |
208 | ||
209 | pub fn successor_nodes<'a>( | |
210 | &'a self, | |
211 | source: NodeIndex, | |
212 | ) -> impl Iterator<Item = NodeIndex> + 'a { | |
213 | self.outgoing_edges(source).targets() | |
214 | } | |
215 | ||
216 | pub fn predecessor_nodes<'a>( | |
217 | &'a self, | |
218 | target: NodeIndex, | |
219 | ) -> impl Iterator<Item = NodeIndex> + 'a { | |
220 | self.incoming_edges(target).sources() | |
221 | } | |
222 | ||
416331ca XL |
223 | pub fn depth_traverse( |
224 | &self, | |
8faf50e0 XL |
225 | start: NodeIndex, |
226 | direction: Direction, | |
416331ca | 227 | ) -> DepthFirstTraversal<'_, N, E> { |
8faf50e0 XL |
228 | DepthFirstTraversal::with_start_node(self, start, direction) |
229 | } | |
230 | ||
b7449926 XL |
231 | pub fn nodes_in_postorder( |
232 | &self, | |
8faf50e0 XL |
233 | direction: Direction, |
234 | entry_node: NodeIndex, | |
235 | ) -> Vec<NodeIndex> { | |
0bf4aa26 | 236 | let mut visited = BitSet::new_empty(self.len_nodes()); |
8faf50e0 XL |
237 | let mut stack = vec![]; |
238 | let mut result = Vec::with_capacity(self.len_nodes()); | |
239 | let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| { | |
240 | if visited.insert(node.0) { | |
241 | stack.push((node, self.adjacent_edges(node, direction))); | |
242 | } | |
243 | }; | |
244 | ||
dfeec247 XL |
245 | for node in |
246 | Some(entry_node).into_iter().chain(self.enumerated_nodes().map(|(node, _)| node)) | |
8faf50e0 XL |
247 | { |
248 | push_node(&mut stack, node); | |
249 | while let Some((node, mut iter)) = stack.pop() { | |
250 | if let Some((_, child)) = iter.next() { | |
251 | let target = child.source_or_target(direction); | |
252 | // the current node needs more processing, so | |
253 | // add it back to the stack | |
254 | stack.push((node, iter)); | |
255 | // and then push the new node | |
256 | push_node(&mut stack, target); | |
257 | } else { | |
258 | result.push(node); | |
259 | } | |
260 | } | |
261 | } | |
262 | ||
263 | assert_eq!(result.len(), self.len_nodes()); | |
264 | result | |
265 | } | |
266 | } | |
267 | ||
268 | // # Iterators | |
269 | ||
9fa01778 | 270 | pub struct AdjacentEdges<'g, N, E> { |
8faf50e0 XL |
271 | graph: &'g Graph<N, E>, |
272 | direction: Direction, | |
273 | next: EdgeIndex, | |
274 | } | |
275 | ||
276 | impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> { | |
277 | fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g { | |
e74abb32 | 278 | self.map(|(_, edge)| edge.target) |
8faf50e0 XL |
279 | } |
280 | ||
281 | fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g { | |
e74abb32 | 282 | self.map(|(_, edge)| edge.source) |
8faf50e0 XL |
283 | } |
284 | } | |
285 | ||
286 | impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> { | |
287 | type Item = (EdgeIndex, &'g Edge<E>); | |
288 | ||
289 | fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> { | |
290 | let edge_index = self.next; | |
291 | if edge_index == INVALID_EDGE_INDEX { | |
292 | return None; | |
293 | } | |
294 | ||
295 | let edge = self.graph.edge(edge_index); | |
296 | self.next = edge.next_edge[self.direction.repr]; | |
297 | Some((edge_index, edge)) | |
298 | } | |
299 | ||
300 | fn size_hint(&self) -> (usize, Option<usize>) { | |
301 | // At most, all the edges in the graph. | |
302 | (0, Some(self.graph.len_edges())) | |
303 | } | |
304 | } | |
305 | ||
9fa01778 | 306 | pub struct DepthFirstTraversal<'g, N, E> { |
8faf50e0 XL |
307 | graph: &'g Graph<N, E>, |
308 | stack: Vec<NodeIndex>, | |
0bf4aa26 | 309 | visited: BitSet<usize>, |
8faf50e0 XL |
310 | direction: Direction, |
311 | } | |
312 | ||
313 | impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> { | |
314 | pub fn with_start_node( | |
315 | graph: &'g Graph<N, E>, | |
316 | start_node: NodeIndex, | |
317 | direction: Direction, | |
318 | ) -> Self { | |
0bf4aa26 | 319 | let mut visited = BitSet::new_empty(graph.len_nodes()); |
8faf50e0 | 320 | visited.insert(start_node.node_id()); |
dfeec247 | 321 | DepthFirstTraversal { graph, stack: vec![start_node], visited, direction } |
8faf50e0 XL |
322 | } |
323 | ||
324 | fn visit(&mut self, node: NodeIndex) { | |
325 | if self.visited.insert(node.node_id()) { | |
326 | self.stack.push(node); | |
327 | } | |
328 | } | |
329 | } | |
330 | ||
331 | impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> { | |
332 | type Item = NodeIndex; | |
333 | ||
334 | fn next(&mut self) -> Option<NodeIndex> { | |
335 | let next = self.stack.pop(); | |
336 | if let Some(idx) = next { | |
337 | for (_, edge) in self.graph.adjacent_edges(idx, self.direction) { | |
338 | let target = edge.source_or_target(self.direction); | |
339 | self.visit(target); | |
340 | } | |
341 | } | |
342 | next | |
343 | } | |
344 | ||
345 | fn size_hint(&self) -> (usize, Option<usize>) { | |
346 | // We will visit every node in the graph exactly once. | |
347 | let remaining = self.graph.len_nodes() - self.visited.count(); | |
348 | (remaining, Some(remaining)) | |
349 | } | |
350 | } | |
351 | ||
352 | impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {} | |
353 | ||
354 | impl<E> Edge<E> { | |
355 | pub fn source(&self) -> NodeIndex { | |
356 | self.source | |
357 | } | |
358 | ||
359 | pub fn target(&self) -> NodeIndex { | |
360 | self.target | |
361 | } | |
362 | ||
363 | pub fn source_or_target(&self, direction: Direction) -> NodeIndex { | |
dfeec247 | 364 | if direction == OUTGOING { self.target } else { self.source } |
8faf50e0 XL |
365 | } |
366 | } |