src/librustc_data_structures/graph/vec_graph/mod.rs

   1 use crate::indexed_vec::{Idx, IndexVec};
   2 use crate::graph::{DirectedGraph, WithNumNodes, WithNumEdges, WithSuccessors, GraphSuccessors};
   3
   4 #[cfg(test)]
   5 mod test;
   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(
  22         num_nodes: usize,
  23         mut edge_pairs: Vec<(N, N)>,
  24     ) -> Self {
  25         // Sort the edges by the source -- this is important.
  26         edge_pairs.sort();
  27
  28         let num_edges = edge_pairs.len();
  29
  30         // Store the *target* of each edge into `edge_targets`
  31         let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect();
  32
  33         // Create the *edge starts* array. We are iterating over over
  34         // the (sorted) edge pairs. We maintain the invariant that the
  35         // length of the `node_starts` arary is enough to store the
  36         // current source node -- so when we see that the source node
  37         // for an edge is greater than the current length, we grow the
  38         // edge-starts array by just enough.
  39         let mut node_starts = IndexVec::with_capacity(num_edges);
  40         for (index, &(source, _)) in edge_pairs.iter().enumerate() {
  41             // If we have a list like `[(0, x), (2, y)]`:
  42             //
  43             // - Start out with `node_starts` of `[]`
  44             // - Iterate to `(0, x)` at index 0:
  45             //   - Push one entry because `node_starts.len()` (0) is <= the source (0)
  46             //   - Leaving us with `node_starts` of `[0]`
  47             // - Iterate to `(2, y)` at index 1:
  48             //   - Push one entry because `node_starts.len()` (1) is <= the source (2)
  49             //   - Push one entry because `node_starts.len()` (2) is <= the source (2)
  50             //   - Leaving us with `node_starts` of `[0, 1, 1]`
  51             // - Loop terminates
  52             while node_starts.len() <= source.index() {
  53                 node_starts.push(index);
  54             }
  55         }
  56
  57         // Pad out the `node_starts` array so that it has `num_nodes +
  58         // 1` entries. Continuing our example above, if `num_nodes` is
  59         // be `3`, we would push one more index: `[0, 1, 1, 2]`.
  60         //
  61         // Interpretation of that vector:
  62         //
  63         // [0, 1, 1, 2]
  64         //        ---- range for N=2
  65         //     ---- range for N=1
  66         //  ---- range for N=0
  67         while node_starts.len() <= num_nodes {
  68             node_starts.push(edge_targets.len());
  69         }
  70
  71         assert_eq!(node_starts.len(), num_nodes + 1);
  72
  73         Self { node_starts, edge_targets }
  74     }
  75
  76     /// Gets the successors for `source` as a slice.
  77     pub fn successors(&self, source: N) -> &[N] {
  78         let start_index = self.node_starts[source];
  79         let end_index = self.node_starts[source.plus(1)];
  80         &self.edge_targets[start_index..end_index]
  81     }
  82 }
  83
  84 impl<N: Idx> DirectedGraph for VecGraph<N> {
  85     type Node = N;
  86 }
  87
  88 impl<N: Idx> WithNumNodes for VecGraph<N> {
  89     fn num_nodes(&self) -> usize {
  90         self.node_starts.len() - 1
  91     }
  92 }
  93
  94 impl<N: Idx> WithNumEdges for VecGraph<N> {
  95     fn num_edges(&self) -> usize {
  96         self.edge_targets.len()
  97     }
  98 }
  99
 100 impl<N: Idx> GraphSuccessors<'graph> for VecGraph<N> {
 101     type Item = N;
 102
 103     type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>;
 104 }
 105
 106 impl<N: Idx> WithSuccessors for VecGraph<N> {
 107     fn successors<'graph>(
 108         &'graph self,
 109         node: N
 110     ) -> <Self as GraphSuccessors<'graph>>::Iter {
 111         self.successors(node).iter().cloned()
 112     }
 113 }