testresources

Merge lp:~lifeless/testresources/bug-522338 into lp:~testresources-developers/testresources/trunk

  1. bug-522338
  2. Merge into trunk
Proposed by Robert Collins
Status: Merged
Merged at revision: not available
Proposed branch: lp:~lifeless/testresources/bug-522338
Merge into: lp:~testresources-developers/testresources/trunk
Diff against target: 598 lines (+447/-34)
5 files modified
NEWS (+8/-0)
lib/testresources/__init__.py (+248/-28)
lib/testresources/tests/__init__.py (+2/-0)
lib/testresources/tests/test_optimising_test_suite.py (+48/-6)
lib/testresources/tests/test_resource_graph.py (+141/-0)
To merge this branch: bzr merge lp:~lifeless/testresources/bug-522338
Reviewer Review Type Date Requested Status
testresources developers Pending
Review via email: mp+19684@code.launchpad.net
To post a comment you must log in.
Revision history for this message
Robert Collins (lifeless) wrote :

Faster stuff good. Good stuff good. Stuff is good. Faster is good, so stuff is faster.

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
=== modified file 'NEWS'
--- NEWS 2010-02-12 02:01:38 +0000
+++ NEWS 2010-02-19 05:54:16 +0000
@@ -13,6 +13,14 @@
13* Rename TestResource to TestResourceManager leaving TestResource as an alias.13* Rename TestResource to TestResourceManager leaving TestResource as an alias.
14 Fixes bug #520769.14 Fixes bug #520769.
1515
16* Test sorting no longer performs N! work on tests that can never benefit from
17 order optimisations (when resources are not shared an arbitrary order is
18 sufficient). Partial fix for bug #522338.
19
20* Test sorting now uses a heuristic on each partition to get a sort that is
21 no worse than twice the optimal number of setup/teardown operations and is
22 fast to calculate. Fixes bug #522338
23
160.2.3240.2.3
17-----25-----
1826
1927
=== modified file 'lib/testresources/__init__.py'
--- lib/testresources/__init__.py 2010-02-12 02:01:38 +0000
+++ lib/testresources/__init__.py 2010-02-19 05:54:16 +0000
@@ -19,7 +19,9 @@
1919
20"""TestResources: declarative management of external resources for tests."""20"""TestResources: declarative management of external resources for tests."""
2121
22import heapq
22import inspect23import inspect
24import operator
23import unittest25import unittest
2426
2527
@@ -28,6 +30,105 @@
28 return testresources.tests.test_suite()30 return testresources.tests.test_suite()
2931
3032
33def _digraph_to_graph(digraph, prime_node_mapping):
34 """Convert digraph to a graph.
35
36 :param digraph: A directed graph in the form
37 {from:{to:value}}.
38 :param prime_node_mapping: A mapping from every
39 node in digraph to a new unique and not in digraph node.
40 :return: A symmetric graph in the form {from:to:value}} created by
41 creating edges in the result between every N to M-prime with the
42 original N-M value and from every N to N-prime with a cost of 0.
43 No other edges are created.
44 """
45 result = {}
46 for from_node, from_prime_node in prime_node_mapping.iteritems():
47 result[from_node] = {from_prime_node:0}
48 result[from_prime_node] = {from_node:0}
49 for from_node, to_nodes in digraph.iteritems():
50 from_prime = prime_node_mapping[from_node]
51 for to_node, value in to_nodes.iteritems():
52 to_prime = prime_node_mapping[to_node]
53 result[from_prime][to_node] = value
54 result[to_node][from_prime] = value
55 return result
56
57
58def _kruskals_graph_MST(graph):
59 """Find the minimal spanning tree in graph using Kruskals algorithm.
60
61 See http://en.wikipedia.org/wiki/Kruskal%27s_algorithm.
62 :param graph: A graph in {from:{to:value}} form. Every node present in
63 graph must be in the outer dict (because graph is not a directed graph.
64 :return: A graph with all nodes and those vertices that are part of the MST
65 for graph. If graph is not connected, then the result will also be a
66 forest.
67 """
68 # forest contains all the nodes -> graph that node is in.
69 forest = {}
70 # graphs is the count of graphs we have yet to combine.
71 for node in graph:
72 forest[node] = {node:{}}
73 graphs = len(forest)
74 # collect edges: every edge is present twice (due to the graph
75 # representation), so normalise.
76 edges = set()
77 for from_node, to_nodes in graph.iteritems():
78 for to_node, value in to_nodes.iteritems():
79 edge = (value,) + tuple(sorted([from_node, to_node]))
80 edges.add(edge)
81 edges = list(edges)
82 heapq.heapify(edges)
83 while edges and graphs > 1:
84 # more edges to go and we haven't gotten a spanning tree yet.
85 edge = heapq.heappop(edges)
86 g1 = forest[edge[1]]
87 g2 = forest[edge[2]]
88 if g1 is g2:
89 continue # already joined
90 # combine g1 and g2 into g1
91 graphs -= 1
92 for from_node, to_nodes in g2.iteritems():
93 #remember its symmetric, don't need to do 'to'.
94 forest[from_node] = g1
95 g1.setdefault(from_node, {}).update(to_nodes)
96 # add edge
97 g1[edge[1]][edge[2]] = edge[0]
98 g1[edge[2]][edge[1]] = edge[0]
99 # union the remaining graphs
100 _, result = forest.popitem()
101 for _, g2 in forest.iteritems():
102 if g2 is result: # common case
103 continue
104 for from_node, to_nodes in g2.iteritems():
105 result.setdefault(from_node, {}).update(to_nodes)
106 return result
107
108
109def _resource_graph(resource_sets):
110 """Convert an iterable of resource_sets into a graph.
111
112 Each resource_set in the iterable is treated as a node, and each resource
113 in that resource_set is used as an edge to other nodes.
114 """
115 nodes = {}
116 edges = {}
117 for resource_set in resource_sets:
118 # put node in nodes
119 node = frozenset(resource_set)
120 nodes[node] = set()
121 # put its contents in as edges
122 for resource in resource_set:
123 edges.setdefault(resource, []).append(node)
124 # populate the adjacent members of nodes
125 for node, connected in nodes.iteritems():
126 for resource in node:
127 connected.update(edges[resource])
128 connected.discard(node)
129 return nodes
130
131
31def split_by_resources(tests):132def split_by_resources(tests):
32 """Split a list of tests by the resources that the tests use.133 """Split a list of tests by the resources that the tests use.
33134
@@ -47,6 +148,30 @@
47 return resource_set_tests148 return resource_set_tests
48149
49150
151def _strongly_connected_components(graph, no_resources):
152 """Find the strongly connected components in graph.
153
154 This is essentially a nonrecursive flatterning of Tarjan's method. It
155 may be worth profiling against an actual Tarjan's implementation at some
156 point, but sets are often faster than python calls.
157
158 graph gets consumed, but that could be changed easily enough.
159 """
160 partitions = []
161 while graph:
162 node, pending = graph.popitem()
163 current_partition = set([node])
164 while pending:
165 # add all the nodes connected to a connected node to pending.
166 node = pending.pop()
167 current_partition.add(node)
168 pending.update(graph.pop(node, []))
169 # don't try to process things we've allready processed.
170 pending.difference_update(current_partition)
171 partitions.append(current_partition)
172 return partitions
173
174
50class OptimisingTestSuite(unittest.TestSuite):175class OptimisingTestSuite(unittest.TestSuite):
51 """A resource creation optimising TestSuite."""176 """A resource creation optimising TestSuite."""
52177
@@ -126,54 +251,149 @@
126 def sortTests(self):251 def sortTests(self):
127 """Attempt to topographically sort the contained tests.252 """Attempt to topographically sort the contained tests.
128253
254 This function biases to reusing a resource: it assumes that resetting
255 a resource is usually cheaper than a teardown + setup; and that most
256 resources are not dirtied by most tests.
257
129 Feel free to override to improve the sort behaviour.258 Feel free to override to improve the sort behaviour.
130 """259 """
131 # We group the tests by the resource combinations they use,260 # We group the tests by the resource combinations they use,
132 # since there will usually be fewer resource combinations than261 # since there will usually be fewer resource combinations than
133 # actual tests and there can never be more.262 # actual tests and there can never be more: This gives us 'nodes' or
263 # 'resource_sets' that represent many tests using the same set of
264 # resources.
134 resource_set_tests = split_by_resources(self._tests)265 resource_set_tests = split_by_resources(self._tests)
135266 # Partition into separate sets of resources, there is no ordering
136 graph = self._getGraph(resource_set_tests.keys())267 # preference between sets that do not share members. Rationale:
268 # If resource_set A and B have no common resources, AB and BA are
269 # equally good - the global setup/teardown sums are identical. Secondly
270 # if A shares one or more resources with C, then pairing AC|CA is better
271 # than having B between A and C, because the shared resources can be
272 # reset or reused. Having partitioned we can use connected graph logic
273 # on each partition.
274 resource_set_graph = _resource_graph(resource_set_tests)
137 no_resources = frozenset()275 no_resources = frozenset()
138 # Recursive visit-all-nodes all-permutations.276 # A list of resource_set_tests, all fully internally connected.
139 def cost(from_set, resource_sets):277 partitions = _strongly_connected_components(resource_set_graph,
140 """Get the cost of resource traversal for resource sets.278 no_resources)
141279 result = []
142 :return: cost, order280 for partition in partitions:
143 """281 # we process these at the end for no particularly good reason (it makes
144 if not resource_sets:282 # testing slightly easier).
145 # tear down last resources283 if partition == [no_resources]:
146 return graph[from_set][no_resources], []284 continue
147 costs = []285 order = self._makeOrder(partition)
148 for to_set in resource_sets:286 # Spit this partition out into result
149 child_cost, child_order = cost(287 for resource_set in order:
150 to_set, resource_sets - set([to_set]))288 result.extend(resource_set_tests[resource_set])
151 costs.append((graph[from_set][to_set] + child_cost,289 result.extend(resource_set_tests[no_resources])
152 [to_set] + child_order))290 self._tests = result
153 return min(costs)
154 _, order = cost(no_resources,
155 set(resource_set_tests) - set([no_resources]))
156 order.append(no_resources)
157 self._tests = sum(
158 (resource_set_tests[resource_set] for resource_set in order), [])
159291
160 def _getGraph(self, resource_sets):292 def _getGraph(self, resource_sets):
161 """Build a graph of the resource-using nodes.293 """Build a graph of the resource-using nodes.
162294
295 This special cases set(['root']) to be a node with no resources and
296 edges to everything.
297
163 :return: A complete directed graph of the switching costs298 :return: A complete directed graph of the switching costs
164 between each resource combination.299 between each resource combination. Note that links from N to N are
300 not included.
165 """301 """
302 no_resources = frozenset()
166 graph = {}303 graph = {}
304 root = set(['root'])
305 # bottom = set(['bottom'])
167 for from_set in resource_sets:306 for from_set in resource_sets:
168 graph[from_set] = {}307 graph[from_set] = {}
308 if from_set == root:
309 from_resources = no_resources
310 #elif from_set == bottom:
311 # continue # no links from bottom
312 else:
313 from_resources = from_set
169 for to_set in resource_sets:314 for to_set in resource_sets:
170 if from_set is to_set:315 if from_set is to_set:
171 graph[from_set][to_set] = 0316 continue # no self-edges
317 #if to_set == bottom:
318 # if from_set == root:
319 # continue # no short cuts!
320 # to_resources = no_resources
321 #el
322 if to_set == root:
323 continue # no links to root
172 else:324 else:
173 graph[from_set][to_set] = self.cost_of_switching(325 to_resources = to_set
174 from_set, to_set)326 graph[from_set][to_set] = self.cost_of_switching(
327 from_resources, to_resources)
175 return graph328 return graph
176329
330 def _makeOrder(self, partition):
331 """Return a order for the resource sets in partition."""
332 # This problem is NP-C - find the lowest cost hamiltonian path. It
333 # also meets the triangle inequality, so we can use an approximation.
334 # TODO: implement Christofides.
335 # See http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP
336 # We need a root
337 root = frozenset(['root'])
338 partition.add(root)
339 # and an end
340 # partition.add(frozenset(['bottom']))
341 # get rid of 'noresources'
342 partition.discard(frozenset())
343 digraph = self._getGraph(partition)
344 # build a prime map
345 primes = {}
346 prime = frozenset(['prime'])
347 for node in digraph:
348 primes[node] = node.union(prime)
349 graph = _digraph_to_graph(digraph, primes)
350 mst = _kruskals_graph_MST(graph)
351 # Because the representation is a digraph, we can build an Eulerian
352 # cycle directly from the representation by just following the links:
353 # a node with only 1 'edge' has two directed edges; and we can only
354 # enter and leave it once, so the edge lookups will match precisely.
355 # As the mst is a spanning tree, the graph will become disconnected
356 # (we choose non-disconnecting edges first)
357 # - for a stub node (1 outgoing link): when exiting it unless it is
358 # the first node started at
359 # - for a non-stub node if choosing an outgoing link where some other
360 # endpoints incoming link has not been traversed. [exit by a
361 # different node than entering, until all exits taken].
362 # We don't need the mst after, so it gets modified in place.
363 node = root
364 cycle = [node]
365 steps = 2 * (len(mst) - 1)
366 for step in xrange(steps):
367 found = False
368 outgoing = None # For clearer debugging.
369 for outgoing in mst[node]:
370 if node in mst[outgoing]:
371 # we have a return path: take it
372 # print node, '->', outgoing, ' can return'
373 del mst[node][outgoing]
374 node = outgoing
375 cycle.append(node)
376 found = True
377 break
378 if not found:
379 # none of the outgoing links have an incoming, so follow an
380 # arbitrary one (the last examined outgoing)
381 # print node, '->', outgoing
382 del mst[node][outgoing]
383 node = outgoing
384 cycle.append(node)
385 # Convert to a path:
386 visited = set()
387 order = []
388 for node in cycle:
389 if node in visited:
390 continue
391 if node in primes:
392 order.append(node)
393 visited.add(node)
394 assert order[0] == root
395 return order[1:]
396
177397
178class TestLoader(unittest.TestLoader):398class TestLoader(unittest.TestLoader):
179 """Custom TestLoader to set the right TestSuite class."""399 """Custom TestLoader to set the right TestSuite class."""
180400
=== modified file 'lib/testresources/tests/__init__.py'
--- lib/testresources/tests/__init__.py 2009-07-13 08:22:13 +0000
+++ lib/testresources/tests/__init__.py 2010-02-19 05:54:16 +0000
@@ -28,10 +28,12 @@
28 import testresources.tests.test_resourced_test_case28 import testresources.tests.test_resourced_test_case
29 import testresources.tests.test_test_loader29 import testresources.tests.test_test_loader
30 import testresources.tests.test_test_resource30 import testresources.tests.test_test_resource
31 import testresources.tests.test_resource_graph
31 result = TestUtil.TestSuite()32 result = TestUtil.TestSuite()
32 result.addTest(testresources.tests.test_test_loader.test_suite())33 result.addTest(testresources.tests.test_test_loader.test_suite())
33 result.addTest(testresources.tests.test_test_resource.test_suite())34 result.addTest(testresources.tests.test_test_resource.test_suite())
34 result.addTest(testresources.tests.test_resourced_test_case.test_suite())35 result.addTest(testresources.tests.test_resourced_test_case.test_suite())
36 result.addTest(testresources.tests.test_resource_graph.test_suite())
35 result.addTest(37 result.addTest(
36 testresources.tests.test_optimising_test_suite.test_suite())38 testresources.tests.test_optimising_test_suite.test_suite())
37 return result39 return result
3840
=== modified file 'lib/testresources/tests/test_optimising_test_suite.py'
--- lib/testresources/tests/test_optimising_test_suite.py 2010-01-05 05:51:14 +0000
+++ lib/testresources/tests/test_optimising_test_suite.py 2010-02-19 05:54:16 +0000
@@ -403,7 +403,7 @@
403 resource = self.makeResource()403 resource = self.makeResource()
404 suite = testresources.OptimisingTestSuite()404 suite = testresources.OptimisingTestSuite()
405 graph = suite._getGraph([frozenset()])405 graph = suite._getGraph([frozenset()])
406 self.assertEqual({frozenset(): {frozenset(): 0}}, graph)406 self.assertEqual({frozenset(): {}}, graph)
407407
408 def testTwoCasesInGraph(self):408 def testTwoCasesInGraph(self):
409 res1 = self.makeResource()409 res1 = self.makeResource()
@@ -415,9 +415,9 @@
415415
416 suite = testresources.OptimisingTestSuite()416 suite = testresources.OptimisingTestSuite()
417 graph = suite._getGraph([no_resources, set1, set2])417 graph = suite._getGraph([no_resources, set1, set2])
418 self.assertEqual({no_resources: {no_resources: 0, set1: 2, set2: 1},418 self.assertEqual({no_resources: {set1: 2, set2: 1},
419 set1: {no_resources: 2, set1: 0, set2: 1},419 set1: {no_resources: 2, set2: 1},
420 set2: {no_resources: 1, set1: 1, set2: 0}}, graph)420 set2: {no_resources: 1, set1: 1 }}, graph)
421421
422422
423class TestGraphStuff(testtools.TestCase):423class TestGraphStuff(testtools.TestCase):
@@ -489,10 +489,15 @@
489 return permutations489 return permutations
490490
491 def testBasicSortTests(self):491 def testBasicSortTests(self):
492 # Test every permutation of inputs, with equal cost resources and492 # Test every permutation of inputs, with legacy tests.
493 # legacy tests.493 # Cannot use equal costs because of the use of
494 # a 2*optimal heuristic for sorting: with equal
495 # costs the wrong sort order is < twice the optimal
496 # weight, and thus can be selected.
494 resource_one = testresources.TestResource()497 resource_one = testresources.TestResource()
495 resource_two = testresources.TestResource()498 resource_two = testresources.TestResource()
499 resource_two.setUpCost = 5
500 resource_two.tearDownCost = 5
496 resource_three = testresources.TestResource()501 resource_three = testresources.TestResource()
497502
498 self.case1.resources = [503 self.case1.resources = [
@@ -584,6 +589,43 @@
584 permutation.index(self.case3) < permutation.index(self.case4),589 permutation.index(self.case3) < permutation.index(self.case4),
585 sorted.index(self.case3) < sorted.index(self.case4))590 sorted.index(self.case3) < sorted.index(self.case4))
586591
592 def testSortingTwelveIndependentIsFast(self):
593 # Given twelve independent resource sets, my patience is not exhausted.
594 managers = []
595 for pos in range(12):
596 managers.append(testresources.TestResourceManager())
597 # Add more sample tests
598 cases = [self.case1, self.case2, self.case3, self.case4]
599 for pos in range(5,13):
600 cases.append(
601 testtools.clone_test_with_new_id(cases[0], 'case%d' % pos))
602 # We care that this is fast in this test, so we don't need to have
603 # overlapping resource usage
604 for case, manager in zip(cases, managers):
605 case.resources = [('_resource', manager)]
606 # Any sort is ok, as long as its the right length :)
607 result = self.sortTests(cases)
608 self.assertEqual(12, len(result))
609
610 def testSortingTwelveOverlappingIsFast(self):
611 # Given twelve connected resource sets, my patience is not exhausted.
612 managers = []
613 for pos in range(12):
614 managers.append(testresources.TestResourceManager())
615 # Add more sample tests
616 cases = [self.case1, self.case2, self.case3, self.case4]
617 for pos in range(5,13):
618 cases.append(
619 testtools.clone_test_with_new_id(cases[0], 'case%d' % pos))
620 tempdir = testresources.TestResourceManager()
621 # give all tests a tempdir, enough to provoke a single partition in
622 # the current code.
623 for case, manager in zip(cases, managers):
624 case.resources = [('_resource', manager), ('tempdir', tempdir)]
625 # Any sort is ok, as long as its the right length :)
626 result = self.sortTests(cases)
627 self.assertEqual(12, len(result))
628
587 def testSortConsidersDependencies(self):629 def testSortConsidersDependencies(self):
588 """Tests with different dependencies are sorted together."""630 """Tests with different dependencies are sorted together."""
589 # We test this by having two resources (one and two) that share a very631 # We test this by having two resources (one and two) that share a very
590632
=== added file 'lib/testresources/tests/test_resource_graph.py'
--- lib/testresources/tests/test_resource_graph.py 1970-01-01 00:00:00 +0000
+++ lib/testresources/tests/test_resource_graph.py 2010-02-19 05:54:16 +0000
@@ -0,0 +1,141 @@
1#
2# testresources: extensions to python unittest to allow declaritive use
3# of resources by test cases.
4# Copyright (C) 2010 Robert Collins <robertc@robertcollins.net>
5#
6# This program is free software; you can redistribute it and/or modify
7# it under the terms of the GNU General Public License as published by
8# the Free Software Foundation; either version 2 of the License, or
9# (at your option) any later version.
10#
11# This program is distributed in the hope that it will be useful,
12# but WITHOUT ANY WARRANTY; without even the implied warranty of
13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14# GNU General Public License for more details.
15#
16# You should have received a copy of the GNU General Public License
17# along with this program; if not, write to the Free Software
18# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19#
20
21"""Test _resource_graph(resource_sets)."""
22
23import testtools
24import testresources
25from testresources import split_by_resources, _resource_graph
26from testresources.tests import ResultWithResourceExtensions
27import unittest
28
29
30def test_suite():
31 from testresources.tests import TestUtil
32 loader = TestUtil.TestLoader()
33 result = loader.loadTestsFromName(__name__)
34 return result
35
36
37class TestResourceGraph(testtools.TestCase):
38
39 def test_empty(self):
40 no_resources = frozenset()
41 resource_sets = [no_resources]
42 self.assertEqual({no_resources:set([])}, _resource_graph(resource_sets))
43
44 def test_discrete(self):
45 resset1 = frozenset([testresources.TestResourceManager()])
46 resset2 = frozenset([testresources.TestResourceManager()])
47 resource_sets = [resset1, resset2]
48 result = _resource_graph(resource_sets)
49 self.assertEqual({resset1:set([]), resset2:set([])}, result)
50
51 def test_overlapping(self):
52 res1 = testresources.TestResourceManager()
53 res2 = testresources.TestResourceManager()
54 resset1 = frozenset([res1])
55 resset2 = frozenset([res2])
56 resset3 = frozenset([res1, res2])
57 resource_sets = [resset1, resset2, resset3]
58 result = _resource_graph(resource_sets)
59 self.assertEqual(
60 {resset1:set([resset3]),
61 resset2:set([resset3]),
62 resset3:set([resset1, resset2])},
63 result)
64
65
66class TestDigraphToGraph(testtools.TestCase):
67
68 def test_wikipedia_example(self):
69 """Converting a digraph mirrors it in the XZ axis (matrix view).
70
71 See http://en.wikipedia.org/wiki/Travelling_salesman_problem \
72 #Solving_by_conversion_to_Symmetric_TSP
73 """
74 # A B C
75 # A 1 2
76 # B 6 3
77 # C 5 4
78 A = "A"
79 Ap = "A'"
80 B = "B"
81 Bp = "B'"
82 C = "C"
83 Cp = "C'"
84 digraph = {A:{ B:1, C:2},
85 B:{A:6, C:3},
86 C:{A:5, B:4 }}
87 # and the output
88 # A B C A' B' C'
89 # A 0 6 5
90 # B 1 0 4
91 # C 2 3 0
92 # A' 0 1 2
93 # B' 6 0 3
94 # C' 5 4 0
95 expected = {
96 A :{ Ap:0, Bp:6, Cp:5},
97 B :{ Ap:1, Bp:0, Cp:4},
98 C :{ Ap:2, Bp:3, Cp:0},
99 Ap:{A:0, B:1, C:2 },
100 Bp:{A:6, B:0, C:3 },
101 Cp:{A:5, B:4, C:0 }}
102 self.assertEqual(expected,
103 testresources._digraph_to_graph(digraph, {A:Ap, B:Bp, C:Cp}))
104
105
106class TestKruskalsMST(testtools.TestCase):
107
108 def test_wikipedia_example(self):
109 """Performing KruskalsMST on a graph returns a spanning tree.
110
111 See http://en.wikipedia.org/wiki/Kruskal%27s_algorithm.
112 """
113 A = "A"
114 B = "B"
115 C = "C"
116 D = "D"
117 E = "E"
118 F = "F"
119 G = "G"
120 graph = {
121 A:{ B:7, D:5},
122 B:{A:7, C:8, D:9, E:7},
123 C:{ B:8, E:5},
124 D:{A:5, B:9, E:15, F:6},
125 E:{ B:7, C:5, D:15, F:8, G:9},
126 F:{ D:6, E:8, G:11},
127 G:{ E:9, F:11}}
128 expected = {
129 A:{ B:7, D:5},
130 B:{A:7, E:7},
131 C:{ E:5},
132 D:{A:5, F:6},
133 E:{ B:7, C:5, G:9},
134 F:{ D:6},
135 G:{ E:9}}
136 result = testresources._kruskals_graph_MST(graph)
137 e_weight = sum(sum(row.itervalues()) for row in expected.itervalues())
138 r_weight = sum(sum(row.itervalues()) for row in result.itervalues())
139 self.assertEqual(e_weight, r_weight)
140 self.assertEqual(expected,
141 testresources._kruskals_graph_MST(graph))

Subscribers

People subscribed via source and target branches