Task. Deadlock Detection with One Resource of Each Type

Input File Format $($Adjacency Matrix$)$

Background. As shown in the above figure $($left$),$ processes' resource holding and requesting

states can be illustrated as a graph, and further represented by an adjacency matrix $($right figure$).$

Input format. In this task, your program will be given several one$-$way directed graphs as $a$

single input file, with each graph formatted as the figure on the right $($see the provided input file

example$).$

Your program. Your task is to write a deadlock detection program to $1)$ read each matrix

$($graph$)$ from the input file, $2)$ perform a deadlock detection for each graph, and $3)$ write the

detection results to an output file.

Output format. The output file will contain only $\text{'}1\text{'}$ or $\text{'}0\text{'}$ for each line $($for each graph$),$ where

$\text{'}1\text{'}$ indicates deadlock detected and $\text{'}0\text{'}$ indicates the graph is deadlock$-$free $($see the provided

output file example$).$

Testing. You are responsible for creating a testing file to verify the correctness of your program.

Submissions. Code file with line$-$by$-$line comments$/$explanations

Evaluation. Our teaching assistant will use a randomly generated input file $($will not be

provided$)$ with the same format above to check the correctness of your algorithm.

Programming Language: Python