from mppy import MPI

import numpy as np

# MPI setup

comm $=$ MPI.COMM$\_$WORLD

rank $=$ comm.Get$\_$rank$()$

n $=$ comm.Get$\_$size$()$

# Message types

IDLE $=0$

COLORED $=1$

TERMINATE $=2$

ROUND $=0$

UPDATE $=1$

ACK $=2$

DISCARD $=3$

ROVER $=4$

TERMINATE $=5$

# Spanning tree of graph

ROOT $=0$

A $=$ np$.$array$([[0,0,0,1,1,0,0,1],$

$[0,0,0,0,0,1,0,1],$

$[0,0,0,1,1,0,1,0],$

$[1,0,1,0,1,0,1,0],$

$[1,0,1,1,0,1,0,1],$

$[0,1,0,0,1,0,0,1],$

$[0,0,1,1,0,0,0,0],$

$[1,1,0,0,1,1,0,0]],$ dtype$=$int$)$

children $=[[3],[],[4],[6],[7],[1],[2],[5]]$

parents $=[0,5,6,0,2,7,3,4]$

# Process state and communication variables

state $=$ IDLE

parent $=$ parents$[$rank$]$

childs $=$ set$($children$[$rank$])$

neighs $=$ indices$\_$set $=$ set$($i for i$,$ value in enumerate$($A$[$rank$])$ if value $==1)$

n$\_$neighs $=$ neighs.copy$()$

neighs$\_$received $=$ set$()$

rovers$\_$received $=$ set$()$

round$\_$received $=$ False

color $=-1$

banned$\_$colors $=$ set$()$

msg $=[-1,-1,$ None$]$ # sender$,$ type, data

round $=[-1,$ False$]$ # round number, round over

# Function to find the smallest available color

def find$\_$smallest$\_$available$\_$color$()$:

global banned$\_$colors

candidate$\_$color $=0$

while candidate$\_$color in banned$\_$colors:

candidate$\_$color $+=1$

return candidate$\_$color

# Function to check if the process has the highest degree in not colored neighbors

def highest$\_$degree$\_$in$\_$not$\_$colored$\_$neighbors$()$:

global n$\_$neighs

return not n$\_$neighs or rank $>$ max$($n$\_$neighs$)$

# Main loop for the algorithm

while state $!=$ TERMINATE:

round$[1]=$ False

neighs$\_$received.clear$()$

rovers$\_$received.clear$()$

round$\_$received $=$ False

# Root process handling termination or starting a new round

if rank $==0$:

if state $==$ COLORED:

# Send termination message if already colored

term$\_$msg $=$ msg$.$copy$()$

term$\_$msg$[0],$ term$\_$msg$[1]=$ rank, TERMINATE

comm.send$($obj$=$term$\_$msg$,$ dest$=$ROOT, tag$=$TERMINATE$)$

else:

# Start a new round

round$[0]+=1$

round$\_$msg $=$ msg$.$copy$()$

round$\_$msg$[0],$ round$\_$msg$[1],$ round$\_$msg$[2]=$ rank, ROUND, round$[0]$

comm.send$($obj$=$round$\_$msg$,$ dest$=$ROOT, tag$=$ROUND$)$

# Process communication and logic during a round

while not round$[1]$:

sender$,\_$type, data $=$ comm.recv$()$

if $\_$type $==$ ROUND:

# Update round number and propagate it to children

round$[0]=$ data

round$\_$msg $=$ msg$.$copy$()$

round$\_$msg$[0],$ round$\_$msg$[1],$ round$\_$msg$[2]=$ rank, ROUND, data

for child in childs:

comm.send$($obj$=$round$\_$msg$,$ dest$=$child, tag$=$ROUND$)$

# If already colored, send discard messages to neighbors

if state $==$ COLORED:

discard$\_$msg $=$ msg$.$copy$()$

discard$\_$msg$[0],$ discard$\_$msg$[1]=$ rank, DISCARD

for neigh in neighs:

comm.send$($obj$=$discard$\_$msg$,$ dest$=$neigh, tag$=$DISCARD$)$

else:

# If highest degree in not colored neighbors, color the process

if highest$\_$degree$\_$in$\_$not$\_$colored$\_$neighbors$()$:

color $=$ find$\_$smallest$\_$available$\_$color$()$

state $=$ COLORED

update$\_$msg $=$ msg$.$copy$()$

update$\_$msg$[0],$ update$\_$msg$[1],$ update$\_$msg$[2]=$ rank, UPDATE, color

for neigh in n$\_$neighs:

comm.send$($obj$=$update$\_$msg$,$ dest$=$neigh, tag$=$UPDATE$)$

else:

# Otherwise, send discard messages to neighbors

discard$\_$msg $=$ msg$.$copy$()$

discard$\_$msg$[0],$ discard$\_$msg$[1]=$ rank, DISCARD

for neigh in neighs:

comm.send$($obj$=$discard$\_$msg$,$ dest$=$neigh, tag$=$DISCARD$)$

round$\_$received $=$ True

# Handling various message types

elif $\_$type $==$ UPDATE:

neighs$\_$received.add$($sender$)$

ack$\_$msg $=$ msg$.$copy$()$

ack$\_$msg$[0],$ ack$\_$msg$[1]=$ rank, ACK

comm.send$($obj$=$ack$\_$msg$,$ dest$=$sender$,$ tag$=$ACK$)$

if state $!=$ COLORED:

n$\_$neighs.remove$($sender$)$

banned$\_$colors.add$($data$)$

elif $\_$type $==$ DISCARD:

neighs$\_$received.add$($sender$)$

elif $\_$type $==$ ACK:

neighs$\_$received.add$($sender$)$

elif $\_$type $==$ ROVER:

rovers$\_$received.add$($sender$)$

elif $\_$type $==$ TERMINATE:

# Terminate and propagate termination message to children

if childs:

for child in childs:

term$\_$msg $=$ msg$.$copy$()$

term$\_$msg$[0],$ term$\_$msg$[1]=$ rank, TERMINATE

comm.send$($obj$=$term$\_$msg$,$ dest$=$child, tag$=$TERMINATE$)$

state $=$ TERMINATE

break

# Check conditions for round completion

This is the code and i need description of high level design with FSM diagrams and FSM table.Either give the pseudocode of actions or the pseudocode of the whole algorithm. It should be something like i added below.