Assignment 3

Question 1

Given an undirected graph G = (V,E) representing a communications network of ground stations connected by fibre-optic links, define the the robustness R(x, y) of the connection between ground-stations x and y in G as
R(x,y) = A / (B * C)

where

• A is the sum over all edges e in E of SP(x,y, G, e), the length of the shortest path (in terms of number of edges) between x and in the version of G in which edge e has been deleted;
• B is the number of edges in G, i.e., |E|; and
• C is the length of the shortest path (in terms of number of edges) between x and y in G.

Note that if the removal of any edge in the graph disconnects a pair of vertices, the robustness of that pair of vertices is defined as positive infinity. The robustness of a connection is essentially a measure of the multiplicative factor by which the length of that connection increases on average if any individual link in the network goes down.

Write and document a Python program that, given an adjacency-list description of an undirected graph specified in a file that is input as a command-line argument, computes and displays the robustness of the connection between every pair of vertices in that graph. A graph on n vertices is specified as an (n + 1)-line file, where the first line has a single number giving the value of n and each line i of the remaining lines specifies (in sorted order) the vertices adjacent to vertex i. For example, the undirected graph

is described by the following file:

6
1:  2  4  5
2:  1  3
3:  2  4  6
4:  1  3  6
5:  1  6
6:  3  4  5

You may assume that all input files are formatted correctly. Examples of several program runs relative to the graph files net1.dat, net2.dat, net3.dat, net4.dat, net5.dat net6.dat, and net7.dat are given in script file out.script.

Hints

Your program need not perform computations on a graph using the representation in which that graph was given,

Your program need not use an algorithm that computes shortest paths only in terms of number of edges.

Assignment Submission

Please submit your program files for Q1 through the course D2L / Brightspace shell by 11:59pm on the assignment due date. Note that each program file must have the following comment block at the top, where the X's are replaced with the appropriate information. For example, my Python program for Question #1 of this assignment would begin with the following comment block:

#########################################################
##  CS 3600 (Winter 2024), Assignment #3, Question #1  ##
##   Script File Name: NRC.py                          ##
##       Student Name: Todd Wareham                    ##
##         Login Name: harold                          ##
##              MUN #: 8008765                         ##
#########################################################

You do not have to develop your code on our CS departmental systems. However, as your code will be compiled and tested on our CS departmental systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• Nov 21, 2023
  Assignment #3 posted.

Created: November 21, 2023
Last Modified: November 21, 2023