please code parts :

 

Part B -  partb.py

from a2d import Graph
# add imports for your DisjointSet or MinHeap as you see fit

def minimum_spanning_tree(graph):
    pass

Part C-  partc.py

import random
from a2d import Graph
from a3_partb import minimum_spanning_tree

def generate_maze(number_of_rows, number_of_columns):
    pass

Given Code -

 

PART A -  parta.py

class MinHeap:
    def __init__(self, arr=[]):
        self.heap_arr = []
        for val in arr:
            self.insert(val)


    def insert(self, element):
        self.heap_arr.append(element)
        self._go_up(len(self.heap_arr) - 1)


    def _go_up(self, ind):
        parent_ind = (ind - 1) // 2
        if parent_ind < 0:
            return
        if self.heap_arr[parent_ind] > self.heap_arr[ind]:
            self.heap_arr[parent_ind], self.heap_arr[ind] = self.heap_arr[ind], self.heap_arr[parent_ind]
            self._go_up(parent_ind)


    def get_min(self):
        if self.is_empty():
            return None
        return self.heap_arr[0]


    def extract_min(self):
        if self.is_empty():
            return None
        min_element = self.heap_arr[0]
        last_element = self.heap_arr.pop()
        if len(self.heap_arr) > 0:
            self.heap_arr[0] = last_element
            self._go_down(0)
        return min_element


    def _go_down(self, index):
        left_index = 2 * index + 1
        right_index = 2 * index + 2
        smallest_index = index
        if left_index < len(self.heap_arr) and self.heap_arr[left_index] < self.heap_arr[smallest_index]:
            smallest_index = left_index
        if right_index < len(self.heap_arr) and self.heap_arr[right_index] < self.heap_arr[smallest_index]:
            smallest_index = right_index
        if smallest_index != index:
            self.heap_arr[index], self.heap_arr[smallest_index] = self.heap_arr[smallest_index], self.heap_arr[index]
            self._go_down(smallest_index)


    def is_empty(self):
        return len(self.heap_arr) == 0


    def __len__(self):
        return len(self.heap_arr)

 

Maze.py

# do not modify this file.  This is almost the same maze object as A1.  Only difference is
# that it loads the maze from a file with different data format and has a function
# to print a maze (as represented by a list of walls)


import json


class Maze:
    def __init__(self,filename):
        file = open(filename, "r")
        lines = file.readlines()
        mazeobject = json.loads(lines[0])
        file.close()
       
        self.num_rows = mazeobject['maxRow']
        self.num_cols = mazeobject['maxCol']
        self.num_cells = self.num_rows * self.num_cols
        self.cells = [False for i in range(self.num_cells)]
        self.walls = [[False for j in range(self.num_cells)] for i in range(self.num_cells)]
        for the_cells in mazeobject["walls"]:
            self.walls[the_cells[0]][the_cells[1]] = True
            self.walls[the_cells[1]][the_cells[0]] = True
       


    # returns total number of rows in the maze
    def get_num_rows(self):
        return self.num_rows


    # returns total number of columns in the maze
    def get_num_cols(self):
        return self.num_cols


    # returns the cell_number given row and col
    def get_cell(self, row, col):
        return row * self.num_cols + col


    # returns the row given cell_number
    def get_row(self, cell_number):
        return cell_number//self.num_cols


    # returns the col given cell_number
    def get_col(self, cell_number):
        return cell_number % self.num_cols


    # returns the cell_number of the cell to the left of the cell_number
    # if there is no cell on the left or there is a wall between current cell
    # and left cell, function returns -1
    def get_left(self, cell_number):
        col = self.get_col(cell_number)
        row = self.get_row(cell_number)
        if col == 0:
            return -1
        else:
            left_cell = self.get_cell(row,col-1)
            if not self.walls[left_cell][cell_number]:
                return left_cell
            return -1



    # returns the cell_number of the cell to the right of the cell_number
    # if there is no cell on the right or there is a wall between current cell
    # and right cell, function returns -1
    def get_right(self, cell_number):
        col = self.get_col(cell_number)
        row = self.get_row(cell_number)
        if col == self.num_cols-1:
            return -1
        else:
            right_cell = self.get_cell(row,col+1)
            if not self.walls[right_cell][cell_number]:
                return right_cell
            return -1


    # returns the cell_number of the cell to the up of the cell_number
    # if there is no cell on the up or there is a wall between current cell
    # and up cell, function returns -1
    def get_up(self, cell_number):
        col = self.get_col(cell_number)
        row = self.get_row(cell_number)
        if row == 0:
            return -1
        else:
            up_cell = self.get_cell(row-1,col)
            if not self.walls[up_cell][cell_number]:
                return up_cell
            return -1



    # returns the cell_number of the cell to the down of the cell_number
    # if there is no cell on the down or there is a wall between current cell
    # and down cell, function returns -1
    def get_down(self, cell_number):
        col = self.get_col(cell_number)
        row = self.get_row(cell_number)
        if row == self.num_rows-1:
            return -1
        else:
            down_cell = self.get_cell(row+1,col)
            if not self.walls[down_cell][cell_number]:
                return down_cell
            return -1


    # marks the cell with cell_number, this will allow you to leave a mark on
    # the cells that are part of your path (or being considered to be on your path)
    def mark_cell(self, cell_number):
        self.cells[cell_number]=True


    # ummarks the cell
    def unmark_cell(self, cell_number):
        self.cells[cell_number]=False


    # returns true of cell_number is marked, false otherwise
    def get_is_marked(self,cell_number):
        return self.cells[cell_number]



