summaryrefslogtreecommitdiffstats
path: root/taskcluster/taskgraph/test/test_graph.py
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /taskcluster/taskgraph/test/test_graph.py
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'taskcluster/taskgraph/test/test_graph.py')
-rw-r--r--taskcluster/taskgraph/test/test_graph.py157
1 files changed, 157 insertions, 0 deletions
diff --git a/taskcluster/taskgraph/test/test_graph.py b/taskcluster/taskgraph/test/test_graph.py
new file mode 100644
index 000000000..5c4c950a7
--- /dev/null
+++ b/taskcluster/taskgraph/test/test_graph.py
@@ -0,0 +1,157 @@
+# -*- coding: utf-8 -*-
+
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import absolute_import, print_function, unicode_literals
+
+import unittest
+
+from ..graph import Graph
+from mozunit import main
+
+
+class TestGraph(unittest.TestCase):
+
+ tree = Graph(set(['a', 'b', 'c', 'd', 'e', 'f', 'g']), {
+ ('a', 'b', 'L'),
+ ('a', 'c', 'L'),
+ ('b', 'd', 'K'),
+ ('b', 'e', 'K'),
+ ('c', 'f', 'N'),
+ ('c', 'g', 'N'),
+ })
+
+ linear = Graph(set(['1', '2', '3', '4']), {
+ ('1', '2', 'L'),
+ ('2', '3', 'L'),
+ ('3', '4', 'L'),
+ })
+
+ diamonds = Graph(set(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']),
+ set(tuple(x) for x in
+ 'AFL ADL BDL BEL CEL CHL DFL DGL EGL EHL FIL GIL GJL HJL'.split()
+ ))
+
+ multi_edges = Graph(set(['1', '2', '3', '4']), {
+ ('2', '1', 'red'),
+ ('2', '1', 'blue'),
+ ('3', '1', 'red'),
+ ('3', '2', 'blue'),
+ ('3', '2', 'green'),
+ ('4', '3', 'green'),
+ })
+
+ disjoint = Graph(set(['1', '2', '3', '4', 'α', 'β', 'γ']), {
+ ('2', '1', 'red'),
+ ('3', '1', 'red'),
+ ('3', '2', 'green'),
+ ('4', '3', 'green'),
+ ('α', 'β', 'πράσινο'),
+ ('β', 'γ', 'κόκκινο'),
+ ('α', 'γ', 'μπλε'),
+ })
+
+ def test_transitive_closure_empty(self):
+ "transitive closure of an empty set is an empty graph"
+ g = Graph(set(['a', 'b', 'c']), {('a', 'b', 'L'), ('a', 'c', 'L')})
+ self.assertEqual(g.transitive_closure(set()),
+ Graph(set(), set()))
+
+ def test_transitive_closure_disjoint(self):
+ "transitive closure of a disjoint set is a subset"
+ g = Graph(set(['a', 'b', 'c']), set())
+ self.assertEqual(g.transitive_closure(set(['a', 'c'])),
+ Graph(set(['a', 'c']), set()))
+
+ def test_transitive_closure_trees(self):
+ "transitive closure of a tree, at two non-root nodes, is the two subtrees"
+ self.assertEqual(self.tree.transitive_closure(set(['b', 'c'])),
+ Graph(set(['b', 'c', 'd', 'e', 'f', 'g']), {
+ ('b', 'd', 'K'),
+ ('b', 'e', 'K'),
+ ('c', 'f', 'N'),
+ ('c', 'g', 'N'),
+ }))
+
+ def test_transitive_closure_multi_edges(self):
+ "transitive closure of a tree with multiple edges between nodes keeps those edges"
+ self.assertEqual(self.multi_edges.transitive_closure(set(['3'])),
+ Graph(set(['1', '2', '3']), {
+ ('2', '1', 'red'),
+ ('2', '1', 'blue'),
+ ('3', '1', 'red'),
+ ('3', '2', 'blue'),
+ ('3', '2', 'green'),
+ }))
+
+ def test_transitive_closure_disjoint_edges(self):
+ "transitive closure of a disjoint graph keeps those edges"
+ self.assertEqual(self.disjoint.transitive_closure(set(['3', 'β'])),
+ Graph(set(['1', '2', '3', 'β', 'γ']), {
+ ('2', '1', 'red'),
+ ('3', '1', 'red'),
+ ('3', '2', 'green'),
+ ('β', 'γ', 'κόκκινο'),
+ }))
+
+ def test_transitive_closure_linear(self):
+ "transitive closure of a linear graph includes all nodes in the line"
+ self.assertEqual(self.linear.transitive_closure(set(['1'])), self.linear)
+
+ def test_visit_postorder_empty(self):
+ "postorder visit of an empty graph is empty"
+ self.assertEqual(list(Graph(set(), set()).visit_postorder()), [])
+
+ def assert_postorder(self, seq, all_nodes):
+ seen = set()
+ for e in seq:
+ for l, r, n in self.tree.edges:
+ if l == e:
+ self.failUnless(r in seen)
+ seen.add(e)
+ self.assertEqual(seen, all_nodes)
+
+ def test_visit_postorder_tree(self):
+ "postorder visit of a tree satisfies invariant"
+ self.assert_postorder(self.tree.visit_postorder(), self.tree.nodes)
+
+ def test_visit_postorder_diamonds(self):
+ "postorder visit of a graph full of diamonds satisfies invariant"
+ self.assert_postorder(self.diamonds.visit_postorder(), self.diamonds.nodes)
+
+ def test_visit_postorder_multi_edges(self):
+ "postorder visit of a graph with duplicate edges satisfies invariant"
+ self.assert_postorder(self.multi_edges.visit_postorder(), self.multi_edges.nodes)
+
+ def test_visit_postorder_disjoint(self):
+ "postorder visit of a disjoint graph satisfies invariant"
+ self.assert_postorder(self.disjoint.visit_postorder(), self.disjoint.nodes)
+
+ def test_links_dict(self):
+ "link dict for a graph with multiple edges is correct"
+ self.assertEqual(self.multi_edges.links_dict(), {
+ '2': set(['1']),
+ '3': set(['1', '2']),
+ '4': set(['3']),
+ })
+
+ def test_named_links_dict(self):
+ "named link dict for a graph with multiple edges is correct"
+ self.assertEqual(self.multi_edges.named_links_dict(), {
+ '2': dict(red='1', blue='1'),
+ '3': dict(red='1', blue='2', green='2'),
+ '4': dict(green='3'),
+ })
+
+ def test_reverse_links_dict(self):
+ "reverse link dict for a graph with multiple edges is correct"
+ self.assertEqual(self.multi_edges.reverse_links_dict(), {
+ '1': set(['2', '3']),
+ '2': set(['3']),
+ '3': set(['4']),
+ })
+
+if __name__ == '__main__':
+ main()