COMP2011		Final Assignment: Due mid-Week 14			94s1

Assignment Name:	mst
Date Due:		Wednesday of week 14
Type:			Group, major (10% of overall assessment)
Implementation:		Modula-2 (gpm) or ANSI C
Estimated time:		Design: 15 hours, implementation & testing: 10 hours

Aim:	To gain experience in designing a fairly large piece of software
	in a group context.

Specification:
	Each group is to write a program that reads in the specification
for a weighted, undirected graph, determines a minimum-cost spanning tree,
and displays the tree and the original graph on a graphics screen.
The input syntax conforms to the following EBNF description:

graph		= "&V" numvertices { vertex } "&E" { edge } .
numvertices	= unsignedint .
vertex		= vertexident label xvalue yvalue .
label		= """ string """ .
vertexident	= letter { letter | digit | "_" } .
xvalue		= realnum .
yvalue		= realnum .
edge		= vertexident vertexident weight .
weight		= realnum .
unsignedint	= digit { digit } .
realnum		= [ sign ] unsignedint [ "." unsignedint ] [ exponent ]
exponent	= ("E"|"e") [  sign ] unsignedint .
string		= { any } .
any		= any character except newline or " .

For example, the following could describe a graph with three vertices
and three edges:
&V 3
A  "vertex A" 10 100
B  "vertex B" 50 150    C "vertex C" 35
     220   &E
A B 17.5     B C 1e+4     C
    A
  -56

Spaces, tabs and newlines can appear between any symbols.
The x and y values associated with each vertex are an indication of
where to display the vertex on the display area.
The graph should be scaled to fit the screen (see Display below).

Groups should be formed very quickly, and may consist of three or
four class members. One member of the group is the spokesperson,
and must register all members using the "register" command.
Subsequent personnel changes must be cleared with GW or LM.

Group duties:
1. To hold regular meetings, starting in week 11. A record of attendance
	and decisions made should be kept.
2. To devise definition modules for the three main components of the
	program.
3. To write the main program module.
4. To produce a written report by the end of week 12 on progress described
	in 1, 2 and 3. The report must include the following statement,
	signed by all group members:
	"We agree that the mark awarded to the project submitted by this
	 group will be given equally to each member registered in the group" 
5. To separately implement the modules making up the program.
6. To combine the implementations into a single program for testing
	and submission.

Besides the main module that controls the entire process, there should be
three modules:
  A Graph input translator, which reads the spec and creates a Graph
	it needs a Table ADT to map vertex identifiers into vertices
  A Minimum-cost spanning tree module, which creates a new graph representing
	the MCST. It should use Prim's algorithm and will need a
	Priority Queue ADT to support the algorithm
  A Graph display driver, which makes calls on the Ming (MINimal Graphics)
	module to display the original graph and MCST.

The low-level modules Table, Graph and PriorityQueue may be adapted
from those given in Kingston. A small amount of change is needed:
  * if you use a hash table for Table, pass the hash function
    as an argument to the insertion and retrieval operations
  * we need a Graph rather than a DiGraph ADT, so each edge must be
    represented twice (and the algorithms modified to suit).
  * for the heap implementation for a PriQ and the hash table, a key
    comparison function should be passed to the operations.
You can use Kingston's implementation of Prim's algorithm with changes
to create a new graph of type Graph.

C Implementations
The C versions should follow the same program structure.
There is more effort in translating the Kingston algorithms, but there
should not be any real difficulty. There *must* be separate header
and code files: just becaise C is flexible doesn't mean that a strict
discipline should not be enforced to enhance readability and reliability.

Display
A simple graphics display module Ming is to be supplied. Because of juggler's
load problems all of Ming's display modes may not be implemented. The
gpm-pc and Turbo C (or possibly Borland C) versions should provide
full functionality. At least, the display operations can be made to
print their arguments, so the MCST can be picked from the (text) output.
   
Assessment: 12 marks for correctness; 8 marks awarded by a tutor.

Submission:	In the supervisor's account, create a tar (tape archive)
of all source files:
	tar cf mystuff.tar  files...
	~cs2011/bin/give  mystuff.tar  mst

The usual late penalties (2 marks per weekday late) apply.