Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Computer Science 220 S2 (2024)
Assignment 6 / Week 8 (Graph Representation)
Due date: Sept 20, 2024
Problem Statement
Two programs are required to learn how to process compter representations of digraphs.
Program 1: Read Adjacency Matrices and output Adjacency Lists.
Recall the adjacency matrix format as described in the CS220 textbook. Here, the first line for each digraph is an integer n indicating the order of the digraph. This is followed by n white space separated lists of 0 and 1 values, where the j-th item on row i indicates whether the arc (i, j) is included in the digraph. We have nodes labeled 0 to n − 1.
Program 2: Read Adjacency Lists and output Adjacency Matrices.
Recall the adjacency list format as described in the CS220 textbook. Here, the first line for each digraph is an integer n indicating the order of the digraph. This is followed by n white space separated lists of (out-) adjacencies for nodes labeled 0 to n − 1.
In both problem cases we will have a sequence of digraphs to process. The digraphs may contain up to a thousand nodes. The last digraph of the sequence will be a digraph of order 0.
In both input cases you output a digraph of order 0 in the desired format. Input comes from stdin (keyboard) and output goes to stdout (console).
Submission and Due Date
Submit your Python source code to https://www.automarker.cs.auckland.ac.nz. There will be two test cases provided for each problem, an easy test case (3 marks) and harder test cases (2 marks). A maximum of 8 submissions is allowed before a penalty of 20% will be applied.
The deadline is 23.59pm (automarker time) on September 20th. There is a late submission date three days later which costs 20% per problem (September 23rd).
Note we use plagiarism detection software so do not share any source code with your fellow students, nor use any AI tools (see https://academicintegrity.cs.auckland.ac.nz/).
Sample Input/Output
The following can be used as either input or output depending which way you are converting representations. Note we output sorted adjacency lists but the input may not be sorted, nor be single space-separated. You need to process the input stream with properly using string methods strip() and split().
Adjacency Lists
3
1
2
0 1
5
2 4
0 4
4
0
1 2
8
1 2 3 5
0 4 5 6 7
0 1 6
4 6 7
1 3 6 7
0 1 4 7
1 2 4 5
0
Adjacency Matrices
3
0 1 0
0 0 1
1 1 0
5
0 0 1 0 1
1 0 0 0 1
0 0 0 0 1
1 0 0 0 0
0 1 1 0 0
8
0 1 1 1 0 1 0 0
1 0 0 0 1 1 1 1
1 1 0 0 0 0 1 0
0 0 0 0 1 0 1 1
0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 1
0 1 1 0 1 1 0 0
0