graph_unittest.py 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165
  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.graph."""
  6. import unittest
  7. import graph
  8. class TestNode(unittest.TestCase):
  9. """Unit tests for dependency_analysis.graph.Node."""
  10. UNIQUE_KEY_1 = 'abc'
  11. UNIQUE_KEY_2 = 'def'
  12. def test_initialization(self):
  13. """Tests that the node was initialized correctly."""
  14. test_node = graph.Node(self.UNIQUE_KEY_1)
  15. self.assertEqual(test_node.name, self.UNIQUE_KEY_1)
  16. self.assertEqual(len(test_node.inbound), 0)
  17. self.assertEqual(len(test_node.outbound), 0)
  18. def test_equality(self):
  19. """Tests that two nodes with the same unique keys are equal."""
  20. test_node = graph.Node(self.UNIQUE_KEY_1)
  21. equal_node = graph.Node(self.UNIQUE_KEY_1)
  22. self.assertEqual(test_node, equal_node)
  23. def test_add_outbound(self):
  24. """Tests adding a single outbound edge from the node."""
  25. begin_node = graph.Node(self.UNIQUE_KEY_1)
  26. end_node = graph.Node(self.UNIQUE_KEY_2)
  27. begin_node.add_outbound(end_node)
  28. self.assertEqual(begin_node.outbound, {end_node})
  29. def test_add_outbound_duplicate(self):
  30. """Tests that adding the same outbound edge twice will not dupe."""
  31. begin_node = graph.Node(self.UNIQUE_KEY_1)
  32. end_node = graph.Node(self.UNIQUE_KEY_2)
  33. begin_node.add_outbound(end_node)
  34. begin_node.add_outbound(end_node)
  35. self.assertEqual(begin_node.outbound, {end_node})
  36. def test_add_outbound_self(self):
  37. """Tests adding an circular outbound edge to the node itself."""
  38. test_node = graph.Node(self.UNIQUE_KEY_1)
  39. test_node.add_outbound(test_node)
  40. self.assertEqual(test_node.outbound, {test_node})
  41. def test_add_inbound(self):
  42. """Tests adding a single inbound edge to the node."""
  43. begin_node = graph.Node(self.UNIQUE_KEY_1)
  44. end_node = graph.Node(self.UNIQUE_KEY_2)
  45. end_node.add_inbound(begin_node)
  46. self.assertEqual(end_node.inbound, {begin_node})
  47. def test_add_inbound_duplicate(self):
  48. """Tests that adding the same inbound edge twice will not dupe."""
  49. begin_node = graph.Node(self.UNIQUE_KEY_1)
  50. end_node = graph.Node(self.UNIQUE_KEY_2)
  51. end_node.add_inbound(begin_node)
  52. end_node.add_inbound(begin_node)
  53. self.assertEqual(end_node.inbound, {begin_node})
  54. def test_add_inbound_self(self):
  55. """Tests adding an circular inbound edge from the node itself."""
  56. test_node = graph.Node(self.UNIQUE_KEY_1)
  57. test_node.add_inbound(test_node)
  58. self.assertEqual(test_node.inbound, {test_node})
  59. class TestGraph(unittest.TestCase):
  60. """Unit tests for dependency_analysis.graph.Graph."""
  61. UNIQUE_KEY_1 = 'abc'
  62. UNIQUE_KEY_2 = 'def'
  63. def setUp(self):
  64. """Sets up a new graph object."""
  65. self.test_graph = graph.Graph()
  66. def test_initialization(self):
  67. """Tests that the graph was initialized correctly."""
  68. self.assertEqual(self.test_graph.num_nodes, 0)
  69. self.assertEqual(self.test_graph.num_edges, 0)
  70. self.assertEqual(self.test_graph.nodes, [])
  71. self.assertEqual(self.test_graph.edges, [])
  72. def test_get_node_exists(self):
  73. """Tests getting a node that we know exists in the graph."""
  74. self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  75. self.assertIsNotNone(self.test_graph.get_node_by_key(
  76. self.UNIQUE_KEY_1))
  77. def test_get_node_does_not_exist(self):
  78. """Tests getting a node that we know does not exist in the graph."""
  79. self.assertIsNone(self.test_graph.get_node_by_key(self.UNIQUE_KEY_1))
  80. def test_add_nodes(self):
  81. """Tests adding two different nodes to the graph."""
  82. node1 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  83. node2 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_2)
  84. self.assertEqual(self.test_graph.num_nodes, 2)
  85. self.assertEqual(graph.sorted_nodes_by_name(self.test_graph.nodes),
  86. graph.sorted_nodes_by_name([node1, node2]))
  87. def test_add_nodes_duplicate(self):
  88. """Tests adding the same node twice to the graph."""
  89. self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  90. node = self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  91. self.assertEqual(self.test_graph.num_nodes, 1)
  92. self.assertEqual(self.test_graph.nodes, [node])
  93. def test_add_edge(self):
  94. """Tests adding a new edge to the graph."""
  95. node1 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  96. node2 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_2)
  97. self.test_graph.add_edge_if_new(self.UNIQUE_KEY_1, self.UNIQUE_KEY_2)
  98. self.assertEqual(self.test_graph.num_edges, 1)
  99. self.assertEqual(node2.inbound, {node1})
  100. self.assertEqual(node1.outbound, {node2})
  101. self.assertEqual(self.test_graph.edges, [(node1, node2)])
  102. def test_add_edge_double_sided(self):
  103. """Tests adding a bidirectional edge to the graph."""
  104. node1 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  105. node2 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_2)
  106. self.test_graph.add_edge_if_new(self.UNIQUE_KEY_1, self.UNIQUE_KEY_2)
  107. self.test_graph.add_edge_if_new(self.UNIQUE_KEY_2, self.UNIQUE_KEY_1)
  108. self.assertEqual(self.test_graph.num_edges, 2)
  109. self.assertEqual(node1.inbound, {node2})
  110. self.assertEqual(node1.outbound, {node2})
  111. self.assertEqual(node2.inbound, {node1})
  112. self.assertEqual(node2.outbound, {node1})
  113. self.assertEqual(
  114. graph.sorted_edges_by_name(self.test_graph.edges),
  115. graph.sorted_edges_by_name([(node1, node2), (node2, node1)]))
  116. def test_add_edge_duplicate(self):
  117. """Tests adding a duplicate edge to the graph."""
  118. node1 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_1)
  119. node2 = self.test_graph.add_node_if_new(self.UNIQUE_KEY_2)
  120. edge_added_first = self.test_graph.add_edge_if_new(
  121. self.UNIQUE_KEY_1, self.UNIQUE_KEY_2)
  122. edge_added_second = self.test_graph.add_edge_if_new(
  123. self.UNIQUE_KEY_1, self.UNIQUE_KEY_2)
  124. self.assertEqual(self.test_graph.num_edges, 1)
  125. self.assertTrue(edge_added_first)
  126. self.assertFalse(edge_added_second)
  127. self.assertEqual(self.test_graph.edges, [(node1, node2)])
  128. def test_add_edge_nodes_do_not_exist(self):
  129. """Tests adding a new edge to a graph without the edge's nodes."""
  130. self.test_graph.add_edge_if_new(self.UNIQUE_KEY_1, self.UNIQUE_KEY_2)
  131. self.assertEqual(self.test_graph.num_edges, 1)
  132. self.assertIsNotNone(self.test_graph.get_node_by_key(
  133. self.UNIQUE_KEY_1))
  134. self.assertIsNotNone(self.test_graph.get_node_by_key(
  135. self.UNIQUE_KEY_2))
  136. if __name__ == '__main__':
  137. unittest.main()