Project-Spanning Tree

A group of network designers at SkyNet find themselves facing the following problem. They have an undirected connected graph G = (V, E), in which the nodes represent sites that want to communicate. Each edge e is a communication link, with a given available bandwidth be. That is, each edge has a maximum amount of data that it can transfer in a fixed amount of time given as be. For each pair of nodes u and v, SkyNet wants to select a single u−v path P on which this pair of nodes will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains; that is, b(P) = min(be) where be belongs to P. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u − v paths P in G, of the value b(P); in other words, it is the path over which the most data can be transferred subject to the bandwidth restrictions on the paths. It’s getting to be very complicated to keep track of a path for each nodes, so one designer make a bold suggestion: may be one can find a spanning tree so that the unique path in the tree also attains the best possible bottleneck bandwidth, for every pair of nodes. Does this method work? The answer, though not obvious at a first glance, is a resounding yes (What kind of spanning tree should this be?) This project is to build a spanning tree that contains, for every u−v path in G, the best achievable bottleneck rate. Consider the following edges (defined on a graph with vertexes A, B, C, and D): 6 A B 5 C A 15 A D 10 B C 20 D B 25 D C 30 The spanning tree that would solve this problem would include the following edges (note that the edges are undirected, so the actual ordering of the nodes does not matter): 15 A C B D C D Note that the minimum bandwidth over any u − v paths found in this tree is 15. Input Specification Your program will first prompt the user for the name of input file (without the extension), and then read the data from the file named [login to view URL], which specifies actual links (edges) in the communications network and their corresponding bandwidths. This file will begin with a single line containing only an integer that represents the number of communications links (i.e. edges) there are in the problem. This line will then be followed by one line for each communication link in the following format: <node1> <node2> <bandwidth> where: • <node1> and <node2> are alpha-numeric strings (with no white space) representing two nodes in the graph. • <cost> will be a positive integer representing the bandwidth of the corresponding edge (i.e., communications link). Any amount of white space may separate the fields, so make no assumptions that allow for only a single space between the fields or similar restrictions. It is also possible that there will be white space before the first field (i.e. node1).