1 use crate::graph
::{DirectedGraph, GraphSuccessors, WithNumEdges, WithNumNodes, WithSuccessors}
;
2 use rustc_index
::vec
::{Idx, IndexVec}
;
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
> {
21 pub fn new(num_nodes
: usize, mut edge_pairs
: Vec
<(N
, N
)>) -> Self {
22 // Sort the edges by the source -- this is important.
25 let num_edges
= edge_pairs
.len();
27 // Store the *target* of each edge into `edge_targets`.
28 let edge_targets
: Vec
<N
> = edge_pairs
.iter().map(|&(_
, target
)| target
).collect();
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` arary 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)]`:
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]`
49 while node_starts
.len() <= source
.index() {
50 node_starts
.push(index
);
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]`.
58 // Interpretation of that vector:
64 while node_starts
.len() <= num_nodes
{
65 node_starts
.push(edge_targets
.len());
68 assert_eq
!(node_starts
.len(), num_nodes
+ 1);
70 Self { node_starts, edge_targets }
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
]
81 impl<N
: Idx
> DirectedGraph
for VecGraph
<N
> {
85 impl<N
: Idx
> WithNumNodes
for VecGraph
<N
> {
86 fn num_nodes(&self) -> usize {
87 self.node_starts
.len() - 1
91 impl<N
: Idx
> WithNumEdges
for VecGraph
<N
> {
92 fn num_edges(&self) -> usize {
93 self.edge_targets
.len()
97 impl<N
: Idx
> GraphSuccessors
<'graph
> for VecGraph
<N
> {
100 type Iter
= std
::iter
::Cloned
<std
::slice
::Iter
<'graph
, N
>>;
103 impl<N
: Idx
> WithSuccessors
for VecGraph
<N
> {
104 fn successors
<'graph
>(&'graph
self, node
: N
) -> <Self as GraphSuccessors
<'graph
>>::Iter
{
105 self.successors(node
).iter().cloned()