KXC251 Algorithms and Metrics, ZUT 2005.

Assignment 2
Due: 3pm on Saturday 10th December, 2005
This assignment is worth 15% of your total mark for the unit.  It consists of 3 parts.  Each part is worth 4 marks.  An additional 3 marks are for overall Program Style. You need to complete all parts to get full marks.

Introduction
You are required to write a program to calculate the minimum length of cable needed to link the nodes in a new fibre-optic network.  The figure below shows the island State of Tasmania in Australia.  The circles on the map are the towns (nodes) which must be linked.



Figure 1:  Network Nodes in Tasmania
The program must take into account any existing links (connections) in the network.  This is so that it can be used to link further towns in the future.  It must also take into account the fact that certain links are not possible due to the terrain (eg. mountains) between the towns.
Information must be input from a text file and stored in a graph.  You will then use Prim’s Minimal Spanning Tree Algorithm to solve the problem.  The algorithm will return a graph of the required network connections.  The program will output a listing of the new connections required.
Input Files
Input to your program is from a text file.  The following is an example (input1.txt):
8
Burnie
Deloraine
Devonport
Hobart
Launceston
Oatlands
Queenstown
Swansea
90  48 245 119 191 117 226
49 163  42 103  -1 137
211   0 150 121 180
169  73 174 109
98 150 114
154  59
211

The 1st line contains an integer x which is the number of towns.
Each of the following x (eg. 8) lines contains the name of one town.
Each of the following x-1 (eg. 7) lines contains the distances in Kilometres (Km) from the corresponding town to each of the towns below it in the list of towns.  In the above example the distance numbers correspond to the following town pairs:
Bur-Del, Bur-Dev, Bur-Hob, Bur-Lau, Bur-Oat, Bur-Que, Bur-Swa
Del-Dev, Del-Hob, Del-Lau, Del-Oat, Del-Que, Del-Swa
Dev-Hob, Dev-Lau, Dev-Oat, Dev-Que, Dev-Swa
Hob-Lau, Hob-Oat, Hob-Que, Hob-Swa
Lau-Oat, Lau-Que, Lau-Swa
Oat-Que, Oat-Swa
Que-Swa
A distance of ‘0’ indicates an existing connection (eg. Dev-Lau).
A distance of ‘-1’ indicates an impossible connection (eg. Del-Que).
2 sample input files are provided with the assignment: input1.txt and input2.txt.  These files are for you to test your program. Your program should work correctly for both input files. It should also work correctly for any other input file of the correct format. Marking may include testing with a different file.
Part 1 – Store Information
You must firstly store the input information in a graph. The nodes in the graph will each represent a town in the input file.  The edges in the graph will represent the distances to towns that can be connected.
Implementation
Write a main method to run the program.  This should be put in a file called “assignment2.cpp”.
You should create 3 classes:
The map class should consist of an array of towns.
The town class should store the town name, plus a list of edges which each represent a possible connection.
The connection class should store the index of the connected town and the distance to it.
You should also include a list class:
You MUST use the list code provided in lectures, but you will need to modify it to store connections.  
IMPORTANT: You are NOT allowed to use any other list class (for example, the STL list class)
Points to Note for all Parts
The program needs to correctly free ALL dynamically allocated memory and close after it runs.
All strings should be stored efficiently.  This means that you will need to read stings into a buffer and then dynamically allocate the appropriate amount of memory for the string, as shown in lectures.
You may find that it is easier to test your program if you have some error checking code.
Try and minimise the amount of code in the main method. Where practical put methods in the other classes and make calls to these in the main method.
Part 2 – Prim’s Algorithm
For this part of the assignment, you must implement Prim’s Algorithm.
Implementation
Put your code for Prim’s Algorithm in a new file called prim.cpp. Note the following outline of Prim’s Algorithm from the lectures:
Starting with an arbitrary vertex, repeatedly add a new vertex and edge to those in the tree so far, each time choosing a new vertex with lowest weight edge to the tree so far, (and adding the relevant edge with the vertex).
In this assignment:
There may already be existing connections (edges).  Therefore, do not choose an arbitrary vertex, always start with:
the existing network connections shown in the input file, OR
if there are no existing connections, the 1st town listed in the input file.
Your function that implements Prim’s algorithm must take the stored map (graph) as a parameter and return another map (graph) which represents the minimal spanning tree.
Points to Note
IMPORTANT: It is a requirement of the assignment that you implement point 1 and point 2 in the ‘Implementation’ section.
The method by which the nearest vertex is found determines the time complexity.  Use a method which is efficient.
Part 3 – Print the New Connections
For this part of the assignment, you must print out the New Connections that are in the minimal spanning tree in order of their length (shortest to longest).  You must also print out the length of each connection and the total length of cable required.
Implementation
The format of the output should be as follows (input1.txt example):
New connections are
   Deloraine to Launceston                 42Km
   Burnie to Devonport                 48Km
   Oatlands         to Swansea                 59Km
   Hobart to Oatlands                         73Km
   Launceston to Oatlands                 98Km
   Burnie to Queenstown                117Km
Length of cable required is 437Km
After this is printed memory should be freed and the program should close.
Points to Note
Do not print out existing connections.
It does not matter which town in each pair is printed first (ie. Deloraine to Launceston = Launceston to Deloraine).  Each pair must appear only once.
It would be a good idea to put the code for the printing in a function called printMap().  You could also use this or similar code to print out your initial map.  This may help you to check that you are loading the input information correctly.
The following code shows how output can be formatted when using cout.
// setw and left,right example

#include <iostream>
#include <iomanip>
using namespace std;

// NOTES:
// setw (10) makes column of width=10 characters
// left moves characters to the left of the column
// right moves characters to the right of the column
// not that left and right settings persist and setw setting does not

int main ()
{
  cout << setw (10) << 11 << setw (5) << 2222 << endl;
  cout << setw (10) << left << 33 << setw (5) << 4444 << setw (3) << right << 55 << endl;
  cout << 66 << endl;
  cout << setw (5) << 77 << endl;
  cout << setw (5) << left << 88 << setw (5) << 9999 << endl;
  return 0;
}

The output from the above code:
        11 2222
33        4444  55
66
   77
88   9999

Similar things can be achieved using the printf() function (which is a c function).

Submission
You should submit an electronic copy your program to your Chinese lecturer, including the following files:
list.h
list.cpp
map.h
map.cpp
town.h
town.cpp
connection.h
connection.cpp
prim.h
prim.cpp
assignment2.cpp (containing the “main” method)
Your files should be well documented.  If you have used code from the lectures, or from anywhere else, this should be clearly stated at the top of the file.
You should submit a signed Assignment Cover Sheet to your Chinese Lecturer.
Marking
Your program will be executed and tested for correctness.  Your code will also be examined to determine a mark for coding style (e.g. comments, suitable indentation, structure etc).  The following marking sheet (which will be returned to you) shows the mark allocation for each part of the assignment.

  哪位大大可以帮忙完成下？

  用C++做的 要求上面都有写 E文太差不翻译了

  谢谢了~~~

[注意]看雪招聘，专注安全领域的专业人才平台！