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