1 //! A graph module for use in dataflow, region resolution, and elsewhere.
3 //! # Interface details
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.
11 //! # Implementation details
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
17 //! incoming list and some outgoing list. Basically you can load the
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`).
23 use crate::bit_set
::BitSet
;
24 use crate::snapshot_vec
::{SnapshotVec, SnapshotVecDelegate}
;
31 pub struct Graph
<N
, E
> {
32 nodes
: SnapshotVec
<Node
<N
>>,
33 edges
: SnapshotVec
<Edge
<E
>>,
37 first_edge
: [EdgeIndex
; 2], // see module comment
43 next_edge
: [EdgeIndex
; 2], // see module comment
49 impl<N
> SnapshotVecDelegate
for Node
<N
> {
53 fn reverse(_
: &mut Vec
<Node
<N
>>, _
: ()) {}
56 impl<N
> SnapshotVecDelegate
for Edge
<N
> {
60 fn reverse(_
: &mut Vec
<Edge
<N
>>, _
: ()) {}
63 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
64 pub struct NodeIndex(pub usize);
66 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
67 pub struct EdgeIndex(pub usize);
69 pub const INVALID_EDGE_INDEX
: EdgeIndex
= EdgeIndex(usize::MAX
);
71 // Use a private field here to guarantee no more instances are created:
72 #[derive(Copy, Clone, Debug, PartialEq)]
73 pub struct Direction
{
77 pub const OUTGOING
: Direction
= Direction { repr: 0 }
;
79 pub const INCOMING
: Direction
= Direction { repr: 1 }
;
82 /// Returns unique ID (unique with respect to the graph holding associated node).
83 pub fn node_id(self) -> usize {
88 impl<N
: Debug
, E
: Debug
> Graph
<N
, E
> {
89 pub fn new() -> Graph
<N
, E
> {
91 nodes
: SnapshotVec
::new(),
92 edges
: SnapshotVec
::new(),
96 pub fn with_capacity(nodes
: usize, edges
: usize) -> Graph
<N
, E
> {
98 nodes
: SnapshotVec
::with_capacity(nodes
),
99 edges
: SnapshotVec
::with_capacity(edges
),
103 // # Simple accessors
106 pub fn all_nodes(&self) -> &[Node
<N
>] {
111 pub fn len_nodes(&self) -> usize {
116 pub fn all_edges(&self) -> &[Edge
<E
>] {
121 pub fn len_edges(&self) -> usize {
125 // # Node construction
127 pub fn next_node_index(&self) -> NodeIndex
{
128 NodeIndex(self.nodes
.len())
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
],
140 pub fn mut_node_data(&mut self, idx
: NodeIndex
) -> &mut N
{
141 &mut self.nodes
[idx
.0].data
144 pub fn node_data(&self, idx
: NodeIndex
) -> &N
{
145 &self.nodes
[idx
.0].data
148 pub fn node(&self, idx
: NodeIndex
) -> &Node
<N
> {
152 // # Edge construction and queries
154 pub fn next_edge_index(&self) -> EdgeIndex
{
155 EdgeIndex(self.edges
.len())
158 pub fn add_edge(&mut self, source
: NodeIndex
, target
: NodeIndex
, data
: E
) -> EdgeIndex
{
159 debug
!("graph: add_edge({:?}, {:?}, {:?})", source
, target
, data
);
161 let idx
= self.next_edge_index();
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
];
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
],
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
;
183 pub fn edge(&self, idx
: EdgeIndex
) -> &Edge
<E
> {
187 // # Iterating over nodes, edges
189 pub fn enumerated_nodes(&self) -> impl Iterator
<Item
= (NodeIndex
, &Node
<N
>)> {
193 .map(|(idx
, n
)| (NodeIndex(idx
), n
))
196 pub fn enumerated_edges(&self) -> impl Iterator
<Item
= (EdgeIndex
, &Edge
<E
>)> {
200 .map(|(idx
, e
)| (EdgeIndex(idx
), e
))
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
))
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
))
215 pub fn outgoing_edges(&self, source
: NodeIndex
) -> AdjacentEdges
<'_
, N
, E
> {
216 self.adjacent_edges(source
, OUTGOING
)
219 pub fn incoming_edges(&self, source
: NodeIndex
) -> AdjacentEdges
<'_
, N
, E
> {
220 self.adjacent_edges(source
, INCOMING
)
223 pub fn adjacent_edges(
227 ) -> AdjacentEdges
<'_
, N
, E
> {
228 let first_edge
= self.node(source
).first_edge
[direction
.repr
];
236 pub fn successor_nodes
<'a
>(
239 ) -> impl Iterator
<Item
= NodeIndex
> + 'a
{
240 self.outgoing_edges(source
).targets()
243 pub fn predecessor_nodes
<'a
>(
246 ) -> impl Iterator
<Item
= NodeIndex
> + 'a
{
247 self.incoming_edges(target
).sources()
250 pub fn depth_traverse
<'a
>(
253 direction
: Direction
,
254 ) -> DepthFirstTraversal
<'a
, N
, E
> {
255 DepthFirstTraversal
::with_start_node(self, start
, direction
)
258 pub fn nodes_in_postorder(
260 direction
: Direction
,
261 entry_node
: NodeIndex
,
262 ) -> Vec
<NodeIndex
> {
263 let mut visited
= BitSet
::new_empty(self.len_nodes());
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
)));
272 for node
in Some(entry_node
)
274 .chain(self.enumerated_nodes().map(|(node
, _
)| node
))
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
);
291 assert_eq
!(result
.len(), self.len_nodes());
298 pub struct AdjacentEdges
<'g
, N
, E
> {
299 graph
: &'g Graph
<N
, E
>,
300 direction
: Direction
,
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
)
309 fn sources(self) -> impl Iterator
<Item
= NodeIndex
> + 'g
{
310 self.into_iter().map(|(_
, edge
)| edge
.source
)
314 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for AdjacentEdges
<'g
, N
, E
> {
315 type Item
= (EdgeIndex
, &'g Edge
<E
>);
317 fn next(&mut self) -> Option
<(EdgeIndex
, &'g Edge
<E
>)> {
318 let edge_index
= self.next
;
319 if edge_index
== INVALID_EDGE_INDEX
{
323 let edge
= self.graph
.edge(edge_index
);
324 self.next
= edge
.next_edge
[self.direction
.repr
];
325 Some((edge_index
, edge
))
328 fn size_hint(&self) -> (usize, Option
<usize>) {
329 // At most, all the edges in the graph.
330 (0, Some(self.graph
.len_edges()))
334 pub struct DepthFirstTraversal
<'g
, N
, E
> {
335 graph
: &'g Graph
<N
, E
>,
336 stack
: Vec
<NodeIndex
>,
337 visited
: BitSet
<usize>,
338 direction
: Direction
,
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
,
347 let mut visited
= BitSet
::new_empty(graph
.len_nodes());
348 visited
.insert(start_node
.node_id());
349 DepthFirstTraversal
{
351 stack
: vec
![start_node
],
357 fn visit(&mut self, node
: NodeIndex
) {
358 if self.visited
.insert(node
.node_id()) {
359 self.stack
.push(node
);
364 impl<'g
, N
: Debug
, E
: Debug
> Iterator
for DepthFirstTraversal
<'g
, N
, E
> {
365 type Item
= NodeIndex
;
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
);
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
))
385 impl<'g
, N
: Debug
, E
: Debug
> ExactSizeIterator
for DepthFirstTraversal
<'g
, N
, E
> {}
388 pub fn source(&self) -> NodeIndex
{
392 pub fn target(&self) -> NodeIndex
{
396 pub fn source_or_target(&self, direction
: Direction
) -> NodeIndex
{
397 if direction
== OUTGOING
{