count_cycles_unittest.py 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. #!/usr/bin/env python3
  2. # Copyright 2020 The Chromium Authors. All rights reserved.
  3. # Use of this source code is governed by a BSD-style license that can be
  4. # found in the LICENSE file.
  5. """Unit tests for dependency_analysis.count_cycles."""
  6. import itertools
  7. import unittest
  8. import count_cycles
  9. import graph
  10. class TestFindCycles(unittest.TestCase):
  11. """Unit tests for find_cycles."""
  12. KEY_0 = '0'
  13. KEY_1 = '1'
  14. KEY_2 = '2'
  15. KEY_3 = '3'
  16. MAX_CYCLE_LENGTH = 10
  17. def test_no_self_cycles(self):
  18. """Tests that self-cycles are not considered.
  19. 0 <---+
  20. ^ |
  21. | v
  22. +---> 1 (plus, 0 and 1 have self-cycles)
  23. (one cycle, 010)
  24. """
  25. test_graph = graph.Graph()
  26. test_graph.add_edge_if_new(self.KEY_0, self.KEY_1)
  27. test_graph.add_edge_if_new(self.KEY_1, self.KEY_0)
  28. test_graph.add_edge_if_new(self.KEY_0, self.KEY_0)
  29. test_graph.add_edge_if_new(self.KEY_1, self.KEY_1)
  30. res = count_cycles.find_cycles(test_graph, self.MAX_CYCLE_LENGTH)
  31. expected_cycles = {
  32. 2: 1,
  33. }
  34. for cycle_length, cycles in enumerate(res):
  35. self.assertEqual(len(cycles), expected_cycles.get(cycle_length, 0))
  36. def test_big_cycle(self):
  37. """Tests using a graph with one big cycle.
  38. 0 -> 1
  39. ^ |
  40. | v
  41. 3 <- 2
  42. (one cycle, 01230)
  43. """
  44. test_graph = graph.Graph()
  45. test_graph.add_edge_if_new(self.KEY_0, self.KEY_1)
  46. test_graph.add_edge_if_new(self.KEY_1, self.KEY_2)
  47. test_graph.add_edge_if_new(self.KEY_2, self.KEY_3)
  48. test_graph.add_edge_if_new(self.KEY_3, self.KEY_0)
  49. res = count_cycles.find_cycles(test_graph, self.MAX_CYCLE_LENGTH)
  50. expected_cycles = {
  51. 4: 1,
  52. }
  53. for cycle_length, cycles in enumerate(res):
  54. self.assertEqual(len(cycles), expected_cycles.get(cycle_length, 0))
  55. def test_multiple_cycles(self):
  56. """Tests using a graph with multiple cycles.
  57. 0 -> 1
  58. ^ ^
  59. | v
  60. +--- 2 -> 3
  61. (two cycles, 0120 and 121)
  62. """
  63. test_graph = graph.Graph()
  64. test_graph.add_edge_if_new(self.KEY_0, self.KEY_1)
  65. test_graph.add_edge_if_new(self.KEY_1, self.KEY_2)
  66. test_graph.add_edge_if_new(self.KEY_2, self.KEY_0)
  67. test_graph.add_edge_if_new(self.KEY_2, self.KEY_1)
  68. test_graph.add_edge_if_new(self.KEY_2, self.KEY_3)
  69. res = count_cycles.find_cycles(test_graph, self.MAX_CYCLE_LENGTH)
  70. expected_cycles = {
  71. 2: 1,
  72. 3: 1,
  73. }
  74. for cycle_length, cycles in enumerate(res):
  75. self.assertEqual(len(cycles), expected_cycles.get(cycle_length, 0))
  76. def test_complete_graph(self):
  77. """Tests using a complete graph on 4 nodes.
  78. +------------+
  79. v |
  80. 0 <> 1 <--+ |
  81. ^ ^ | |
  82. | v v |
  83. +--> 2 <> 3 <+
  84. (20 cycles,
  85. 010, 020, 030, 121, 131, 232,
  86. 0120, 0130, 0210, 0230, 0310, 0320, 1231, 1321,
  87. 01230, 01320, 02130, 02310, 03120, 03210)
  88. """
  89. test_graph = graph.Graph()
  90. for ka, kb in itertools.permutations(
  91. [self.KEY_0, self.KEY_1, self.KEY_2, self.KEY_3], 2):
  92. test_graph.add_edge_if_new(ka, kb)
  93. res = count_cycles.find_cycles(test_graph, self.MAX_CYCLE_LENGTH)
  94. expected_cycles = {2: 6, 3: 8, 4: 6}
  95. for cycle_length, cycles in enumerate(res):
  96. self.assertEqual(len(cycles), expected_cycles.get(cycle_length, 0))
  97. def test_complete_graph_restricted_length(self):
  98. """Tests using a complete graph on 4 nodes with maximum cycle length 2.
  99. +------------+
  100. v |
  101. 0 <> 1 <--+ |
  102. ^ ^ | |
  103. | v v |
  104. +--> 2 <> 3 <+
  105. (6 cycles, 010, 020, 030, 121, 131, 232)
  106. """
  107. test_graph = graph.Graph()
  108. for ka, kb in itertools.permutations(
  109. [self.KEY_0, self.KEY_1, self.KEY_2, self.KEY_3], 2):
  110. test_graph.add_edge_if_new(ka, kb)
  111. res = count_cycles.find_cycles(test_graph, 2)
  112. expected_cycles = {2: 6}
  113. for cycle_length, cycles in enumerate(res):
  114. self.assertEqual(len(cycles), expected_cycles.get(cycle_length, 0))