1 use crate::indexed_vec::{Idx, IndexVec};
2 use crate::graph::{DirectedGraph, WithNumNodes, WithNumEdges, WithSuccessors, GraphSuccessors};
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>,
20 impl<N: Idx> VecGraph<N> {
23 mut edge_pairs: Vec<(N, N)>,
25 // Sort the edges by the source -- this is important.
28 let num_edges = edge_pairs.len();
30 // Store the *target* of each edge into `edge_targets`.
31 let edge_targets: Vec<N> = edge_pairs.iter().map(|&(_, target)| target).collect();
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)]`:
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]`
52 while node_starts.len() <= source.index() {
53 node_starts.push(index);
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]`.
61 // Interpretation of that vector:
67 while node_starts.len() <= num_nodes {
68 node_starts.push(edge_targets.len());
71 assert_eq!(node_starts.len(), num_nodes + 1);
73 Self { node_starts, edge_targets }
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]
84 impl<N: Idx> DirectedGraph for VecGraph<N> {
88 impl<N: Idx> WithNumNodes for VecGraph<N> {
89 fn num_nodes(&self) -> usize {
90 self.node_starts.len() - 1
94 impl<N: Idx> WithNumEdges for VecGraph<N> {
95 fn num_edges(&self) -> usize {
96 self.edge_targets.len()
100 impl<N: Idx> GraphSuccessors<'graph> for VecGraph<N> {
103 type Iter = std::iter::Cloned<std::slice::Iter<'graph, N>>;
106 impl<N: Idx> WithSuccessors for VecGraph<N> {
107 fn successors<'graph>(
110 ) -> <Self as GraphSuccessors<'graph>>::Iter {
111 self.successors(node).iter().cloned()