3 use crate::graph::test::TestGraph;
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);
16 // The order in which things will be visited is important to this
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.
36 let graph = TestGraph::new(0, &[
43 let sccs: Sccs<_, usize> = Sccs::new(&graph);
44 assert_eq!(sccs.num_sccs(), 1);
48 fn test_three_sccs() {
58 let graph = TestGraph::new(0, &[
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]);
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
91 let graph = TestGraph::new(0, &[
101 // For this graph, we will start in our DFS by visiting:
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 }`.
112 // When we finally traverse the `0 -> 4` edge and then visit node 2,
113 // the states of the nodes are:
115 // 0 BeingVisited { 0 }
116 // 1 InCycleWith { 3 }
117 // 2 InCycleWith { 1 }
118 // 3 InCycleWith { 0 }
120 // and hence 4 will traverse the links, finding an ultimate depth of 0.
121 // If will also collapse the states to the following:
123 // 0 BeingVisited { 0 }
124 // 1 InCycleWith { 3 }
125 // 2 InCycleWith { 1 }
126 // 3 InCycleWith { 0 }
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), &[]);
139 fn test_find_state_3() {
150 let graph = TestGraph::new(0, &[
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]);