def print_pathfile(filename, result, row, col):


    the_file = open(filename,"w")
    the_file.write(f'{{"rows": {row}, "cols": {col},')
    the_file.write(f' "pathLength": {len(result)},')
    the_file.write(f'"path":{result}')
    the_file.write("}")
    the_file.close()


def print_mazefile(filename, walls, row, col,start,end):


    for i in range(len(walls)):
        walls[i] = list(walls[i])


    the_file = open(filename,"w")
    the_file.write(f'{{"maxRow": {row}, "maxCol": {col},')
    the_file.write(f'"walls":{walls},')
    the_file.write(f'"start":{start},')
    the_file.write(f'"end":{end}')
    the_file.write("}")
    the_file.close()

RUNNING TEST FOR PART B AND PART C :

 

PART B TEST :

import unittest
from a2d import Graph
from a3_partb import minimum_spanning_tree




class MSTTestCase(unittest.TestCase):
    # These are the test cases for functions of MinHeap class


    def test_minimum_spanning_tree(self):
        the_graph = Graph(7)
        the_graph.add_edge(0,1,2)
        the_graph.add_edge(0,2,3)
        the_graph.add_edge(1,4,4)
        the_graph.add_edge(1,6,5)
        the_graph.add_edge(2,3,1)
        the_graph.add_edge(3,4,2)
        the_graph.add_edge(4,5,4)
        the_graph.add_edge(5,6,1)


        the_graph.add_edge(1,0,2)
        the_graph.add_edge(2,0,3)
        the_graph.add_edge(4,1,4)
        the_graph.add_edge(6,1,5)
        the_graph.add_edge(3,2,1)
        the_graph.add_edge(4,3,2)
        the_graph.add_edge(5,4,4)
        the_graph.add_edge(6,5,1)



        correct = [(2, 3), (5, 6), (0, 1), (3, 4), (0, 2), (4, 5)]


        mst = minimum_spanning_tree(the_graph)


        for i in range(len(mst)):
            if mst[i][0] > mst[i][1]:
                mst[i] = (mst[i][1],mst[i][0])


        correct.sort()
        mst.sort()


        self.assertEqual(correct, mst)



    def test_minimum_spanning_tree2(self):
        the_graph = Graph(11)
        the_graph.add_edge(0,1,6)
        the_graph.add_edge(0,5,8)
        the_graph.add_edge(0,7,7)
        the_graph.add_edge(1,2,3)
        the_graph.add_edge(1,4,2)
        the_graph.add_edge(2,3,4)
        the_graph.add_edge(2,4,1)
        the_graph.add_edge(3,6,9)
        the_graph.add_edge(4,6,5)
        the_graph.add_edge(5,7,4)
        the_graph.add_edge(5,9,8)
        the_graph.add_edge(6,8,3)
        the_graph.add_edge(7,10,5)
        the_graph.add_edge(8,9,1)
        the_graph.add_edge(9,10,3)



        the_graph.add_edge(1,0,6)
        the_graph.add_edge(5,0,8)
        the_graph.add_edge(7,0,7)
        the_graph.add_edge(2,1,3)
        the_graph.add_edge(4,1,2)
        the_graph.add_edge(3,2,4)
        the_graph.add_edge(4,2,1)
        the_graph.add_edge(6,3,9)
        the_graph.add_edge(6,4,5)
        the_graph.add_edge(7,5,4)
        the_graph.add_edge(9,5,8)
        the_graph.add_edge(8,6,3)
        the_graph.add_edge(10,7,5)
        the_graph.add_edge(9,8,1)
        the_graph.add_edge(10,9,3)




        correct = [(2,4),(8,9),(1,4),(9,10),(6,8),(5,7),(2,3),(4,6),(7,10),(0,1)]


        mst = minimum_spanning_tree(the_graph)



        for i in range(len(mst)):
            if mst[i][0] > mst[i][1]:
                mst[i] = (mst[i][1],mst[i][0])


        correct.sort()
        mst.sort()


        self.assertEqual(correct, mst)



