Math 314 MATLAB projects

You will have to write about one page of code. After testing it, email your program (not output, just the program) to me in text-only format. Due date is Tuesday 3/23 (after Spring Break).

Kruskal's algorithm

Implement Kruskal's algorithm as outlined in the textbook and in the course.

Here is a test file with four graphs.
Start with this file.

Here are rigorously ALL the MATLAB functions that I need for my model solution

Function	Usage	Comment
sort	[Y,ind]=sort(X)	ind has subscripts so that Y(i)=X(ind(i)) for all i
Colon :	pos(e,:)=[i,j]	record the position of some edge
&	(Gsize>e) & (C(rowcurr)==C(colcurr))	Logical AND
if ... end;	if (outlevel>3), display(H); end;	note comma! terminate with end;
if else end;	if (e<=Gsize), ...; else ...; end;
for	for e=0:Gsize, ...; end;	Loop with known number of repeats

while	while (Gsize>e), ... end;	note comma! terminate loop with end;
zeros	zeros(m,n)	Create m by n matrix of zeros
Optional		For prettification, debugging
int2str	int2str(e)	convert int to string for use with disp
disp	disp(['number of edges', int2str(e)])	alternative to display function
help	eg help elmat, help sort ...	get help on matrices, sorting, ... anything

I guess the two tricky parts are the correct conditions for the loops and using the sorted list of edges - creating a list of edge weights is easy. Sorting it can be done using the sort command. But the sorted list itself is no use - you really need to know the original position in the edge list and then its endpoints. The first is achieved by the [Y,ind]=sort(X) command - see help sort for more information. The second goal is achieved by storing endpoints for each edge in some Gsize times 2 - matrix pos.

Conditions, Restrictions

If you type 'kruskal' or 'MATLAB kruskal' into Google, you get a number of implementations. Therefore we have to adopt some clear policies.

I insist that you write this in MATLAB, no Java, C++ or anything else.
Your function has to start with the line
function T=kruskal(n,W,outlevel)
taking three parameters with the following description.
- n - number of vertices in graph
- W - n times n - matrix of edge weights. Assume that all edge weights are positive, and non-existent edges are marked by zeros.
- outlevel - nonnegative integer. Display no intermediate results if outlevel is zero, more and more as outlevel increases (be sensible - do what you need for debugging your program). Leave these lines in there - the loss in speed is negligible compared to the ease of understanding your program.
Use the algorithm as described in the lecture and in the textbook, do not add refinements 'as described in Ahuja et al (xxxx)'. The output should be the matrix H of edge weights for a minimal spanning tree.
Write comments at crucial steps! My model solution has 26 comments in 89 lines total. If you write comments right on top they will be displayed if the user types help kruskal.

Now it is still possible to download and modify a program from the internet, but the ones I have seen are much more complicated. Most have also a very different input format. So I think it is easier to actually write the program yourself. However, I will accept anything that meets the specifications on input format and performs the correct algorithm, ie I will test it on a few more examples.

Before asking me, look up the MATLAB help pages! And revise the description of Kruskal's algorithm and the examples that we did in class.