Computer Science 220S2C (2019) Assignment 3: Graph Algorithms
Due: Friday, October 4, 2019
Please read the entire assignment before starting.
Goals
In this assignment we want you to write simple graph algorithms for undirected graphs. There are three algorithmic tasks. Each task should be coded up in a separate program.
1. Determine the order of the largest component. 2. Convert to adjacency matrix representation. 3. Compute the diameter.
Input Format
Input for these problems consist of a sequence of one or more (undirected) graphs taken from the keyboard (e.g. sys.stdin). Each graph is represented by an adja- cency list. The first line is an integer n indicating the order of the graph. This is followed by n white space separated lists of adjacencies for nodes labeled 0 to n − 1. The input will be terminated by a line consisting of one zero (0). This line should not be processed. Two sample input graphs are listed below.
4
1 03
1
5
14
02
13 2442 03
0
G1 G201 01
32
3
Output Format
Output will be like the model answers given below to the console (e.g. sys.stdout). Your program will only be correct if there is no difference between your output and the model solution using an automated ’diff’ checker (think windiff, vim -d, etc). That is, any other output besides a sequence of answers required is a wrong program!
Output for Task 1
Graph 1 has a component of order 3.
Graph 2 has a component of order 5.
Output for Task 2
4
0100 1001 0000 0100
5 01001 10100 01010 00101 10010 0
Output for Task 3
Graph 1 is disconnected.
Graph 2 has diameter 2.
Besides have a correct program your grade for this assignment will also be based on how efficient (fast!) your program can handle the marker’s data. To get marks it must complete with the correct answer within a few seconds on a reasonable sized data set (e.g., expect more than two graphs with at least 1000 vertices).
Submission and Due Date
Submit your source code for your three programs to the CompSci 220 assignment automarker https://www.automarker.cs.auckland.ac.nz/ on or before the end of October 4th. Please see the help/FAQ subpage for further information.
To have a fair test on timing, we only allow implementations using Python for this assignment. You should name your submissions like task1.py .. task3.py.
This assignment is worth 7.5% of your course grade. There will be two input cases per task worth 3 marks (easy cases) and 2 marks (harder cases), respectively. You can submit up to 10 times per task before getting 20% penalty (if you eventually solve that task).