SI433 Project II: A Greedy Graph Algorithm

In this project you will implement Prim's algorithm, and use it to compute minimum spanning trees for Euclidean Graphs (graphs whose vertices are points in the plane) and display them on the screen.

The Pieces

A File Format for our Graphs

The graphs we're dealing with are undirected (meaning that if there's an edge from u to v, there is also an edge from v to u), and each vertex is associated with a point in the plane, so there's a well-defined way to draw the graph. For an edge from vertex u to vertex v, we say that the weight of the edge is the distance from the point associated with u to the point associated with v.

You'll read in a description of a graph in a very simple format. The first line is of the form "Gn", where n" is the number of vertices in the graph. The next n lines of the file are of the form

Vi:(x,y): n1 n2 ... nk -1 

where i goes from 1 to n, and vertex i has the k neighbors n1, n2, ... nk. The pair (x,y) are floating-point numbers giving the coordinates of vertex i. So, for example:

G4
V0:(-1.0,0.0): 1 2 -1
V1:(0.0,1.0): 0 2 3 -1
V2:(0.0,-1.0): 0 1 3 -1
V3:(1.0,0.0): 1 2 -1

... describes this graph with four vertices and five edges. The files graph5 and graph10 provide some larger examples. Also, you can generate random graphs using the program gengraph in this directory. The command gengraph 100 300 will generate a random graph of 100 vertices with approximately 300 edges.

Basic Classes for Graphs and Vertices

A class Vertex and Graph are provided for you in Project2.h. These are essentially the same classes as we used in the homeworks for classes 8 and 9. You can add to these classes all you like, but you shouldn't remove any of what's there. I've given the class Vertex data members x and y, which you'll have to use to store the x and y coordinates for each vertex ... that's what my rendering functions use to draw the graph on-screen!

An Interface to the Rendering Functions

The functions

void  StaticRender(Graph &G);
void  StaticRender(Graph &G, vector &Pred);
void AnimateRender(Graph &G, vector &Pred, vector &Ord);

... are what I'm providing you with to draw pictures of your graphs and spanning trees. The first parameter is, of course, the graph. StaticRender(G) simply plots the graph G. StaticRender(G,Pred) plots the graph G, and superimposes the spanning tree defined by Pred ... exactly how Pred defines a spanning tree will be described later.

