please code parts : Part B - partb.py from a2d import Graph # add imports for
Question:
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
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill