Readme for CS760K Project - Edge Colouring Bipartite Graphs =========================================================== Compiling: ---------- This project is written in Java, so it doesn't matter what type of machine is used to compile it, as long as the version of Java is JDK1.1.x. Compile by typing "make" The compiled code will be in a directory "class" under the current directory. Running: -------- go to the "class" directory created. The following commands are possible: java birch.cs760k.Main - this gives a usage message on what commands are valid java birch.cs760k.Main file infile > outfile - this reads a graph from infile and outputs to outfile java birch.cs760k.Main random > outfile - this generates a random graph meeting the constraints and outputs to outfile. the default settings are: minDeg = 0 maxDeg = 1073741823 minV = 0 minDeg = 1073741823 java birch.cs760k.Main visual - this runs the graphical user interface for the program java birch.cs760k.Main script fileStart - this runs the script to test the program. The script randomly picks a number of vertices and creates a file fileStart.txt where it outputs the degree, number of edges, time in seconds, and possible exceptions for a randomly created graph. n gets progressively larger, and 500 graphs of degree 1 to 500 is created for each n. On the web as an applet: http://www.cgl.uwaterloo.ca/~ssiu/cs760k/ Note that when the program is executed as an applet, open and save to files are disabled for security reasons. Instead, input and output via text areas is supported. User Interface: --------------- The user interface is self explanatory. Mouse over a button to get a text description of what it does at the bottom of the application. Error messages are outputted to the bottom. Text description of each step in the algorithm is displayed at the top. Input: ------ input file format is as follows: line1: number of vertices in class0 line2: number of vertices in class1 line3+: v0 v1 where v0 is a vertex in class0 and v1 is a vertex in class1 (vertex labelling starts from 0) and (v0, v1) is an edge in the graph. Any input on the same line after v1 is ignored. Multiple edges are allowed. Output: ------- output file format is as follows: line1: number of vertices in class0 line2: number of vertices in class1 line3+: v0 v1 c where (v0, v1) is an edge and c is the colour given to that edge as of output. Graph colouring can be output before the colouring is done.