if __name__ == '__main__':
    unittest.main()

PART C TEST :

import unittest


from a3_maze import Maze, print_mazefile, print_pathfile
from a1_partd import find_path
from a3_partc import generate_maze



class GenerateMazeTestCase(unittest.TestCase):
    # These are the test cases for functions of MinHeap class


    def test_generate_maze(self):
        maze = generate_maze(3,4)
        self.assertEqual(len(maze),6)



    def test_generate_maze2(self):


        maze = generate_maze(10,10)
        self.assertEqual(len(maze),81)


        print_mazefile("a3_maze1.txt",maze,10,10,11,88)


        the_maze=Maze("a3_maze1.txt")
        result = find_path(the_maze, 11, 88)
        print_pathfile("a3_run1.txt", result, the_maze.get_num_rows(), the_maze.get_num_cols())


    def test_generate_maze3(self):
        maze = generate_maze(80,100)
        self.assertEqual(len(maze),7821)
        print_mazefile("a3_maze2.txt",maze,80,100,99,7900)


        the_maze=Maze("a3_maze2.txt")
        result = find_path(the_maze, 99, 7900)
        print_pathfile("a3_run2.txt", result, the_maze.get_num_rows(), the_maze.get_num_cols())



       




if __name__ == '__main__':
    unittest.main()

a2d.py

class Graph:
   def __init__(self, number_of_verts):
       self.vertCount = number_of_verts
       self.edgeCount = 0
       self.edges = []
       self.verts = []
       for i in range(0, number_of_verts):
           self.verts.append(i)
   def add_vertex(self):
       # add a new vert to vert array. with id of vertCount
       self.verts.append(self.vertCount)
       # increase vert count
       self.vertCount = self.vertCount + 1
   def add_edge(self, from_idx, to_idx, weight=1):
       validFrom = from_idx >= 0 and from_idx < self.vertCount
       validTo = to_idx >= 0 and to_idx < self.vertCount
       doenstHaveEdge = not self.has_edge(from_idx, to_idx)
       returnValue = False
       if validFrom and validTo and doenstHaveEdge:
           self.edges.append([from_idx, to_idx, weight])
           self.edgeCount = self.edgeCount + 1
           returnValue = True
       return returnValue
   def num_edges(self):
       return self.edgeCount
   def num_verts(self):
       return self.vertCount
   def has_edge(self, from_idx, to_idx):
       returnValue = False
       for i in range(0, self.edgeCount):
           # loop through edge array, looking for edge that starts from first, and ends at second.
           currentEdge = self.edges[i]
           if currentEdge[0] == from_idx and currentEdge[1] == to_idx:
               returnValue = True
       return returnValue
   def edge_weight(self, from_idx, to_idx):
       # use has_edge to find if theres an edge there.
       returnValue = None
       for i in range(0, self.edgeCount):
           # loop through edge array, looking for edge that starts from first, and ends at second.
           currentEdge = self.edges[i]
           # yes: return its third value, the weight.
           if currentEdge[0] == from_idx and currentEdge[1] == to_idx:
               returnValue = currentEdge[2]
       return returnValue
   def get_connected(self, v):
       connectedEdges = []
       for i in range(0, self.edgeCount):
           if self.edges[i][0] == v:
               connectedEdges.append((self.edges[i][1], self.edges[i][2]))
       # no idea what this means.
       return connectedEdges
 


Code the MinHeap Class

Code the minimum_spanning_tree function using Prim's or Kruskal's algorithm (your choice)

Code the generate_maze() function