src/librustc_data_structures/graph/scc/test.rs

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