Computer Science 320SC – (2022) Assignment3: Congested Networks
Computer Science 320SC – (2022)
Assignment 3
Due: Monday, September 5th
Congested Networks (part 1)
Given a connected computer network (bidirectional communication) we want to find two different nodes u and v such that we can maximize the congestion between u and v with a continuously sent virus being sent between the pair.
We define the congestion level as the maximum number of edge-disjoint paths between nodes u and v. For example, the network shown in the following figure has three different paths between nodes 0 and 6 such that each edge is only part of one of the paths. Note that two paths are allowed to go through the same node, such as node 7. No other pair of nodes has a higher congestion level.
We have two test cases (easy and harder) for marking on the automarker, worth 1 and 2 marks, respectively.
Input Specification
We will be given a sequence of connected computer networks each with n nodes, n ≤ 40, labeled {0,1,...,n − 1}. The last input case will be followed by a network of n = 0 nodes, which should not be processed.
The specification for a computer network will be as follows: the first line contains a single non-negative value n, denoting the number of nodes. This is then followed by n lines of integers, separated by spaces, denoting the neighbors (zero indexed) of each node. Expect up to 2000 test cases.
Output Specification
For each input case output one integer on a line by itself denoting the maximum congestion level possible for some pair of its network nodes
Sample Input Output for Sample Input Output for Sample Input
8 3
457 2
56
67
7
07
01
127
02346
4
12
02
301
2
0
Congested Networks (part 2)
We extend the problem of the previous section to the case were we want to count only vertex-disjoint paths as a measure of congestion. For this case, the two paths through node 7 of the previous example are not allowed. However, there does exist another pair of nodes (e.g. 6 and 7) that do have three vertex-disjoint paths between them. The input and output specifications are the same as before. This problem will have two test cases on the automarker: an easy set with unlimited submissions allowed (0 marks) and a harder set (2 marks).
