Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Spring 2000

Programming Assignment 5 -- Due May 4, 2000

Objective: To obtain experience in representing and manipulating graphs.

Goal. To implement an adjacency-matrix representation of graphs. To implement the Warshall-Floyd shortest-paths algorithm on the graph.

Graphs may be stored internally in either adjacency-matrix or adjacency-list form. For this assignment, you are to implement (and test) an implementation of a graph object that is stored internally in adjacency-matrix form. You may assume that the vertices of your graph are identified by the integers 0,1,....n-1, and that all edge-weights are floating-point numbers. Your graph object should support the following operations:

create(int n) – creates a graph of n nodes, and no edges.

destroy( ) – destroys a graph

addEdge(int i, int j, float w) – adds edge (i,j), with weight w, to your graph

getEdge(int i, int j) – returns the weight of the edge (i,j)

pathCost(int i, int j) – returns the weight of the shortest path leading from vertex i to vertex j

path(int i, int j) – returns the shortest path leading from vertex i to vertex j

The specifications of the graph are to be read from an input file by your client program. This file has the following format:

u1 v1 w1

u2 v2 w2

...

um vm wm

-1

Here, n denotes the number of vertices in the graph. Each following 3-tuple denotes an edge, which is specified by its source-vertex, its destination-vertex, and its weight. The input file is terminated by a –1.

Rules for submitting this program:

Recall that you are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed comment that begins each program.

Include a (neatly typed – not handwritten) design plan. This design plan should contain a detailed description of all algorithms you use. Include some general comments on the structure and layout of your assignment.

Include a complete listing of all your code, input files, and output files.

Your code must be appropriately commented – if we don’t understand your code with reasonable effort, you get no credit for it. Include comments on the "big-Oh" run-time complexity of all public methods.

Include a test plan detailing how you tested your ADT, and why you believe it is correct.

All of the above should be placed in an envelope with your name and student-ID on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.