Prac 4, CSE2304, CSSE, Monash, Semester 1, 2002

Group A: week 10, 13 - 17 May
Group B: week 11, 20 - 24 May

Candidate: You must prepare your solution to this programming exercise in advance. The designated platform, on which your solution must be demonstrated and on which it will be marked, is the `gcc' compiler running on `Linux'. If you develop a solution on another platform, it is your responsibility to ensure that it works correctly on the designated platform. Read the information under the [prac' guide], [on C and code modularity] and [plagiarism] links on the subject home page.

Groups: Note that different prac'-groups might be set different tasks. Make sure that you do your task. You will get zero marks if you solve the wrong problem.

The objectives of prac's 4 and 5 are to learn one or more graph processing algorithms, and to apply them to a practical problem.

All: You can assume that there will be no more than `M' vertices in any [graph], e.g. M=1000.

Group A

Some readers of books, and some viewers of films, delight in finding errors in plots. It is said that there are several plot errors in War and Peace. One kind of mistake is where two events occur in an impossible order - e.g. someone has possession of an object before they find it for the first time.

In pracs 4 and 5 you have to write a program to detect errors of misordering in plots.

Data:

One or more `events', one per line.

Each event has a unique number and a short description of less than `n' characters (e.g. n=50), e.g.
7 Jonah flies to N.Y.
5 Annie hears Sam on the chat show.
11 Jessica books Jonah a ticket to N.Y.
etc.

The last event is followed by a blank line.

After the events there are one or more `constraints', one per line.

Each contraint is specified by two event numbers, e.g. 3 1 which indicates that the 1st event (3) must occur before the 2nd event (1).

After the last constraint comes the end of the file.

Task:

Write a program to read data of this type from a file (specified as a command-line parameter) and store the constraints in a directed unweighted graph as an adjacency matrix. Each event is represented by a vertex. Each constraint is represented by an edge from the first event to the second.

[2 marks]

Your program must then print the graph of constraints in some compact way, giving event numbers only, to prove that it has input the data correctly.

[1 marks]

The program must detect if there is a `cycle' of constraints, e.g. a before b before c ... before a, -- which shows a plot error. (e.g. You could use Warshall's algorithm.) Print any two events from any cycle of the graph has one, e.g. maybe
26 Sam and Annie divorce, apparently before
17 Sam and Annie marry, -- error.

[2 marks]

Create some test data sets to test your program well.

[1 marks]

Group B

Analysis of web sites:

Data:

One of more web pages, one per line.

Each page has a unique number and a description of less than `n' characters (e.g. n=100), e.g.
7 http://www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/   -- 2304 home
3 http://www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/2002/tute5.html
8 http://www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/2002/progress.html
etc.

The last page is followed by a blank line.

After the pages there are one or more `links' between pages, one per line.

Each link is specified by two page numbers, e.g. 7 3, which indicates that the first page (7) has a direct link to the second page (3).

After the last link comes the end of file.

Task:

Write a program to read data of this type from a file (specified as a command-line parameter) and store the links in a directed unweighted graph (or equivalently a directed weighted graph where all edges have weight `1') as an adjacency matrix. Each page is represented by a vertex. Each link is represented by an edge from the first page to the second.

[2 marks]

Your program must then print the graph of links in some compact way, giving page numbers only, to prove that it has input the data correctly.

[1 marks]

The program must detect if the graph of pages is connected [was "completely connected" by mistake], i.e. if there is a `path', consisting of one or more links, from each page to every other page. (e.g. You could use Warshall's algorithm.)
(NB. Every page is considered to be linked to itself.)
If the graph is not connected, print any two pages, i and j, and their descriptions, such that there is no path from page i to page j.

[2 marks]

Create some test data sets to test your program well.

[1 marks]