Assignment 3: Graph Algorithms
1 | Please read the entire assignment before starting. |
Goals
In this assignment we want you to write simple graph algorithms forundirected
graphs. There are three algorithmic tasks. Each task should be coded up in a
separate program.
- Determine the order of the largest component.
- Convert to adjacency matrix representation.
- 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 integernindicating the order of the graph. This is
followed bynwhite space separated lists of adjacencies for nodes labeled 0 ton−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
0 3
1
5
1 4
0 2
1 3
2 4
0 3
0
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 (thinkwindiff,vim -d,
etc). That is, any other output besides a sequence of answers required is awrong
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
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
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
automarkerhttps://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 liketask1.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).