CSE326 Graphs Trees
Spring 2002

Due: Friday, June 7, 2002
  Electronic turn-in due by 5:30 PM
  Group assignments due to Nick by Friday, May 24

Files We've Provided for You in the Course Directory

• bin/wgraph: displays a graph

• bin/kruskal: an example implementation of Kruskal's algorithm

• projects/graph.tar.gz: Sample code and sample graphs

Programming

1. Design a graph data structure that is displayed on the Visualizer. Implement Dijkstra's and Kruskal's algorithms.

2. You may work in groups of up to 3 people. You can use the same groups that you did for the freq assignment. e-mail your groups to Nick by Friday, May 24.

3. You will produce two executables, dijkstra and kruskal. Each reads a graph on standard input, displays the graph in the Visualizer, animates the appropriate algorithm, prints out results, then waits for the Visualizer to quit.

4. kruskal should compute the MST of the input graph. It should print to stdout the MST in the graph input format, suitable for display. See the sample program for an example.

5. dijkstra should compute the value of the least-cost path from vertex 0 to all other vertices. The distances should be printed to stdout, one line for each vertex, consisting of the vertex number and the distance to it from vertex 0, in that order.

6. No STL code outside of the string class may be used. We may make exceptions for particular needs, but you must clear it with use first.

7. projects/graph.tar.gz in the course directory contains a Makefile with the correct library definitions, some sample code for parsing graphs and working with the Visualizer, and some sample graph input files. Make your own graphs to test your code on. The sample graphs weren't meant to be good test cases, just something to get you going.

8. In the README file you include with your turnin, describe any design decisions you made and any interesting implementation issues that came up. You don't need to recapitulate the algorithms described in the textbook or in class. You should discuss your graph data structure. Your README should also explain how you animated the execution of the algorithm. We have not specified how you should do this; it is up to you to decide on a reasonable, informative animation. See the kruskal sample program for an example.

9. Remember to read the turnin info page before submitting your assignment.

10. Extra-Credit: Write a program bicon, which tests if a graph is biconnected.

11. Extra-Credit: Wire Washington! In share/census in the course directory, there is a file wa-places.txt and an associated readme file. This was taken from the US Census Bureau (our tax dollars at work!): Census 2000 Gazetteer. wa-places.txt contains, among other things, all cites in Washington, their location, and their population; the format is detailed in the readme.

    Important: you do not need to display any of this on the Visualizer.

    Important: this extra-credit may cause significant load on the IWS machines. Please nice your programs (talk to us or lab staff for more details).

    For this extra credit, find out how many miles of cable it would take to wire all towns of population at least 10,000 people in Washington state (that should be about 100 points). Here's a Dr. Math link that may be useful in figuring out the distance between two cities from their latitude and longitude.

    For the more ambitious, wire the entire US! Use data from the Census site mentioned above. The interesting thing to look at is the performance of your algorithm. How does it scale up from just Washington state? How did you expect it to scale up? Did it even finish in a reasonable amount of time? (I haven't tried this, myself; You may need to change the population cut-off) Perhaps profile your program with gprof. More extra-credit will be given for implementing heuristic optimizations and discussing them (e.g., do you really need to consider the edge between Boston and Seattle? does your performance improve if you ignore those edges, or does culling them take more time than you save?).

Visualizer

The Visualizer displays objects. Objects have a label and a color. The types of objects you're interested in are Nodes and Edges, which should be used for vertices and edges, respectively. An object is referred to by its id.

A node is created with a position, and an edge is created with its node end points. Positions are given as double-precision floating-point numbers between 0 and 1, with (0,0) being the top-left of the Visualizer window, and (1,1) the bottom-right.

Colors are specified by the SimpleColor enumeration. Examples of colors are eBlack, eRed and eYellow. The primary colors are there, but not much else.

You will probably never need to change the label of any object after creation. Labels are represented internally as strings. There are Svr... functions that set labels to numbers; these work by translating the numbers to a string.

If you right-click in the Visualizer window, you'll get a menu that will allow you to immediately exit the program, and that will print out a list of all the objects the Visualizer knows about. This may be useful during debugging. The list will appear on the stderr of your original program.

Specifics can be found in the header files common.h and client.h, located in the course include/ directory.

Graph Input Format

 Vertex count
 List of vertices
 List of edges

 n vertex-num x y

The vertex numbers should appear consecutively from 0 to count-1; that is, they must appear in order. I designed it this way to make it easy to catch input errors, although in retrospect it seems like overkill.

Each edge line has the format

 src dst weight

The program wgraph in the course directory reads and displays graphs of this format. The project file for this assignment includes some sample graphs in this format and some sample code for reading in the files.