Computer Science 711 S2 – (2021) Assignment 2 Due: August 16th (11:59pm) Requirements This assignment requires you to use OpenMP (with C or C++ language) to give a parallel formulation of a simple graph algorithm. The problem is to compute the radius for a sequence of digraphs (given as input in adjacency list format). Recall that the radius of the graph is the minimum eccentricity of any vertex and the eccentricity of a vertex v the maximum distance from v to any other vertex. We use our CompSci 220 adjacency list format where the first line is the order n of a digraph. This is followed by n lines listing the out-neighbors. Vertices are indexed with labels 0 to n 1. The input sequence of graphs is terminated by a digraph of order 0 (not processed). The output for each input digraph should be a single integer denoting the radius or the text string ‘None’ if the digraph is not strongly connected (or there is no center vertex for that digraph). [ read from keyboard/stdin/cin; print to console/stdout/cout ] Sample Input: 3 1 2 2 0 4 2 0 0 3 1 5 1 2 2 0 0 1 4 3 0 Sample Output: 1 2 None Submission These problem requirements will require you to submit a program to the computer science automarker http://www.automarker.cs.auckland.ac.nz/. It will test whether your program compiles under the gcc/g++ OpenMP environment. You also need to write a 4–5 page report, where you explain your algorithm, test data, and perfor- mance results of your experiments. Submit this report as a PDF file to Canvas (Parallel Computing Programming Assignment). Each of the two parts of this assignment gives 9 marks of your total grade (18 marks total). 1
