please show that the solution has the same output as the one
provided below. Code Format is also provided. Thank you!
Improving the
MST Implementation
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 1 (67.87 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 2 (31.98 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 3 (10.47 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 4 (10.06 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 5 (28.68 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 6 (24.59 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 7 (29.25 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 8 (32.47 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 9 (34.51 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 10 (31.93 KiB) Viewed 38 times
- Python Programming Please Show That The Solution Has The Same Output As The One Provided Below Code Format Is Also Prov 11 (12.49 KiB) Viewed 38 times
from typing import List
class MinHeap:
def __init__(self) -> None:
self.size = 0
self.keys = [None] # other elements start at index 1
self.values = [None]
def __str__(self) -> str:
return f"keys: {self.keys}, values: {self.values}"
def add(self, item: int, value: int) -> None:
self.keys.append(item)
self.values.append(value)
self.size += 1
idx = self.size
parent_idx = idx//2
while (idx > 1) and (self.values[parent_idx] > value):
self._swap_nodes(parent_idx, idx)
idx = parent_idx
parent_idx = idx//2
def _swap_nodes(self, idx1: int, idx2: int):
# Swap keys
self.keys[idx1], self.keys[idx2] = self.keys[idx2],
self.keys[idx1]
# Swap values
self.values[idx1], self.values[idx2] = self.values[idx2],
self.values[idx1]
def get_smallest(self) -> int:
"""Return the key of the Node with smallest value"""
return self.keys[1]
def remove_smallest(self) -> int:
"""Remove and return the key of Node with smallest value"""
key_of_min = self.keys[1]
end_key = self.keys.pop()
end_value = self.values.pop()
self.size -= 1
if self.size:
self.keys[1] = end_key
self.values[1] = end_value
# Reorder the heap to fix order
self._reorder_heap_from_root()
return key_of_min
def _reorder_heap_from_root(self):
parent_idx = 1
while True:
right_idx = parent_idx*2 + 1
left_idx = parent_idx*2
# Get index with minimum value among parent and children
min_idx = parent_idx
if left_idx <= self.size:
if self.values[left_idx] < self.values[min_idx]:
min_idx = left_idx
if right_idx <= self.size:
if self.values[right_idx] < self.values[min_idx]:
min_idx = right_idx
# If parent already minimum value, heap already ok.
# Otherwise, swap and continue
if min_idx == parent_idx:
break
self._swap_nodes(min_idx, parent_idx)
parent_idx = min_idx
class WeightedQuickUnion:
def __init__(self, size: int) -> None:
"""
Initializes the union-find ds
size: number of elements to initialize
"""
self.size = size
self.parent = [-1]*self.size # create a list where all elements are
roots
self.group_size = [1]*self.size # create separate list to indicate
the size for each element
# (useful for knowing the size in root's perspective)
def __str__(self) -> str:
return f"parent: {self.parent}\nsize: {self.group_size}\n"
def get_root(self, p: int) -> int:
"""Find the root of p"""
idx = p
while self.parent[idx] >= 0: # root should have a negative
value
idx = self.parent[idx]
return idx
def is_connected(self, p1: int, p2:int) -> bool:
return self.get_root(p1) == self.get_root(p2)
def connect(self, p1: int, p2: int) -> None:
"""Connects p1 and p2"""
r1 = self.get_root(p1)
r2 = self.get_root(p2)
r1_size = self.group_size[r1]
r2_size = self.group_size[r2]
if r1_size > r2_size:
self.parent[r2] = r1
self.group_size[r1] += r2_size # increase r1 group size by r2
size
else:
self.parent[r1] = r2
self.group_size[r2] += r1_size # increase r2 group size by r1
size
class GraphUndirected:
def __init__(self, num_vertices: int) -> None:
self.num_vertices = num_vertices
self.num_edges = 0
self.adj_list = []
for _ in range(num_vertices):
self.adj_list.append({})
def __str__(self) -> str:
return f"adj: {self.adj_list}"
def add_edge(self, v: int, w: int, weight: int) ->
None:
self.adj_list[v][w] = weight
self.adj_list[w][v] = weight
self.num_edges += 1
def adj(self, v: int) -> List[int]:
return self.adj_list[v] # returns vertices adjacent to v
def has_edge(self, v: int, w: int) -> bool:
if w in self.adj_list[v]:
return True
return False
class PrimMST:
def __init__(self, graph: GraphUndirected, init_v: int = 0) ->
None:
self.graph = graph
self.source = init_v
self.dist_to = [float("inf")] * graph.num_vertices
self.dist_to[init_v] = 0
self.edge_to = [None] * graph.num_vertices
self.is_marked = [False] * graph.num_vertices
self.mst = []
self.prim(self.graph)
def get_mst(self) -> List[set]:
return self.mst
def prim(self, graph: GraphUndirected):
pq = MinHeap()
pq.add(self.source, 0) # Set distance to source as 0
# Set distance to other vertices to be inf in PQ
for v in range(graph.num_vertices):
if v != self.source:
pq.add(v, float("inf"))
p1 = pq.remove_smallest()
self.scan(graph, pq, p1)
while pq.size > 0:
p1 = pq.remove_smallest()
if self.is_marked[p1]:
continue
self.scan(graph, pq, p1)
def scan(self, graph: GraphUndirected, pq: MinHeap,point:
int):
self.is_marked[point] = True
for neighbor, weight in graph.adj(point).items():
if self.is_marked[neighbor]:
continue
if self.dist_to[neighbor] > weight:
self.dist_to[neighbor] = weight
self.edge_to[neighbor] = point
pq.add(neighbor, weight)
class KruskalMST:
def __init__(self, graph: GraphUndirected) -> None:
self.graph = graph
self.edge_to = [None]*graph.num_vertices
self.mst = []
self.kruskal(self.graph)
def get_mst(self) -> List[set]:
return self.mst
def kruskal(self, graph: GraphUndirected):
uf = WeightedQuickUnion(graph.num_vertices)
pq = MinHeap()
# Create MinHeap containing all edges and their weights
for pt in range(graph.num_vertices):
for neighbor, weight in graph.adj(pt).items():
edge = {pt, neighbor}
if edge not in pq.keys:
pq.add(edge, weight)
while (pq.size > 0):
p1, p2 = pq.remove_smallest()
if not uf.is_connected(p1, p2):
uf.connect(p1,p2)
self.edge_to[p2] = p1
if __name__=="__main__":
# Initialize the graph with a given number of vertices
num_vert = int(input())
g = GraphUndirected(num_vertices=num_vert)
# Add edges to the graph
num_edges = int(input())
for x in range(num_edges):
input_line = input().split(',')
g.add_edge(
v=int(input_line[0]),
w=int(input_line[1]),
weight=int(input_line[2])
)
# Get the MST using both Prim's and Kruskal's algorithm
prim = PrimMST(g)
print(prim.get_mst())
kruskal = KruskalMST(g)
print(kruskal.get_mst())
Modify the given code implementation for the Min Heap such that: • Instead of having separate lists for keys and values (i.e., keys and values), you will instead have a single list called heap. This heap variable should contain Node class objects. Each Node object should contain a key and a value as its attribute. Original Expected modification def class MinHeap: def __init__(self) -> None: self.size = 0 self.keys = [None] self.values = [None] class MinHeap: _init__(self) -> None: self.size = 0 self.heap = [None] • Modify all the necessary methods and lines of code given that you will only have a list of Node objects • You can also choose to add/remove methods as you see fit Hint: make sure to define the __repr__ method for Node class to make it easier to debug Modify the implementation of Prim's and Kruskal's algorithms such that: • Both classes (PrimMST and KruskalMST) would each have an mst attribute (i.e., a variable mst) that stores a list of sets, where each set represents an edge of the Minimum Spanning Tree. • Optional but highly recommended: Change the condition for Kruskal's algorithm to be when the number of edges in the mst is equal to the number of nodes - 1) instead of when the PQ is empty
Input Format • The first line contains the number N which is the number of vertices. Graph will then have nodes/vertices from o to N-1 • The second line contains the number E which is the number of edges • Each of the next E lines contains 3 numbers separated by commas: V,w,weight. This means there is an undirected edge connecting v and w with weight=weight Constraints •v and w are not equal • N, E >0 • weight > 0 v and w are guaranteed to be valid nodes/vertices Output Format • First line of the output should be the edges of the MST from Prim's algorithm • Second line of the output should be the edges of the MST from Kruskal's algorithm Both outputs should be a list of sets, where each set is an edge of the MST. For example, the MST contains edges 1-2 and 2-3. The output should then be [{1,2}, {2,3}]. Note that the checker is order agnostic (i.e., it doesn't matter what order you output the edges; it will check the presence/absence of edges)
Sample Input 0 7 12 0,1,2 ,2,1 1,2,5 1,4,3 1,3,11 4,2,1 4,5,4 4,6,3 2,5,15 3,4,2 6,3,1 6,5,1 Sample Output 0 [{0, 2}, {2, 4}, {0, 1}, {3, 4}, {3, 6}, {5, 6}] [{4, 2}, {2, 0}, {3, 6}, {5, 6}, {0, 1}, {3, 4}]
Sample Input 1 7 11 0,1,7 0,3,5 1,3,9 1,2,8 1,4,7 2,4,5 3,4,15 3,5,6 4,5,8 4,6,9 5,6,11 Sample Output 1 [{0, 3}, {3, 5}, {0, 1}, {1, 4}, {2, 4}, {4, 6}] [{0, 3}, {2, 4}, {3, 5}, {0, 1}, {1, 4}, {4, 6}]
from typing import List class MinHeap: def __init__(self) -> None: self.size = 0 self.keys [None] # other elements start at index 1 self.values [None] = def -_str__(self) -> str: return f"keys: {self.keys), values: {self.values}" def add(self, item: int, value: int) -> None: self.keys.append(item) self.values.append(value) self.size += 1 idx = self.size parent_idx = idx//2 while (idx > 1) and (self.values [parent_idx] > value): self._swap_nodes (parent_idx, idx) idx = parent_idx parent_idx = idx//2 def _swap_nodes (self, idxl: int, idx2: int): # Swap keys self.keys[idxl], self.keys [idx2] self.keys[idx2], self.keys[idx1] # Swap values self.values[idxl], self.values[idx2] = self.values[idx2], self.values[idxl] def get_smallest (self) -> int: Return the key of the Node with smallest value" return self.keys[1]
= def remove_smallest (self) -> int: "Remove and return the key of Node with smallest value"! key_of_min = self.keys[1] end_key self.keys.pop() end_value self.values.pop() self.size -= 1 if self.size: self.keys [1] = end_key self.values[1] = end_value # Reorder the heap to fix order self._reorder_heap_from_root() return key_of_min def _reorder_heap_from_root(self): parent_idx = 1 while True: right_idx = parent_idx*2 + 1 left_idx = parent_idx*2 # Get index with minimum value among parent and children min_idx = parent_idx if left_idx <= self.size: if self.values[left_idx] < self.values[min_idx]: min_idx = left_idx if right_idx <= self.size: if self.values[right_idx] < self.values[min_idx]: min_idx = right_idx =
# If parent already minimum value, heap already ok. # Otherwise, swap and continue if min_idx == parent_idx: break self._swap_nodes (min_idx, parent_idx) parent_idx = min_idx class WeightedQuickUnion: def __init__(self, size: int) -> None: Initializes the union-find ds size: number of elements to initialize self.size = size self.parent = (-1]*self.size # create a list where all elements are roots self.group_size [1]*self.size # create separate list to indicate the size for each element # (useful for knowing the size in root's perspective) = def __str__(self) -> str: return f"parent: {self.parent}\nsize: {self.group_size}\n" def get_root(self, p: int) -> int: "Find the root of p" idx = p while self.parent[idx] >= C: idx = self.parent[idx] return idx # root should have a negative value def is_connected(self, pl: int, p2:int) -> bool: return self.get_root(pl) == self.get_root(p2)
def connect(self, pl: int, p2: int) -> None: "Connects pl and p21 rl = self.get_root(pl) r2 = self.get_root(p2) ri_size = self.group_size[rl] r2_size = self.group_size[r2] if ri_size > r2_size: self.parent[r2] = rl self.group_size[rl] += r2_size # increase rl group size by r2 size else: self.parent[rl] = r2 self.group_size[r2] += ri_size # increase r2 group size by ri size class GraphUndirected: def __init__(self, num_vertices: int) -> None: self.num_vertices = num_vertices self.num_edges = 0 self.adj_list = [] for - in range (num_vertices): self.adj_list.append({}) def __str__(self) -> str: return f"adj: {self.adj_list)" def add_edge (self, v: int, w: int, weight: int) -> None: self.adj.list[v] [w] weight self.adj.list[w][v] = weight self.num_edges += 1 = def adj(self, v: int) -> List[int]: return self.adj_list[v] # returns vertices adjacent to v def has_edge (self, v: int, w: int) -> bool: if w in self.adj.list[v]: return True return false
) -> None: class PrimMST: def __init__(self, graph: GraphUndirected, init_v: int self.graph = graph self. source = init_v self.dist to [float("inf")] * graph.num_vertices self.dist_to[init_v] = 0 self.edge_to = [None] * graph.num_vertices self.is_marked [False] graph.num_vertices self.mst = [] self.prim(self.graph) def get_mst (self) -> List[set]: return self.mst def prim(self, graph: GraphUndirected): pq = MinHeap O pq.add(self.source, o) # Set distance to source as o # Set distance to other vertices to be inf in PQ for v in range (graph.num_vertices): if v != self.source: pg.add(v, float("inf")) pl = pq.remove_smallest self.scan(graph, pq, pl) while pq.size > 0: pl = pq.remove_smallest if self.is_marked[pl]: continue self.scan(graph, pg, pl) = def scan(self, graph: GraphUndirected, pq: MinHeap, point: int): self.is_marked [point] = True for neighbor, weight in graph. adj (point).items(): if self.is_marked[neighbor]: continue
if self.dist_to[neighbor] > weight: self.dist_to[neighbor] = weight self.edge_to [neighbor] = point pq.add(neighbor, weight) class KruskalMST: def __init__(self, graph: GraphUndirected) -> None: self.graph = graph self.edge_to - [None] *graph.num_vertices self.mst = [] self.kruskal(self.graph) def get_mst(self) -> List[set]: return self.mst def kruskal(self, graph: GraphUndirected): uf - WeightedQuickUnion (graph.num_vertices) pq = MinHeap # Create Minheap containing all edges and their weights for pt in range (graph.num_vertices): for neighbor, weight in graph.adj (pt). items(): edge = {pt, neighbor} if edge not in pq.keys: pq.add(edge, weight) while (pg.size > 0): pl, p2 = pq.remove_smallest() if not uf.is_connected (pl, p2): uf.connect(pl,p2) self.edge_to[22] = pl if __name__ =="__main__": # Initialize the graph with a given number of vertices num_vert = int(input) g = GraphUndirected(num_vertices=num_vert)
# Add edges to the graph num_edges = int(input) for x in range(num_edges) : input_line = input().split(',') g.add_edge v=int(input_line[o]), w=int(input_line[1]), weight=int(input_line[2]) ) # Get the MST using both Prim's and Kruskal's algorithm prim PrimMST (9) print(prim.get_msto) kruskal = KruskalMST(S) print (kruskal.get_msto)