src/librustc_data_structures/graph/scc/test.rs

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