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