src/librustc_data_structures/graph/implementation/tests.rs

   1 use crate::graph::implementation::*;
   2 use std::fmt::Debug;
   3
   4 type TestGraph = Graph<&'static str, &'static str>;
   5
   6 fn create_graph() -> TestGraph {
   7     let mut graph = Graph::new();
   8
   9     // Create a simple graph
  10     //
  11     //          F
  12     //          |
  13     //          V
  14     //    A --> B --> C
  15     //          |     ^
  16     //          v     |
  17     //          D --> E
  18
  19     let a = graph.add_node("A");
  20     let b = graph.add_node("B");
  21     let c = graph.add_node("C");
  22     let d = graph.add_node("D");
  23     let e = graph.add_node("E");
  24     let f = graph.add_node("F");
  25
  26     graph.add_edge(a, b, "AB");
  27     graph.add_edge(b, c, "BC");
  28     graph.add_edge(b, d, "BD");
  29     graph.add_edge(d, e, "DE");
  30     graph.add_edge(e, c, "EC");
  31     graph.add_edge(f, b, "FB");
  32
  33     return graph;
  34 }
  35
  36 #[test]
  37 fn each_node() {
  38     let graph = create_graph();
  39     let expected = ["A", "B", "C", "D", "E", "F"];
  40     graph.each_node(|idx, node| {
  41         assert_eq!(&expected[idx.0], graph.node_data(idx));
  42         assert_eq!(expected[idx.0], node.data);
  43         true
  44     });
  45 }
  46
  47 #[test]
  48 fn each_edge() {
  49     let graph = create_graph();
  50     let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
  51     graph.each_edge(|idx, edge| {
  52         assert_eq!(expected[idx.0], edge.data);
  53         true
  54     });
  55 }
  56
  57 fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(
  58     graph: &Graph<N, E>,
  59     start_index: NodeIndex,
  60     start_data: N,
  61     expected_incoming: &[(E, N)],
  62     expected_outgoing: &[(E, N)],
  63 ) {
  64     assert!(graph.node_data(start_index) == &start_data);
  65
  66     let mut counter = 0;
  67     for (edge_index, edge) in graph.incoming_edges(start_index) {
  68         assert!(counter < expected_incoming.len());
  69         debug!(
  70             "counter={:?} expected={:?} edge_index={:?} edge={:?}",
  71             counter, expected_incoming[counter], edge_index, edge
  72         );
  73         match expected_incoming[counter] {
  74             (ref e, ref n) => {
  75                 assert!(e == &edge.data);
  76                 assert!(n == graph.node_data(edge.source()));
  77                 assert!(start_index == edge.target);
  78             }
  79         }
  80         counter += 1;
  81     }
  82     assert_eq!(counter, expected_incoming.len());
  83
  84     let mut counter = 0;
  85     for (edge_index, edge) in graph.outgoing_edges(start_index) {
  86         assert!(counter < expected_outgoing.len());
  87         debug!(
  88             "counter={:?} expected={:?} edge_index={:?} edge={:?}",
  89             counter, expected_outgoing[counter], edge_index, edge
  90         );
  91         match expected_outgoing[counter] {
  92             (ref e, ref n) => {
  93                 assert!(e == &edge.data);
  94                 assert!(start_index == edge.source);
  95                 assert!(n == graph.node_data(edge.target));
  96             }
  97         }
  98         counter += 1;
  99     }
 100     assert_eq!(counter, expected_outgoing.len());
 101 }
 102
 103 #[test]
 104 fn each_adjacent_from_a() {
 105     let graph = create_graph();
 106     test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]);
 107 }
 108
 109 #[test]
 110 fn each_adjacent_from_b() {
 111     let graph = create_graph();
 112     test_adjacent_edges(
 113         &graph,
 114         NodeIndex(1),
 115         "B",
 116         &[("FB", "F"), ("AB", "A")],
 117         &[("BD", "D"), ("BC", "C")],
 118     );
 119 }
 120
 121 #[test]
 122 fn each_adjacent_from_c() {
 123     let graph = create_graph();
 124     test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
 125 }
 126
 127 #[test]
 128 fn each_adjacent_from_d() {
 129     let graph = create_graph();
 130     test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);
 131 }