#!/usr/bin/env python3 # -*- coding: utf-8 -*- from collections import deque from src.graph import Graph from src.recompute_mst_data import data from src.testing import AD2TestCase, get_return_type, recursion_variant from typing import * import logging import math import unittest ''' Assignment 2, Problem 2: Recomputing a Minimum Spanning Tree Student Name: ''' ''' Copyright: justin.pearson@it.uu.se and his teaching assistants, 2024. This file is part of course 1DL231 at Uppsala University, Sweden. Permission is hereby granted only to the registered students of that course to use this file, for a homework assignment. The copyright notice and permission notice above shall be included in all copies and extensions of this file, and those are not allowed to appear publicly on the internet, both during a course instance and forever after. ''' # Note: you must give a recursion variant for each recursive function fun by # wrapping fun with the '@recursion_variant(lambda a, b, ..., z): expr)' # wrapper, where the set {a, b, ..., z} is a subset of the arguments to fun and # expr is evaluated to an integer. # If your solution needs a queue, then you can use deque. # If you need to log information during tests, execution, or both, # then you can use this library: # Basic example: # logger = logging.getLogger('put name here') # a = 5 # logger.debug(f'a = {a}') __all__ = ['update_MST_1', 'update_MST_2', 'update_MST_3', 'update_MST_4'] def update_MST_1(G: Graph, T: Graph, e: Tuple[str, str], w: int) -> Union[Tuple[None, None], Tuple[Tuple[str, str], Tuple[str, str]]]: ''' Pre: T is a minimum spanning tree of G. Edge e is in G. Edge e is not in T. The weight of edge e in G is greater than w. Post: Edge e has weight w in G. T is a minimum spanning tree of G. ''' (u, v) = e assert (e in G and e not in T and w > G.weight(u, v)) def update_MST_2(G: Graph, T: Graph, e: Tuple[str, str], w: int) -> Union[Tuple[None, None], Tuple[Tuple[str, str], Tuple[str, str]]]: ''' Pre: T is a minimum spanning tree of G. Edge e is in G. Edge e is not in T. The weight of edge e in G is smaller than w. Post: Edge e has weight w in G. T is a minimum spanning tree of G. ''' (u, v) = e assert (e in G and e not in T and w < G.weight(u, v)) def update_MST_3(G: Graph, T: Graph, e: Tuple[str, str], w: int) -> Union[Tuple[None, None], Tuple[Tuple[str, str], Tuple[str, str]]]: ''' Pre: T is a minimum spanning tree of G. Edge e is in G. Edge e is in T. The weight of edge e in G is smaller than w. Post: Edge e has weight w in G. T is a minimum spanning tree of G. ''' (u, v) = e assert (e in G and e in T and w < G.weight(u, v)) def update_MST_4(G: Graph, T: Graph, e: Tuple[str, str], w: int) -> Union[Tuple[None, None], Tuple[Tuple[str, str], Tuple[str, str]]]: ''' Pre: T is a minimum spanning tree of G. Edge e is in G. Edge e is in T. The weight of edge e in G is greater than w. Post: Edge e has weight w in G. T is a minimum spanning tree of G. ''' (u, v) = e assert (e in G and e in T and w > G.weight(u, v)) class RecomputeMstTest(AD2TestCase): ''' Test Suite for minimum spanning tree problem Any method named 'test_something' will be run when this file is executed. You may add your own test cases if you wish. (You may delete this class from your submitted solution.) ''' logger = logging.getLogger('RecomputeMstTest') data = data update_MST = [update_MST_1, update_MST_2, update_MST_3, update_MST_4] update_MST_ret_type = [get_return_type(f) for f in update_MST] src_code_path = __file__ def source_code_path(self): return RecomputeMstTest.src_code_path def assertReturnedValue(self, unmodified_g: Graph, modified_g: Graph, unmodified_t: Graph, modified_t: Graph, t: Union[Tuple[None, None], Tuple[Tuple[str, str], Tuple[str, str]]]) -> None: e_removed, e_added = t if e_removed is None or e_added is None: return if e_removed == e_added: return self.assertLessEqual(unmodified_g.weight(*e_removed), unmodified_g.weight(*e_added), 'The weight of the added edge cannot be less ' 'than the weight of the removed edge in the' 'unmodified graph.') self.assertGreaterEqual(modified_g.weight(*e_removed), modified_g.weight(*e_added), 'The weight of the added edge cannot be ' 'greater than the weight of the removed edge ' 'in the modified graph.') self.assertIn(e_removed, unmodified_t, 'The removed edge is not in unmodified MST.') self.assertNotIn(e_removed, modified_t, 'The removed edge is in the modified MST.') self.assertNotIn(e_added, unmodified_t, 'The added edge is in the unmodified MST.') self.assertIn(e_added, modified_t, 'The added edge is not in the modified MST.') def assertUndirectedEdgesEqual(self, actual: List[Tuple[str, str]], expected: List[Tuple[str, str]]) -> None: self.assertListEqual( sorted(((min(u, v), max(u, v)) for u, v in actual)), sorted(((min(u, v), max(u, v)) for u, v in expected)), 'The edges in the MST does not match the expected edges.') def assertEdgesInExpectedGraph(self, expected_graph: List[Tuple[str, str]], graph: Graph) -> None: for e in expected_graph: self.assertIn(e, graph, f'The edge {e} is not in the expected graph.') def assertTreeIsConnected(self, tree: Graph) -> None: if len(tree.nodes) == 0: return visited = set() queue = deque([tree.nodes[0]]) while len(queue) > 0: u = queue.popleft() visited.add(u) for v in tree.neighbors(u): if v not in visited: queue.append(v) self.assertSetEqual(visited, set(tree.nodes), 'The tree is not connected.') def assertGraphsEqual(self, actual: Graph, expected: Graph) -> None: self.assertEqual(len(actual.edges), len(expected.edges), 'The graphs have different number of edges.') for u, v in actual.edges: self.assertEqual(actual.weight(u, v), expected.weight(u, v), f'The weight of edge ({u}, {v}) is not equal in ' 'the actual and expected graphs.') def test_mst(self) -> None: is_implemented = [True] * len(self.update_MST) for i, update_MST in enumerate(self.update_MST, start=1): instance = data[0] graph = instance['graph'].copy() tree = instance['mst'].copy() u, v = instance['solutions'][i - 1]['edge'] weight = instance['solutions'][i - 1]['weight'] if update_MST(graph, tree, (u, v), weight) is None: self.logger.warning(f'update_MST_{i} not implemented.') is_implemented[i - 1] = False continue # test update_MST_{i}: for j, instance in enumerate(self.data): # test update_MST_{i} using instance {j}: with self.subTest(case=i, instance=j): graph: Graph = instance['graph'].copy() tree: Graph = instance['mst'].copy() u, v = instance['solutions'][i - 1]['edge'] weight = instance['solutions'][i - 1]['weight'] expected = instance['solutions'][i - 1]['expected'] expected_graph: Graph = instance['graph'].copy() expected_graph.set_weight(u, v, weight) t = self.assertAlgorithm( update_MST, self.update_MST_ret_type[i - 1], graph, tree, (u, v), weight) self.assertReturnedValue(instance['graph'], graph, instance['mst'], tree, t) self.assertUndirectedEdgesEqual(tree.edges, expected) self.assertEdgesInExpectedGraph(tree.edges, expected_graph) self.assertTreeIsConnected(tree) self.assertGraphsEqual(graph, expected_graph) num_implemented_funs = sum((1 if b else 0 for b in is_implemented)) self.assertGreaterEqual( num_implemented_funs, 2, 'At least two of the four update_MST functions must be implemented.') if __name__ == '__main__': # Set logging config to show debug messages: logging.basicConfig(level=logging.DEBUG) # run unit tests (failfast=True stops testing after the first failed test): unittest.main(failfast=True)