Updated: Sep 17
Total points: 10
This project needs to be completed using Java and is an individual project. Naming of your programs must strictly follow the following convention: (1) one file for each part; (2) Lab3 followed by your Uid and I for part I (for example Lab3U00998499I.java). Upload only your source code (one file for each part) to the Pilot dropbox.
Your report must adequately describe your solutions, such as algorithm, pseudo code, implementation, time complexity etc.
The solution time complexity for this lab is an important consideration in grading. Therefore, you should use proper data structure and implement your solutions carefully. Test cases will exercise your programs thoroughly. Your programs should efficiently handle potentially large problems. Expect that your program produces results for all test cases within 4-5 seconds.
Part I. Widest Path Routing
N large files (1≤N≤10^5), numbered 1…N, are scattered on N distinct storages throughout a network that connects these storages. These storages are also numbered 1…N, such that file fi is at storage si. M links (1≤M≤105), numbered 1…M, where link i bidirectionally connects storage ai with storage bi, and has a bandwidth wi (1≤ ai, bi≤N, ai ≠ bi,1≤ wi ≤10^9). Bandwidth wi takes on integer values.
At any point in time, two files located at two storages directly connected by a link may simultaneously swap places through the link. That is, the file on storage a can be transferred to storage b and the file on b can be transferred to a using the link that connects a and b. The files must perform such swaps until fi is at storage i for 1≤i≤N. That is, the files must eventually be placed at their “rightful” storage using the network.
To reduce the time to accomplish the task of moving files to their rightful storages, you are asked to design and implement an algorithm to maximize the bandwidth of the least wide link which the file transfer must use to move the files to their “rightful” storages speedily. It is guaranteed that it is possible for the files to move to their rightful storages.
INPUT FORMAT (file storage.txt):