MTH 607 Graph Theory Assignment Page

This is the assignment page for course. Assignments will be posted here roughly bi-weekly, just follow the links. The due dates are given when the assignment is posted.

Date posted	Date Due	Description
January 21	-	Preamble
January 29	~~February 15~~ February 19	Assignment 1
March 5	March 14	Assignment 2
March 18	March 28	Assignment 3

Important

The assignments includes various programing tasks which will be auto marked. It is thus very important that you consider the following:

Your programs should be submitted using the submit-mth607 command on jupiter
You can resubmit your files up to the deadline, but if you resubmit after that date marks will be deducted for lateness.
If your program does not compile you will recieve a grade of 0.
Your program must have the filename specified, otherwise it will not compile and you will receive a grade of 0.
Carefully read the output requirements of the assignment. Some assignments will require printed output, some a return value, some output through the write_graph routine, some a combination of these.
Submit only those files required. Do not use multiple files or make files, unless told to do so.
All programs must be in C, they will be compiled with gcc on jupiter. Therefore check that your program compiles correctly on jupiter.

Preamble

Files

graphio.h Graph I/O header file.
graphio.c Graph I/O C code.
mycode.c Sample template for how to call the routines in graphio
Sample graphs in a format readable by graphio.

Since we will need to input and output graphs an initial template including set of routines for doing this is provided in the file graphio.c. Your submitted code will be compiled with graphio.c, so that you can use the routines therein. For example, if you where required to submit mycode.c it would be compiled thus:

gcc -Wall -O3 graphio.c mycode.c -o mycode

A sample template mycode.c is provided to show you how the routines in graphio should be used. Note that you will need to download and #include the file graphio.h. You should also define the variable name appropriately.

The top level routine of graphio.c is called parse_args() and should be called from main, pass it the inputs to main. The return value of parse_args() is non-zero if there was an error and your program should terminate. Here is a sample main

int main(int argc, char *argv[])

{

if(parse_args(argc, argv))

return -1;

ret_val = my_code();

write_graph(file_out, graph, n);

return ret_val;

}

Your compiled program will then read in a graph file specified on the command line. For example, if your program were called graph the command line syntax would be:

graph [<input filename> [<output filename>]]

	If no input name is given outputs to stdin,
	if no output name defaults to stdout

parse_args() reads from the input file and stores the result in the array graph (see below). It also sets the variable n to be the number of vertices and opens the output file with file handle file_out (pass this handle to write graph). graphio.h also sets the value MAX_N, which is the maximum value of n allowed for input.

graphio.c also contains two low level routines, read_graph and write_graph which read and write graphs to and from the array graph to the file pointed to by the handle fhandle. You may call these routines directly, provided you send them a valid file handle and array.

int parse_args(int argc, char *argv[]);

int read_graph(FILE *fhandle, int graph[][MAX_N])

void write_graph(FILE *fhandle, int graph[][MAX_N], int v)

The format of the input and output files is that the first line contains the number of vertices, n. There is then one line for each vertex each containing n integer values, which are the wieghts of the corresponding edge. Some examples of common graphs can be found here. The values on line i are read into an array with the jth entry having the meaning:

`graph[i][j]`	=	weight of edge from vertex i to vertex j,
`graph[i][j]`	=	0 means no edge ij

So the graph is stored internally as a weighted adjacency matrix in the array graph.

Maintained by: P. Danziger, January 2007.