src/librustc_data_structures/graph/scc/tests.rs

   1 use crate::graph::tests::TestGraph;
   2 use super::*;
   3
   4 #[test]
   5 fn diamond() {
   6     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
   7     let sccs: Sccs<_, usize> = Sccs::new(&graph);
   8     assert_eq!(sccs.num_sccs(), 4);
   9     assert_eq!(sccs.num_sccs(), 4);
  10 }
  11
  12 #[test]
  13 fn test_big_scc() {
  14     // The order in which things will be visited is important to this
  15     // test.
  16     //
  17     // We will visit:
  18     //
  19     // 0 -> 1 -> 2 -> 0
  20     //
  21     // and at this point detect a cycle. 2 will return back to 1 which
  22     // will visit 3. 3 will visit 2 before the cycle is complete, and
  23     // hence it too will return a cycle.
  24
  25     /*
  26 +-> 0
  27 |   |
  28 |   v
  29 |   1 -> 3
  30 |   |    |
  31 |   v    |
  32 +-- 2 <--+
  33      */
  34     let graph = TestGraph::new(0, &[
  35         (0, 1),
  36         (1, 2),
  37         (1, 3),
  38         (2, 0),
  39         (3, 2),
  40     ]);
  41     let sccs: Sccs<_, usize> = Sccs::new(&graph);
  42     assert_eq!(sccs.num_sccs(), 1);
  43 }
  44
  45 #[test]
  46 fn test_three_sccs() {
  47     /*
  48     0
  49     |
  50     v
  51 +-> 1    3
  52 |   |    |
  53 |   v    |
  54 +-- 2 <--+
  55      */
  56     let graph = TestGraph::new(0, &[
  57         (0, 1),
  58         (1, 2),
  59         (2, 1),
  60         (3, 2),
  61     ]);
  62     let sccs: Sccs<_, usize> = Sccs::new(&graph);
  63     assert_eq!(sccs.num_sccs(), 3);
  64     assert_eq!(sccs.scc(0), 1);
  65     assert_eq!(sccs.scc(1), 0);
  66     assert_eq!(sccs.scc(2), 0);
  67     assert_eq!(sccs.scc(3), 2);
  68     assert_eq!(sccs.successors(0), &[]);
  69     assert_eq!(sccs.successors(1), &[0]);
  70     assert_eq!(sccs.successors(2), &[0]);
  71 }
  72
  73 #[test]
  74 fn test_find_state_2() {
  75     // The order in which things will be visited is important to this
  76     // test. It tests part of the `find_state` behavior. Here is the
  77     // graph:
  78     //
  79     //
  80     //       /----+
  81     //     0 <--+ |
  82     //     |    | |
  83     //     v    | |
  84     // +-> 1 -> 3 4
  85     // |   |      |
  86     // |   v      |
  87     // +-- 2 <----+
  88
  89     let graph = TestGraph::new(0, &[
  90         (0, 1),
  91         (0, 4),
  92         (1, 2),
  93         (1, 3),
  94         (2, 1),
  95         (3, 0),
  96         (4, 2),
  97     ]);
  98
  99     // For this graph, we will start in our DFS by visiting:
 100     //
 101     // 0 -> 1 -> 2 -> 1
 102     //
 103     // and at this point detect a cycle. The state of 2 will thus be
 104     // `InCycleWith { 1 }`.  We will then visit the 1 -> 3 edge, which
 105     // will attempt to visit 0 as well, thus going to the state
 106     // `InCycleWith { 0 }`. Finally, node 1 will complete; the lowest
 107     // depth of any successor was 3 which had depth 0, and thus it
 108     // will be in the state `InCycleWith { 3 }`.
 109     //
 110     // When we finally traverse the `0 -> 4` edge and then visit node 2,
 111     // the states of the nodes are:
 112     //
 113     // 0 BeingVisited { 0 }
 114     // 1 InCycleWith { 3 }
 115     // 2 InCycleWith { 1 }
 116     // 3 InCycleWith { 0 }
 117     //
 118     // and hence 4 will traverse the links, finding an ultimate depth of 0.
 119     // If will also collapse the states to the following:
 120     //
 121     // 0 BeingVisited { 0 }
 122     // 1 InCycleWith { 3 }
 123     // 2 InCycleWith { 1 }
 124     // 3 InCycleWith { 0 }
 125
 126     let sccs: Sccs<_, usize> = Sccs::new(&graph);
 127     assert_eq!(sccs.num_sccs(), 1);
 128     assert_eq!(sccs.scc(0), 0);
 129     assert_eq!(sccs.scc(1), 0);
 130     assert_eq!(sccs.scc(2), 0);
 131     assert_eq!(sccs.scc(3), 0);
 132     assert_eq!(sccs.scc(4), 0);
 133     assert_eq!(sccs.successors(0), &[]);
 134 }
 135
 136 #[test]
 137 fn test_find_state_3() {
 138     /*
 139       /----+
 140     0 <--+ |
 141     |    | |
 142     v    | |
 143 +-> 1 -> 3 4 5
 144 |   |      | |
 145 |   v      | |
 146 +-- 2 <----+-+
 147      */
 148     let graph = TestGraph::new(0, &[
 149         (0, 1),
 150         (0, 4),
 151         (1, 2),
 152         (1, 3),
 153         (2, 1),
 154         (3, 0),
 155         (4, 2),
 156         (5, 2),
 157     ]);
 158     let sccs: Sccs<_, usize> = Sccs::new(&graph);
 159     assert_eq!(sccs.num_sccs(), 2);
 160     assert_eq!(sccs.scc(0), 0);
 161     assert_eq!(sccs.scc(1), 0);
 162     assert_eq!(sccs.scc(2), 0);
 163     assert_eq!(sccs.scc(3), 0);
 164     assert_eq!(sccs.scc(4), 0);
 165     assert_eq!(sccs.scc(5), 1);
 166     assert_eq!(sccs.successors(0), &[]);
 167     assert_eq!(sccs.successors(1), &[0]);
 168 }