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.
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.
13 use graph::test::TestGraph;
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);
26 // The order in which things will be visited is important to this
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.
46 let graph = TestGraph::new(0, &[
53 let sccs: Sccs<_, usize> = Sccs::new(&graph);
54 assert_eq!(sccs.num_sccs(), 1);
58 fn test_three_sccs() {
68 let graph = TestGraph::new(0, &[
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]);
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
101 let graph = TestGraph::new(0, &[
111 // For this graph, we will start in our DFS by visiting:
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 }`.
122 // When we finally traverse the `0 -> 4` edge and then visit node 2,
123 // the states of the nodes are:
125 // 0 BeingVisited { 0 }
126 // 1 InCycleWith { 3 }
127 // 2 InCycleWith { 1 }
128 // 3 InCycleWith { 0 }
130 // and hence 4 will traverse the links, finding an ultimate depth of 0.
131 // If will also collapse the states to the following:
133 // 0 BeingVisited { 0 }
134 // 1 InCycleWith { 3 }
135 // 2 InCycleWith { 1 }
136 // 3 InCycleWith { 0 }
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), &[]);
149 fn test_find_state_3() {
160 let graph = TestGraph::new(0, &[
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]);