Đã Đóng

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).

Kĩ năng: Lập trình C++

Xem nhiều hơn: tree art project, visual studio 2008 sharepoint custom field project, tree school project, tree vb6 project, project decision tree, mba project related marketing field, binary tree code project, optimal binary search tree code project, add field project dotproject, track field project, create dynamicaly tree mlm project asp net, project reference number field sahrepoint, project reference number field sharepoint, family tree poster project, family tree school project poster

Về Bên Thuê:
( 3 nhận xét ) Edwardsville, United States

ID dự án: #28321927

2 freelancer chào giá trung bình$30 cho công việc này

it2051229

Hi there, I do C++ programming and have good command in data structures and algorithms. I went through your requirements and I would like to do this project if given the opportunity. Let me know if you are interested.

$30 USD trong 1 ngày
(640 Nhận xét)
7.3
starkagi

Thanks for providing such a detailed description of the task. I've put some thought into this and I think using the algorithm I came up with, it would be possible to calculate the spanning tree you're looking for. This Thêm

$30 USD trong 1 ngày
(0 Nhận xét)
0.0