src/librustc_data_structures/graph/implementation/tests.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use graph::*;
  12 use std::fmt::Debug;
  13
  14 type TestGraph = Graph<&'static str, &'static str>;
  15
  16 fn create_graph() -> TestGraph {
  17     let mut graph = Graph::new();
  18
  19     // Create a simple graph
  20     //
  21     //          F
  22     //          |
  23     //          V
  24     //    A --> B --> C
  25     //          |     ^
  26     //          v     |
  27     //          D --> E
  28
  29     let a = graph.add_node("A");
  30     let b = graph.add_node("B");
  31     let c = graph.add_node("C");
  32     let d = graph.add_node("D");
  33     let e = graph.add_node("E");
  34     let f = graph.add_node("F");
  35
  36     graph.add_edge(a, b, "AB");
  37     graph.add_edge(b, c, "BC");
  38     graph.add_edge(b, d, "BD");
  39     graph.add_edge(d, e, "DE");
  40     graph.add_edge(e, c, "EC");
  41     graph.add_edge(f, b, "FB");
  42
  43     return graph;
  44 }
  45
  46 #[test]
  47 fn each_node() {
  48     let graph = create_graph();
  49     let expected = ["A", "B", "C", "D", "E", "F"];
  50     graph.each_node(|idx, node| {
  51         assert_eq!(&expected[idx.0], graph.node_data(idx));
  52         assert_eq!(expected[idx.0], node.data);
  53         true
  54     });
  55 }
  56
  57 #[test]
  58 fn each_edge() {
  59     let graph = create_graph();
  60     let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
  61     graph.each_edge(|idx, edge| {
  62         assert_eq!(expected[idx.0], edge.data);
  63         true
  64     });
  65 }
  66
  67 fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(graph: &Graph<N, E>,
  68                                                                    start_index: NodeIndex,
  69                                                                    start_data: N,
  70                                                                    expected_incoming: &[(E, N)],
  71                                                                    expected_outgoing: &[(E, N)]) {
  72     assert!(graph.node_data(start_index) == &start_data);
  73
  74     let mut counter = 0;
  75     for (edge_index, edge) in graph.incoming_edges(start_index) {
  76         assert!(counter < expected_incoming.len());
  77         debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
  78                counter,
  79                expected_incoming[counter],
  80                edge_index,
  81                edge);
  82         match expected_incoming[counter] {
  83             (ref e, ref n) => {
  84                 assert!(e == &edge.data);
  85                 assert!(n == graph.node_data(edge.source()));
  86                 assert!(start_index == edge.target);
  87             }
  88         }
  89         counter += 1;
  90     }
  91     assert_eq!(counter, expected_incoming.len());
  92
  93     let mut counter = 0;
  94     for (edge_index, edge) in graph.outgoing_edges(start_index) {
  95         assert!(counter < expected_outgoing.len());
  96         debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
  97                counter,
  98                expected_outgoing[counter],
  99                edge_index,
 100                edge);
 101         match expected_outgoing[counter] {
 102             (ref e, ref n) => {
 103                 assert!(e == &edge.data);
 104                 assert!(start_index == edge.source);
 105                 assert!(n == graph.node_data(edge.target));
 106             }
 107         }
 108         counter += 1;
 109     }
 110     assert_eq!(counter, expected_outgoing.len());
 111 }
 112
 113 #[test]
 114 fn each_adjacent_from_a() {
 115     let graph = create_graph();
 116     test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]);
 117 }
 118
 119 #[test]
 120 fn each_adjacent_from_b() {
 121     let graph = create_graph();
 122     test_adjacent_edges(&graph,
 123                         NodeIndex(1),
 124                         "B",
 125                         &[("FB", "F"), ("AB", "A")],
 126                         &[("BD", "D"), ("BC", "C")]);
 127 }
 128
 129 #[test]
 130 fn each_adjacent_from_c() {
 131     let graph = create_graph();
 132     test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
 133 }
 134
 135 #[test]
 136 fn each_adjacent_from_d() {
 137     let graph = create_graph();
 138     test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);
 139 }