]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | use crate::graph::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}; |
2 | use rustc_index::vec::{Idx, IndexVec}; | |
3 | ||
4 | #[cfg(test)] | |
5 | mod tests; | |
6 | ||
7 | pub struct VecGraph<N: Idx> { | |
8 | /// Maps from a given node to an index where the set of successors | |
9 | /// for that node starts. The index indexes into the `edges` | |
10 | /// vector. To find the range for a given node, we look up the | |
11 | /// start for that node and then the start for the next node | |
12 | /// (i.e., with an index 1 higher) and get the range between the | |
13 | /// two. This vector always has an extra entry so that this works | |
14 | /// even for the max element. | |
15 | node_starts: IndexVec<N, usize>, | |
16 | ||
17 | edge_targets: Vec<N>, | |
18 | } | |
19 | ||
20 | impl<N: Idx> VecGraph<N> { | |
21 | pub fn new(num_nodes: usize, mut edge_pairs: Vec<(N, N)>) -> Self { | |
22 | // Sort the edges by the source -- this is important. | |
23 | edge_pairs.sort(); | |
24 | ||
25 | let num_edges = edge_pairs.len(); | |
26 | ||
27 | // Store the *target* of each edge into `edge_targets`. | |
28 | let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect(); | |
29 | ||
30 | // Create the *edge starts* array. We are iterating over over | |
31 | // the (sorted) edge pairs. We maintain the invariant that the | |
32 | // length of the `node_starts` array is enough to store the | |
33 | // current source node -- so when we see that the source node | |
34 | // for an edge is greater than the current length, we grow the | |
35 | // edge-starts array by just enough. | |
36 | let mut node_starts = IndexVec::with_capacity(num_edges); | |
37 | for (index, &(source, _)) in edge_pairs.iter().enumerate() { | |
38 | // If we have a list like `[(0, x), (2, y)]`: | |
39 | // | |
40 | // - Start out with `node_starts` of `[]` | |
41 | // - Iterate to `(0, x)` at index 0: | |
42 | // - Push one entry because `node_starts.len()` (0) is <= the source (0) | |
43 | // - Leaving us with `node_starts` of `[0]` | |
44 | // - Iterate to `(2, y)` at index 1: | |
45 | // - Push one entry because `node_starts.len()` (1) is <= the source (2) | |
46 | // - Push one entry because `node_starts.len()` (2) is <= the source (2) | |
47 | // - Leaving us with `node_starts` of `[0, 1, 1]` | |
48 | // - Loop terminates | |
49 | while node_starts.len() <= source.index() { | |
50 | node_starts.push(index); | |
51 | } | |
52 | } | |
53 | ||
54 | // Pad out the `node_starts` array so that it has `num_nodes + | |
55 | // 1` entries. Continuing our example above, if `num_nodes` is | |
56 | // be `3`, we would push one more index: `[0, 1, 1, 2]`. | |
57 | // | |
58 | // Interpretation of that vector: | |
59 | // | |
60 | // [0, 1, 1, 2] | |
61 | // ---- range for N=2 | |
62 | // ---- range for N=1 | |
63 | // ---- range for N=0 | |
64 | while node_starts.len() <= num_nodes { | |
65 | node_starts.push(edge_targets.len()); | |
66 | } | |
67 | ||
68 | assert_eq!(node_starts.len(), num_nodes + 1); | |
69 | ||
70 | Self { node_starts, edge_targets } | |
71 | } | |
72 | ||
73 | /// Gets the successors for `source` as a slice. | |
74 | pub fn successors(&self, source: N) -> &[N] { | |
75 | let start_index = self.node_starts[source]; | |
76 | let end_index = self.node_starts[source.plus(1)]; | |
77 | &self.edge_targets[start_index..end_index] | |
78 | } | |
79 | } | |
80 | ||
81 | impl<N: Idx> DirectedGraph for VecGraph<N> { | |
82 | type Node = N; | |
83 | } | |
84 | ||
85 | impl<N: Idx> WithNumNodes for VecGraph<N> { | |
86 | fn num_nodes(&self) -> usize { | |
87 | self.node_starts.len() - 1 | |
88 | } | |
89 | } | |
90 | ||
91 | impl<N: Idx> WithNumEdges for VecGraph<N> { | |
92 | fn num_edges(&self) -> usize { | |
93 | self.edge_targets.len() | |
94 | } | |
95 | } | |
96 | ||
97 | impl<N: Idx> GraphSuccessors<'graph> for VecGraph<N> { | |
98 | type Item = N; | |
99 | ||
100 | type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>; | |
101 | } | |
102 | ||
103 | impl<N: Idx> WithSuccessors for VecGraph<N> { | |
104 | fn successors(&self, node: N) -> <Self as GraphSuccessors<'_>>::Iter { | |
105 | self.successors(node).iter().cloned() | |
106 | } | |
107 | } |