Programming Problem #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. You have been given Python files myNRCClasses.py and NRC.py and you need to fill in the function definitions in file myNRCFunctions.template according to the computation described above create a file myNCRFunctions.py such that NCR.py (when run relative to given problem-description files net1.txt, net2.txt, net3.txt, net4.txt, net5.txt, net6.txt, and net7.txt using python3 on the CS departmental LabNet systems) can exactly reproduce the outputs in script file out.script.

You should not modify any of the code in provided files NRC.py and myNRCClasses.py. When modifying file myNRCFunctions.template to create myNRCFunctions.py, try not to

• modify the given import statement;
• add other import statements (this includes import statements added automatically by IDEs such as PyCharm);
• add, modify, or remove function definitions;
• add new class definitions or global variables (use the provided classes in file myNRCClasses.py); or
• access any provided class attributes directly (use provided attribute access functions in file myNRCClasses.py).

Hints

You may find it useful to progress through the given tests in the given order when debugging your code.

When debugging your code, you may find it useful to look at the debugging version of the output given in script file out.debug.script.

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

Additional Notes:

• July 15, 2026
  Programming Problem #3 posted.

Created: July 15, 2026
Last Modified: July 15, 2026