radiate_gp/collections/graphs/
iter.rs

1use crate::collections::GraphNode;
2use std::collections::VecDeque;
3
4pub trait GraphIterator<'a, T> {
5    fn iter_topological(&'a self) -> GraphTopologicalIterator<'a, T>;
6}
7
8impl<'a, G: AsRef<[GraphNode<T>]>, T> GraphIterator<'a, T> for G {
9    fn iter_topological(&'a self) -> GraphTopologicalIterator<'a, T> {
10        GraphTopologicalIterator::new(self.as_ref())
11    }
12}
13
14/// `GraphIterator` is an iterator that traverses a `Graph` in sudo-topological order. I say
15/// "sudo-topological" because it is not a true topological order, but rather a topological order
16/// that allows for recurrent connections. This iterator is used by the `GraphReducer` to evaluate
17/// the nodes in a `Graph` in the correct order.
18pub struct GraphTopologicalIterator<'a, T> {
19    graph: &'a [GraphNode<T>],
20    completed: Vec<bool>,
21    index_queue: VecDeque<usize>,
22    pending_index: usize,
23}
24
25impl<'a, T> GraphTopologicalIterator<'a, T> {
26    /// Create a new `GraphIterator` from a reference to a `Graph`.
27    ///
28    /// # Arguments
29    /// - `graph`: A reference to the `Graph` to iterate over.
30    pub fn new(graph: &'a [GraphNode<T>]) -> Self {
31        GraphTopologicalIterator {
32            graph,
33            completed: vec![false; graph.len()],
34            index_queue: VecDeque::new(),
35            pending_index: 0,
36        }
37    }
38}
39
40/// Implement the `Iterator` trait for `GraphIterator`.
41/// The `Item` type is a reference to a `GraphNode`.
42///
43/// This implementation is a bit more complex than the typical iterator implementation. The iterator
44/// must traverse the graph in a sudo-topological order. This means that it must iterate over the
45/// nodes in the graph in an order that respects the dependencies between the nodes. The iterator
46/// does this by keeping track of which nodes have been completed and which nodes are pending. It
47/// then iterates over the nodes in the graph, checking the dependencies of each node to determine
48/// if it can be completed. If a node can be completed, it is added to the index queue, which is
49/// used to determine the order in which the nodes are returned by the iterator.
50/// It is a 'sudo' topological order because it allows for recurrent connections in the graph.
51impl<'a, T> Iterator for GraphTopologicalIterator<'a, T> {
52    type Item = &'a GraphNode<T>;
53
54    #[inline]
55    fn next(&mut self) -> Option<Self::Item> {
56        let mut min_pending_index = self.graph.len();
57        for index in self.pending_index..self.graph.len() {
58            if self.completed[index] {
59                continue;
60            }
61
62            let node = &self.graph[index];
63            let mut degree = node.incoming().len();
64            for incoming_index in node.incoming() {
65                let incoming_node = &self.graph[*incoming_index];
66                if self.completed[incoming_node.index()] || incoming_node.is_recurrent() {
67                    degree -= 1;
68                }
69            }
70
71            if degree == 0 {
72                self.completed[node.index()] = true;
73                self.index_queue.push_back(node.index());
74            } else {
75                min_pending_index = std::cmp::min(min_pending_index, node.index());
76            }
77        }
78
79        self.pending_index = min_pending_index;
80
81        if let Some(index) = self.index_queue.pop_front() {
82            return Some(&self.graph[index]);
83        }
84
85        None
86    }
87
88    fn size_hint(&self) -> (usize, Option<usize>) {
89        (0, Some(self.graph.len()))
90    }
91
92    fn count(self) -> usize {
93        self.graph.len()
94    }
95}
radiate_gp/collections/graphs/iter.rs

radiate_gp/collections/graphs/
iter.rs
