p2panda_rs/graph/
graph.rs

1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3use log::debug;
4use std::collections::HashMap;
5use std::fmt::Debug;
6use std::hash::Hash;
7
8use crate::graph::error::{GraphError, ReducerError};
9use crate::graph::Reducer;
10
11/// This struct contains all functionality implemented in this module. It is can be used for
12/// building and sorting a graph of causally connected nodes.
13///
14/// Sorting is deterministic with > comparison of contained node data being the deciding factor on
15/// which paths to walk first.
16///
17/// ## Example
18///
19/// ```
20/// # extern crate p2panda_rs;
21/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
22/// use p2panda_rs::graph::{Graph, Reducer};
23/// use p2panda_rs::graph::error::ReducerError;
24///
25/// // First we define a reducer we will use later on.
26///
27/// #[derive(Default)]
28/// struct CharReducer {
29///     acc: String,
30/// }
31///
32/// impl Reducer<char> for CharReducer {
33///     type Error = ReducerError;
34///
35///     fn combine(&mut self, value: &char) -> Result<(), Self::Error> {
36///         self.acc = format!("{}{}", self.acc, value);
37///         Ok(())
38///     }
39/// }
40///
41/// // Instantiate the graph.
42///
43/// let mut graph = Graph::new();
44///
45/// // Add some nodes to the graph.
46///
47/// graph.add_node(&'a', 'A');
48/// graph.add_node(&'b', 'B');
49/// graph.add_node(&'c', 'C');
50///
51/// assert!(graph.get_node(&'a').is_some());
52/// assert!(graph.get_node(&'x').is_none());
53///
54/// // Add some links between the nodes.
55///
56/// graph.add_link(&'a', &'b');
57/// graph.add_link(&'a', &'c');
58///
59/// // The graph looks like this:
60/// //
61/// //  /--[B]
62/// // [A]<--[C]
63///
64/// // We can sort it topologically and pass in our reducer.
65///
66/// let mut reducer = CharReducer::default();
67/// let nodes = graph.reduce(&mut reducer)?;
68///
69/// assert_eq!(nodes.sorted(), vec!['A', 'B', 'C']);
70/// assert_eq!(reducer.acc, "ABC".to_string());
71///
72/// // Add another link which creates a cycle (oh dear!).
73///
74/// graph.add_link(&'b', &'a');
75///
76/// let mut reducer = CharReducer::default();
77/// assert!(graph.reduce(&mut reducer).is_err());
78///
79/// # Ok(())
80/// # }
81/// ```
82#[derive(Debug, Eq, PartialEq, Clone)]
83pub struct Graph<K, V>(HashMap<K, Node<K, V>>)
84where
85    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
86    V: PartialEq + Clone + Debug;
87
88/// An internal struct which represents a node in the graph and contains generic data.
89#[derive(Debug, Eq, PartialEq, Clone)]
90pub struct Node<K, V>
91where
92    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
93    V: PartialEq + Clone + Debug,
94{
95    key: K,
96    data: V,
97    previous: Vec<K>,
98    next: Vec<K>,
99}
100
101#[derive(Debug, Eq, PartialEq, Clone, Default)]
102pub struct GraphData<V: PartialEq + Clone + Debug> {
103    sorted: Vec<V>,
104    graph_tips: Vec<V>,
105}
106
107impl<V: PartialEq + Clone + Debug> GraphData<V> {
108    /// Returns the data from sorted graph nodes.
109    pub fn sorted(&self) -> Vec<V> {
110        self.sorted.clone()
111    }
112
113    /// Returns the current tips of this graph.
114    pub fn current_graph_tips(&self) -> Vec<V> {
115        self.graph_tips.clone()
116    }
117}
118
119impl<K, V> Node<K, V>
120where
121    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
122    V: PartialEq + Clone + Debug,
123{
124    /// Returns true if this node is the root of this graph.
125    fn is_root(&self) -> bool {
126        self.previous.is_empty()
127    }
128
129    /// Returns true if this is a merge node.
130    fn is_merge(&self) -> bool {
131        self.previous.len() > 1
132    }
133
134    /// Returns true if this is a graph tip.
135    fn is_tip(&self) -> bool {
136        self.next.is_empty()
137    }
138
139    /// Returns the key for this node.
140    fn key(&self) -> &K {
141        &self.key
142    }
143
144    /// Returns a vector of keys for the nodes preceding this node in the graph.
145    fn previous(&self) -> &Vec<K> {
146        &self.previous
147    }
148
149    /// Returns a vector of keys for the nodes following this node in the graph.
150    fn next(&self) -> &Vec<K> {
151        &self.next
152    }
153
154    fn data(&self) -> V {
155        self.data.clone()
156    }
157}
158
159impl<'a, K, V> Graph<K, V>
160where
161    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
162    V: PartialEq + Clone + Debug,
163{
164    /// Instantiate a new empty graph.
165    pub fn new() -> Self {
166        Self(HashMap::new())
167    }
168
169    /// Add a node to the graph. This node will be detached until it is linked to another node.
170    pub fn add_node(&mut self, key: &K, data: V) {
171        let new_node = Node {
172            key: key.clone(),
173            next: Vec::new(),
174            previous: Vec::new(),
175            data,
176        };
177
178        self.0.insert(key.clone(), new_node);
179    }
180
181    /// Add a link between existing nodes to the graph. Returns true if the link was added.
182    /// Returns false if the link was unable to be added. This happens if either of the nodes were
183    /// not present in the graph, or if the link creates a single node loop.
184    pub fn add_link(&mut self, from: &K, to: &K) -> bool {
185        // Check for self-referential links
186        if from == to {
187            return false;
188        }
189
190        // Check that both nodes exist
191        if self.get_node(from).is_none() || self.get_node(to).is_none() {
192            return false;
193        }
194
195        // Add the outgoing link on the source
196        self.0.get_mut(from).unwrap().next.push(to.to_owned());
197
198        // Add the incoming link on the target
199        self.0.get_mut(to).unwrap().previous.push(from.to_owned());
200
201        true
202    }
203
204    /// Get node from the graph by key, returns `None` if it wasn't found.
205    pub fn get_node(&'a self, key: &K) -> Option<&Node<K, V>> {
206        self.0.get(key)
207    }
208
209    /// Returns a reference to the root node of this graph.
210    pub fn root_node(&self) -> Result<&Node<K, V>, GraphError> {
211        let root: Vec<&Node<K, V>> = self.0.values().filter(|node| node.is_root()).collect();
212        match root.len() {
213            0 => Err(GraphError::NoRootNode),
214            1 => Ok(root[0]),
215            _ => Err(GraphError::MultipleRootNodes),
216        }
217    }
218
219    /// Returns the root node key.
220    pub fn root_node_key(&self) -> Result<&K, GraphError> {
221        match self.root_node() {
222            Ok(root) => Ok(root.key()),
223            Err(e) => Err(e),
224        }
225    }
226
227    /// Check if all a nodes dependencies have been visited.
228    fn dependencies_visited(&self, sorted: &[&Node<K, V>], node: &Node<K, V>) -> bool {
229        let mut has_dependencies = true;
230        let previous_nodes = node.previous();
231
232        for node_key in previous_nodes {
233            let node = self.get_node(node_key).expect("Node not in graph");
234            if !sorted.contains(&node) {
235                has_dependencies = false
236            }
237        }
238
239        has_dependencies
240    }
241
242    /// Returns the next un-visited node following the passed node.
243    fn next(&'a self, sorted: &[&Node<K, V>], node: &Node<K, V>) -> Option<Vec<&'a Node<K, V>>> {
244        let mut next_nodes: Vec<&'a Node<K, V>> = Vec::new();
245
246        for node_key in node.next() {
247            // Nodes returned by `next()` have always been added by `add_link()`, which ensures
248            // that these keys all have corresponding nodes in the graph so we can unwrap here.
249            let node = self.get_node(node_key).unwrap();
250            if !sorted
251                .iter()
252                .any(|sorted_node| sorted_node.key() == node.key())
253            {
254                next_nodes.push(node)
255            }
256        }
257
258        if next_nodes.is_empty() {
259            return None;
260        };
261        next_nodes.sort_by_key(|node_a| node_a.key());
262        next_nodes.reverse();
263        Some(next_nodes)
264    }
265
266    /// Returns a new graph instance which has had all nodes removed which aren't causally linked
267    /// to the passed nodes.
268    ///
269    /// Data contained in the returned nodes is unchanged, but the nodes' `next` arrays are edited
270    /// to reflect the new graph connections. The returned graph can be sorted in order to arrive
271    /// at a linear ordering of nodes.
272    pub fn trim(&'a mut self, tip_nodes: &[K]) -> Result<Graph<K, V>, GraphError> {
273        // Instantiate the passed graph tips and make sure they exist in the graph.
274        let mut graph_tips = vec![];
275        for key in tip_nodes {
276            let node = match self.get_node(key) {
277                Some(node) => node.to_owned(),
278                None => return Err(GraphError::InvalidTrimNodes),
279            };
280            graph_tips.push(node)
281        }
282
283        // The queue initially contains all the passed graph tips.
284        let mut queue: Vec<&Node<K, V>> = graph_tips.iter().collect();
285        let mut next_graph_nodes: HashMap<K, Node<K, V>> = HashMap::new();
286
287        while let Some(mut current_node) = queue.pop() {
288            // Push the current node to the graph nodes array.
289            next_graph_nodes.insert(current_node.key().to_owned(), current_node.clone());
290
291            // We now start traversing the graph backwards from this point until we reach the root
292            // or a merge node.
293            while !current_node.previous().is_empty() {
294                if queue.len() > self.0.len() {
295                    return Err(GraphError::CycleDetected);
296                }
297
298                // Collect parent nodes from the graph by their key.
299                let mut parent_nodes: Vec<&Node<K, V>> = current_node
300                    .previous()
301                    .iter()
302                    // Unwrap as all nodes parents should exist in the graph.
303                    .map(|key| self.get_node(key).unwrap())
304                    .collect();
305
306                for parent_node in parent_nodes.clone() {
307                    // If a parent node has already been visited, we retrieve it, if not we set it's
308                    // `next` field to an empty vec. This is done because we don't want to include any
309                    // links to nodes which will be removed.
310                    let mut parent_node_mut = match next_graph_nodes.get(parent_node.key()) {
311                        Some(node) => node.to_owned(),
312                        None => {
313                            // If it hasn't we set it's `next` field to an empty
314                            let mut parent_node = parent_node.clone();
315                            parent_node.next = vec![];
316                            parent_node
317                        }
318                    };
319
320                    // Push the current node's key to the `next` field of the parent_node unless
321                    // it is already included.
322                    if !parent_node_mut.next.contains(current_node.key()) {
323                        parent_node_mut.next.push(current_node.key().to_owned());
324                    }
325
326                    // Insert the parent_node into the next_graph_nodes.
327                    next_graph_nodes.insert(parent_node.key().to_owned(), parent_node_mut.clone());
328                }
329
330                // If this is a merge node push all parent nodes back into the queue
331                // and break out of the loop.
332                if current_node.is_merge() {
333                    for parent_node in parent_nodes {
334                        queue.push(parent_node);
335                    }
336                    break;
337                }
338
339                // Pop and unwrap as we know there is exactly one node in the parent nodes.
340                current_node = parent_nodes.pop().unwrap();
341            }
342        }
343
344        // We need to edit the `next` field of every passed tip node so that they only contain nodes
345        // which exist in the graph.
346        let next_graph_nodes = next_graph_nodes
347            .clone()
348            .iter_mut()
349            .map(|(key, node)| {
350                let tips = node
351                    .next
352                    .iter()
353                    .filter_map(|next_node| {
354                        next_graph_nodes
355                            .get(next_node)
356                            .map(|node| node.key().to_owned())
357                    })
358                    .collect();
359
360                node.next = tips;
361
362                (key.to_owned(), node.to_owned())
363            })
364            .collect();
365
366        Ok(Graph(next_graph_nodes))
367    }
368
369    /// Sorts the graph topologically and returns the result.
370    pub fn walk_from(
371        &'a self,
372        key: &K,
373        reducer: &mut impl Reducer<V>,
374    ) -> Result<GraphData<V>, GraphError> {
375        let root_node = match self.get_node(key) {
376            Some(node) => Ok(node),
377            None => Err(GraphError::NodeNotFound),
378        }?;
379        let mut queue = vec![root_node];
380        let mut sorted_nodes = vec![];
381        let mut graph_data = GraphData {
382            sorted: vec![],
383            graph_tips: vec![],
384        };
385
386        // Pop from the queue while it has items.
387        while let Some(mut current_node) = queue.pop() {
388            // If the sorted stack is bigger than the number of existing nodes we have a cycle.
389            if sorted_nodes.len() > self.0.len() {
390                return Err(GraphError::CycleDetected);
391            }
392            // Push this node to the sorted stack...
393            sorted_nodes.push(current_node);
394            graph_data.sorted.push(current_node.data());
395            if current_node.is_tip() {
396                graph_data.graph_tips.push(current_node.data())
397            }
398
399            // Pass node data into reducer.
400            reducer
401                .combine(&current_node.data)
402                .map_err(|err| ReducerError::Custom(err.to_string()))?;
403
404            debug!(
405                "{:?}: sorted to position {}",
406                current_node.key(),
407                sorted_nodes.len()
408            );
409
410            // ...and then walk the graph starting from this node.
411            while let Some(mut next_nodes) = self.next(&sorted_nodes, current_node) {
412                // Pop off the next node we will visit.
413                //
414                // Nodes returned by `next()` have always been added by `add_link()`, which ensures
415                // that these keys all have corresponding nodes in the graph so we can unwrap.
416                let next_node = next_nodes.pop().unwrap();
417                debug!("visiting: {:?}", next_node.key());
418
419                // Push all other nodes connected to this one to the queue, we will visit these later.
420                while let Some(node_to_be_queued) = next_nodes.pop() {
421                    queue.push(node_to_be_queued);
422                    debug!("{:?}: pushed to queue", node_to_be_queued.key());
423                }
424
425                // If it's a merge node, check it's dependencies have all been visited.
426                if next_node.is_merge() {
427                    if self.dependencies_visited(&sorted_nodes, next_node) {
428                        // If they have been, push this node to the queue and exit this loop.
429                        debug!(
430                            "{:?}: is merge and has all dependencies met",
431                            next_node.key()
432                        );
433                        queue.push(next_node);
434
435                        debug!("{:?}: pushed to queue", next_node.key(),);
436
437                        break;
438                    } else if queue.is_empty() {
439                        // The queue is empty, but this node has dependencies missing then there
440                        // is either a cycle or missing nodes.
441                        return Err(GraphError::BadlyFormedGraph);
442                    }
443
444                    debug!(
445                        "{:?}: is merge and does not have dependencies met",
446                        next_node.key()
447                    );
448                    break;
449                }
450                // If it wasn't a merge node, push it to the sorted stack and keep walking.
451                sorted_nodes.push(next_node);
452                graph_data.sorted.push(next_node.data());
453
454                // If it is a tip, push it to the graph tips list.
455                if next_node.is_tip() {
456                    graph_data.graph_tips.push(next_node.data());
457                }
458
459                // Pass node data into reducer.
460                reducer
461                    .combine(&next_node.data)
462                    .map_err(|err| ReducerError::Custom(err.to_string()))?;
463
464                debug!(
465                    "{:?}: sorted to position {}",
466                    next_node.key(),
467                    sorted_nodes.len()
468                );
469                current_node = next_node;
470            }
471        }
472        Ok(graph_data)
473    }
474
475    /// Sort the entire graph, starting from the root node.
476    ///
477    /// Accepts a mutable reducer as an argument. As each node is sorted into topological order
478    /// its value is passed into the `combine` method.
479    pub fn reduce(&'a self, reducer: &mut impl Reducer<V>) -> Result<GraphData<V>, GraphError> {
480        let root_node = self.root_node_key()?;
481        self.walk_from(root_node, reducer)
482    }
483}
484
485impl<K, V> Default for Graph<K, V>
486where
487    K: Hash + Ord + PartialOrd + Eq + PartialEq + Clone + Debug,
488    V: PartialEq + Clone + Debug,
489{
490    fn default() -> Self {
491        Self::new()
492    }
493}
494
495#[cfg(test)]
496mod test {
497    use crate::graph::error::ReducerError;
498    use crate::graph::{Graph, Reducer};
499
500    use super::GraphData;
501
502    #[derive(Default)]
503    struct CharReducer {
504        acc: String,
505    }
506
507    impl Reducer<char> for CharReducer {
508        type Error = ReducerError;
509
510        fn combine(&mut self, value: &char) -> Result<(), Self::Error> {
511            self.acc = format!("{}{}", self.acc, value);
512            Ok(())
513        }
514    }
515
516    #[derive(Default)]
517    struct CountReducer {
518        count: i32,
519    }
520
521    impl Reducer<i32> for CountReducer {
522        type Error = ReducerError;
523
524        fn combine(&mut self, value: &i32) -> Result<(), Self::Error> {
525            self.count += value;
526            Ok(())
527        }
528    }
529
530    #[derive(Default)]
531    struct PoeticReducer {
532        acc: String,
533    }
534
535    impl Reducer<String> for PoeticReducer {
536        type Error = ReducerError;
537
538        fn combine(&mut self, value: &String) -> Result<(), Self::Error> {
539            self.acc = format!("{}{}\n", self.acc, value);
540            Ok(())
541        }
542    }
543
544    #[test]
545    fn basics() {
546        let mut graph: Graph<char, char> = Graph::default();
547        graph.add_node(&'a', 'A');
548        graph.add_node(&'b', 'B');
549        graph.add_node(&'c', 'C');
550        graph.add_node(&'d', 'D');
551        graph.add_node(&'e', 'E');
552        graph.add_node(&'f', 'F');
553        graph.add_node(&'g', 'G');
554        graph.add_node(&'h', 'H');
555        graph.add_node(&'i', 'I');
556        graph.add_node(&'j', 'J');
557        graph.add_node(&'k', 'K');
558
559        // NB: unlinked nodes are simply not visited and do not exist in the sorted result.
560
561        graph.add_link(&'a', &'b');
562        graph.add_link(&'b', &'c');
563        graph.add_link(&'c', &'d');
564        graph.add_link(&'d', &'e');
565        graph.add_link(&'e', &'f');
566
567        // [A]<--[B]<--[C]<--[D]<--[E]<--[F]
568
569        let expected = GraphData {
570            sorted: vec!['A', 'B', 'C', 'D', 'E', 'F'],
571            graph_tips: vec!['F'],
572        };
573
574        let mut reducer = CharReducer::default();
575        let graph_data = graph.walk_from(&'a', &mut reducer).unwrap();
576
577        assert_eq!(graph_data.sorted(), expected.sorted());
578        assert_eq!(
579            graph_data.current_graph_tips(),
580            expected.current_graph_tips()
581        );
582        assert_eq!(reducer.acc, "ABCDEF".to_string());
583
584        graph.add_link(&'a', &'g');
585        graph.add_link(&'g', &'h');
586        graph.add_link(&'h', &'d');
587
588        //  /--[B]<--[C]--\
589        // [A]<--[G]<-----[H]<--[D]<--[E]<---[F]
590
591        let expected = GraphData {
592            sorted: vec!['A', 'B', 'C', 'G', 'H', 'D', 'E', 'F'],
593            graph_tips: vec!['F'],
594        };
595
596        let mut reducer = CharReducer::default();
597        let graph_data = graph.walk_from(&'a', &mut reducer).unwrap();
598
599        assert_eq!(graph_data.sorted(), expected.sorted());
600        assert_eq!(
601            graph_data.current_graph_tips(),
602            expected.current_graph_tips()
603        );
604        assert_eq!(reducer.acc, "ABCGHDEF".to_string());
605
606        graph.add_link(&'c', &'i');
607        graph.add_link(&'i', &'j');
608        graph.add_link(&'j', &'k');
609        graph.add_link(&'k', &'f');
610
611        //             /--[I]<--[J]<--[K]<--\
612        //  /--[B]<--[C]--\                  \
613        // [A]<--[G]<-----[H]<--[D]<--[E]<---[F]
614        //
615
616        let expected = GraphData {
617            sorted: vec!['A', 'B', 'C', 'I', 'J', 'K', 'G', 'H', 'D', 'E', 'F'],
618            graph_tips: vec!['F'],
619        };
620
621        let mut reducer = CharReducer::default();
622        let graph_data = graph.walk_from(&'a', &mut reducer).unwrap();
623
624        assert_eq!(graph_data.sorted(), expected.sorted());
625        assert_eq!(
626            graph_data.current_graph_tips(),
627            expected.current_graph_tips()
628        );
629        assert_eq!(reducer.acc, "ABCIJKGHDEF".to_string());
630    }
631
632    #[test]
633    fn has_cycle() {
634        let mut graph = Graph::new();
635
636        graph.add_node(&'a', 1);
637        graph.add_node(&'b', 2);
638        graph.add_node(&'c', 3);
639        graph.add_node(&'d', 4);
640
641        // Can't add self-referential links
642        assert!(!graph.add_link(&'a', &'a'));
643
644        // Can't add links to non-existing nodes
645        assert!(!graph.add_link(&'a', &'x'));
646
647        graph.add_link(&'a', &'b');
648        graph.add_link(&'b', &'c');
649        graph.add_link(&'c', &'d');
650        graph.add_link(&'d', &'b');
651
652        let mut reducer = CountReducer::default();
653        assert!(graph.walk_from(&'a', &mut reducer).is_err());
654    }
655
656    #[test]
657    fn missing_dependencies() {
658        let mut graph = Graph::new();
659        graph.add_node(&'a', 1);
660        graph.add_node(&'b', 2);
661        graph.add_node(&'c', 3);
662        graph.add_node(&'d', 4);
663
664        graph.add_link(&'a', &'b');
665        graph.add_link(&'b', &'c');
666        graph.add_link(&'c', &'d');
667        graph.add_link(&'d', &'b');
668        graph.add_link(&'e', &'b'); // 'e' doesn't exist in the graph.
669
670        let mut reducer = CountReducer::default();
671        assert!(graph.walk_from(&'a', &mut reducer).is_err())
672    }
673
674    #[test]
675    fn can_trim_graph() {
676        let mut graph = Graph::new();
677        graph.add_node(&'a', 1);
678        graph.add_node(&'b', 2);
679        graph.add_node(&'c', 3);
680        graph.add_node(&'d', 4);
681        graph.add_node(&'e', 5);
682
683        graph.add_link(&'a', &'b');
684        graph.add_link(&'b', &'c');
685        graph.add_link(&'c', &'d');
686        graph.add_link(&'c', &'e');
687
688        let mut reducer = CountReducer::default();
689        let result = graph.trim(&['d', 'e']).unwrap().reduce(&mut reducer);
690        assert_eq!(result.unwrap().sorted(), [1, 2, 3, 4, 5]);
691        assert_eq!(reducer.count, 15);
692
693        let mut reducer = CountReducer::default();
694        let result = graph.trim(&['c']).unwrap().reduce(&mut reducer);
695        assert_eq!(result.unwrap().sorted(), [1, 2, 3]);
696        assert_eq!(reducer.count, 6);
697
698        let mut reducer = CountReducer::default();
699        let result = graph.trim(&['e']).unwrap().reduce(&mut reducer);
700        assert_eq!(result.unwrap().sorted(), [1, 2, 3, 5]);
701        assert_eq!(reducer.count, 11);
702
703        let mut reducer = CountReducer::default();
704        let result = graph.trim(&['d']).unwrap().reduce(&mut reducer);
705        assert_eq!(result.unwrap().sorted(), [1, 2, 3, 4]);
706        assert_eq!(reducer.count, 10);
707    }
708
709    #[test]
710    fn can_trim_more_complex_graph() {
711        let mut graph = Graph::new();
712        graph.add_node(&'a', 'A');
713        graph.add_node(&'b', 'B');
714        graph.add_node(&'c', 'C');
715        graph.add_node(&'d', 'D');
716        graph.add_node(&'e', 'E');
717        graph.add_node(&'f', 'F');
718        graph.add_node(&'g', 'G');
719        graph.add_node(&'h', 'H');
720        graph.add_node(&'i', 'I');
721        graph.add_node(&'j', 'J');
722        graph.add_node(&'k', 'K');
723
724        graph.add_link(&'a', &'b');
725        graph.add_link(&'b', &'c');
726        graph.add_link(&'c', &'d');
727        graph.add_link(&'d', &'e');
728        graph.add_link(&'e', &'f');
729
730        graph.add_link(&'a', &'g');
731        graph.add_link(&'g', &'h');
732        graph.add_link(&'h', &'d');
733
734        graph.add_link(&'c', &'i');
735        graph.add_link(&'i', &'j');
736        graph.add_link(&'j', &'k');
737        graph.add_link(&'k', &'f');
738
739        //             /--[I]<--[J]<--[K]<--\
740        //  /--[B]<--[C]--\                  \
741        // [A]<--[G]<-----[H]<--[D]<--[E]<---[F]
742        //
743
744        let mut reducer = CharReducer::default();
745        let result = graph.trim(&['k']).unwrap().reduce(&mut reducer);
746        assert_eq!(result.unwrap().sorted(), ['A', 'B', 'C', 'I', 'J', 'K']);
747        assert_eq!(reducer.acc, "ABCIJK".to_string());
748
749        let mut reducer = CharReducer::default();
750        let result = graph.trim(&['k', 'e']).unwrap().reduce(&mut reducer);
751        assert_eq!(
752            result.unwrap().sorted(),
753            ['A', 'B', 'C', 'I', 'J', 'K', 'G', 'H', 'D', 'E']
754        );
755        assert_eq!(reducer.acc, "ABCIJKGHDE".to_string());
756
757        let mut reducer = CharReducer::default();
758        let result = graph.trim(&['f']).unwrap().reduce(&mut reducer);
759        assert_eq!(
760            result.unwrap().sorted(),
761            ['A', 'B', 'C', 'I', 'J', 'K', 'G', 'H', 'D', 'E', 'F']
762        );
763        assert_eq!(reducer.acc, "ABCIJKGHDEF".to_string());
764
765        let mut reducer = CharReducer::default();
766        let result = graph.trim(&['k', 'g']).unwrap().reduce(&mut reducer);
767        assert_eq!(
768            result.unwrap().sorted(),
769            ['A', 'B', 'C', 'I', 'J', 'K', 'G']
770        );
771        assert_eq!(reducer.acc, "ABCIJKG".to_string());
772
773        // This is a weird case, many "tips" are passed, but they all exist in the same branch. It is valid though
774        // and we process it correctly.
775        let mut reducer = CharReducer::default();
776        let result = graph
777            .trim(&['a', 'b', 'c', 'j'])
778            .unwrap()
779            .reduce(&mut reducer);
780        assert_eq!(result.unwrap().sorted(), ['A', 'B', 'C', 'I', 'J']);
781        assert_eq!(reducer.acc, "ABCIJ".to_string());
782    }
783
784    #[test]
785    fn invalid_trim_node_keys() {
786        let mut graph = Graph::new();
787        graph.add_node(&'a', 1);
788        graph.add_node(&'b', 2);
789        graph.add_node(&'c', 3);
790        graph.add_node(&'d', 4);
791        graph.add_node(&'e', 5);
792
793        graph.add_link(&'a', &'b');
794        graph.add_link(&'b', &'c');
795        graph.add_link(&'c', &'d');
796        graph.add_link(&'c', &'e');
797
798        let expected_err = "Requested trim nodes not found in graph";
799        assert_eq!(
800            graph.trim(&['d', 'f']).unwrap_err().to_string(),
801            expected_err
802        );
803        assert_eq!(graph.trim(&['g']).unwrap_err().to_string(), expected_err);
804    }
805
806    #[test]
807    fn trim_can_detect_cycle() {
808        let mut graph = Graph::new();
809
810        graph.add_node(&'a', 1);
811        graph.add_node(&'b', 2);
812        graph.add_node(&'c', 3);
813        graph.add_node(&'d', 4);
814
815        graph.add_link(&'a', &'b');
816        graph.add_link(&'b', &'c');
817        graph.add_link(&'c', &'d');
818        graph.add_link(&'d', &'b');
819
820        let expected_err = "Cycle detected";
821        assert_eq!(graph.trim(&['d']).unwrap_err().to_string(), expected_err);
822    }
823
824    #[test]
825    fn poetic_graph() {
826        let mut graph = Graph::new();
827        graph.add_node(&'a', "Wake Up".to_string());
828        graph.add_node(&'b', "Make Coffee".to_string());
829        graph.add_node(&'c', "Drink Coffee".to_string());
830        graph.add_node(&'d', "Stroke Cat".to_string());
831        graph.add_node(&'e', "Look Out The Window".to_string());
832        graph.add_node(&'f', "Start The Day".to_string());
833        graph.add_node(&'g', "Cat Jumps Off Bed".to_string());
834        graph.add_node(&'h', "Cat Meows".to_string());
835        graph.add_node(&'i', "Brain Receives Caffeine".to_string());
836        graph.add_node(&'j', "Brain Starts Engine".to_string());
837        graph.add_node(&'k', "Brain Starts Thinking".to_string());
838
839        graph.add_link(&'a', &'b');
840        graph.add_link(&'b', &'c');
841        graph.add_link(&'c', &'d');
842        graph.add_link(&'d', &'e');
843        graph.add_link(&'e', &'f');
844
845        graph.add_link(&'a', &'g');
846        graph.add_link(&'g', &'h');
847        graph.add_link(&'h', &'d');
848
849        graph.add_link(&'c', &'i');
850        graph.add_link(&'i', &'j');
851        graph.add_link(&'j', &'k');
852        graph.add_link(&'k', &'f');
853
854        let mut reducer = PoeticReducer::default();
855        graph.walk_from(&'a', &mut reducer).unwrap();
856
857        assert_eq!(
858            reducer.acc,
859            "Wake Up\n".to_string()
860                + "Make Coffee\n"
861                + "Drink Coffee\n"
862                + "Brain Receives Caffeine\n"
863                + "Brain Starts Engine\n"
864                + "Brain Starts Thinking\n"
865                + "Cat Jumps Off Bed\n"
866                + "Cat Meows\n"
867                + "Stroke Cat\n"
868                + "Look Out The Window\n"
869                + "Start The Day\n"
870        )
871    }
872}
p2panda_rs/graph/graph.rs

p2panda_rs/graph/
graph.rs
