Assignment 2

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 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 graph should be a single integer denoting the radius or the text string ‘None’ if there is no center vertex for that digraph. [ read from keyboard/stdin/cin; print to console/stdout/cout ]

Sample Input:                                          Sample Output:

3                                                                    1

1   2                                                               3

2                                                                    None

0

4

2

0

0  3

5

1  2

2  0

0  1

4

3

0

Submission

These problem requirements will require you to submit a program to the computer science automarker . 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 performance results of your experiments.

学霸联盟