| 5 | ) |
| 6 | |
| 7 | func TestKahn(t *testing.T) { |
| 8 | testCases := []struct { |
| 9 | name string |
| 10 | n int |
| 11 | dependencies [][]int |
| 12 | wantNil bool |
| 13 | }{ |
| 14 | { |
| 15 | "linear graph", |
| 16 | 3, |
| 17 | [][]int{{0, 1}, {1, 2}}, |
| 18 | false, |
| 19 | }, |
| 20 | { |
| 21 | "diamond graph", |
| 22 | 4, |
| 23 | [][]int{{0, 1}, {0, 2}, {1, 3}, {2, 3}}, |
| 24 | false, |
| 25 | }, |
| 26 | { |
| 27 | "star graph", |
| 28 | 5, |
| 29 | [][]int{{0, 1}, {0, 2}, {0, 3}, {0, 4}}, |
| 30 | false, |
| 31 | }, |
| 32 | { |
| 33 | "disconnected graph", |
| 34 | 5, |
| 35 | [][]int{{0, 1}, {0, 2}, {3, 4}}, |
| 36 | false, |
| 37 | }, |
| 38 | { |
| 39 | "cycle graph 1", |
| 40 | 4, |
| 41 | [][]int{{0, 1}, {1, 2}, {2, 3}, {3, 0}}, |
| 42 | true, |
| 43 | }, |
| 44 | { |
| 45 | "cycle graph 2", |
| 46 | 4, |
| 47 | [][]int{{0, 1}, {1, 2}, {2, 0}, {2, 3}}, |
| 48 | true, |
| 49 | }, |
| 50 | { |
| 51 | "single node graph", |
| 52 | 1, |
| 53 | [][]int{}, |
| 54 | false, |
| 55 | }, |
| 56 | { |
| 57 | "empty graph", |
| 58 | 0, |
| 59 | [][]int{}, |
| 60 | false, |
| 61 | }, |
| 62 | { |
| 63 | "redundant dependencies", |
| 64 | 4, |