Pred is of type vector<int>. Essentially, Pred[i] is the index of vertex i's predecessor, i.e. when you added vertex i to the spanning tree (see the description of Prim's Algorithm below), what vertex did you get to vertex i from? [Note: if vertex i doesn't have a predecessor, Pred[i] must be -1.] This is what the rendering algorithm uses to determine what edges are in the spanning tree. AnimateRender(G,Pred,Ord) takes another vector<int>, "Ord" as a third argument. You'll set up Ord to contain the indices of the vertices of the spanning tree in the order they were added, so that my routines can give an animation of the process your implementation of Prim's algorithm went through in constructing the tree.

here is a small main function that uses StaticRender, and Here is a picture of its output. Note that StaticRender and AnimateRender only plot points in the rectangle with lowerer left corner (-2,-2) and upper right corner (2,2).

The Structure of Your Project

For this project you'll need to download the files Makefile, Project2.h, and render.cc. The file render.cc contains the definitions of all the functions that do the rendering for this project. Because compiling and linking to MesaGL require telling the compiler about the location of the Mesa installation, I bundled all of it up in the Makefile, which assumes that your code is in a file called main.cc. All of these files (including your main.cc) need to be in the same directory. From that directory, typing "make" will cause your program to be compiled and linked into an executable named "go". Makefile is quite simple, so you should be able to look at it and see what would need to be changed in order to, for example, add another source file to be compiled and linked. [Note: if you cut an paste "Makfile" from the browser to your home directory, make sure that there is at least one tab before the "g++" on line 9. If there isn't, your make won't work!]

A Definition of Prim's Algorithm

A minimum spanning tree for a graph G is a tree that contains all the vertices from G and whose edges are edges from G, such that the sum of the lengths of all the edges in the tree is a small as possible. Prim's algorithm is a greedy algorithm, so we need to phrase the process of constructing a spanning tree as a series of choices. We start with some vertex s, and delcare it to be "in the tree", and all other vertices to be "out of the tree". We then continually choose a vertex that is not in the tree, and add it to the tree. The trick, of course, is how to choose the vertex! The greedy choice for Prim's algorithm is to choose the vertex whose "distance" from the tree is as small as possible. The "distance" from vertex v to the current tree is the length of the shortest edge from v to any vertex already in the tree. If there is no edge from v to any of the vertices already in the tree, the distance is "infinity"!

When vertex v is "added to the tree", we need to keep track of how we attached v to the tree, i.e. which vertex was it that was already in the tree and was joined to v by that short edge? To do this, we need to keep track of each vertex's predecessor when it is added to the tree. It's also helful to keep track of each vertex's distance from the current tree. Here is a psuedo-code description of Prim's Algorithm.

Prim(G,s), where G is a graph and s the "source" vertex for the
algorithm

  1) for each vertex v, initialize dist(v) to infinity and pred(v)
     to nil
  2) set dist(s) to zero
  3) mark each vertex as "not part of the tree"
  4) of all the vertices that are not part of the tree, find `v', the
     vertex with smallest "dist" value
  5) mark v as "part of the tree" and set dist(v) = 0
  6) for each neighbor u of vertex v
       if dist(u) > weight of the edge from v to u
         set dist(u) = weight of the edge from v to u
         set pred(u) = v
  7) if there are vertices that are not part of the tree and have dist
     value other than infinity, then goto 4

I strongly recommend that you make up a small graph and step through this algorithm by hand to understand how it works!

The Project

Part 1 [40 Points]: Reading and Rendering the Graph

Write a "main" program that reads in a graph in the format described above, and uses StaticRend to display the graph on the screen. It should work for any graph defined in our file format. Turn in the source code for your main function (and for Project2.h if you've modified it), and a screen capture of the output your program produces for graph100. (Note: a wise student might test their program on some small graphs, like the graph on 4 vertices that I gave you above.)

Part 2 [40 Points]: Implementing Prim's Algorithm

Add to your original "main" program so that, after you've read in the input graph, you use Prim's Algorithm to construct a minimum spanning tree for the graph. Your program should represent the minimum spanning tree as a vector<int> Pred, such that Pred[i] is the index of vertex i's "predecessor". Note that the "source" vertex for Prim's Algorithm will have predecessor -1, as will any vertices that are unreachable from the "source". Your program should use StaticRender(G,Pred) to display a picture of the graph with the minimum spanning tree. Turn in the source code for your main function (and for Project2.h if you've modified it), and a screen capture of the output your program produces for graph300. (Note: a wise student might test their program on some small graphs.)

Part 3 [10 Points]: Analyzing Your Implementation of Prim's Algorithm

Print out your implementation of Prim's algorithm, and analyze its worst case time complexity in terms of n, the number of vertices, and e, the number of edges. If you can't get a "theta" expression for the complexity, at least give me a "big-O". I want to see your work.

You can use my "gengraph" program to try your algorithm on a variety of different graph sizes. For example,

~wcbrown/courses/SI433/projects/P2/gengraph 500 10000 | go

generates a graph with 500 vertices and about 10,000 edges, and uses my solution to the project to construct a minimum spanning tree. It takes several seconds to run. With what size graphs does this become infeasible?

Part 4 [10 Points]: Animating Prim's Algorithm

Modify your implementation of Prim's Algorithm so that it keeps track of the order in which vertices are "added" to your minimum spanning tree. In particular, construct the vector<int> "Ord" such that Ord[0] is the index of the first vertex "added" to the tree, Ord[1] is the index of the second vertex added to the tree, ... and so on up to the last element of Ord being the index of the last element added to the tree by your implementation of Prim's Algorithm. You'll call AnimateRender(G,Pred,Ord) to produce an animation of your implementation's construction of a minimum spanning tree. Run your program produces on graph300. Turn in the source code for your program that produces the animation.

Due Dates and Submitting Your Project

Extra Credit