samuelklam/minimum-spanning-trees

Computing MSTs with Prim's Algorithm

Minimum Spanning Trees (MST)

This repo calculates the expected (average) weight of the MST using Prim's algorithm as a function of n (up to 131072) from the following complete, undirected graphs.

1. Complete graphs on n vertices, where the weight of each edge is a real number chosen uniformly at random on [0, 1].
2. Complete graphs on n vertices, where the vertices are points chosen uniformly at random inside the unit square (That is, the points are (x,y), with x and y each a real number chosen uniformly at random from [0, 1].) The weight of an edge is the Euclidean distance between its endpoints.
3. Complete graphs on n vertices, where the vertices are points chosen uniformly at random inside the unit cube (3 dimensions) and hypercube (4 dimensions). As with the unit square case above, the weight of an edge is just the Euclidean distance between its endpoints.

For a full write-up refer to: minimum-spanning-tree-writeup.pdf.

Usage

In the command line:

$ make
$ ./randmst 0 numpoints numtrials dimension

The flag 0 can be used for testing, debugging, or extensions. The value numpoints is n, the number of points; the value numtrials is the number of runs to be done; the value dimension gives the dimension.

The output is: average numpoints numtrials dimension, where average is the average MST weight over the trials.

minimum-spanning-trees's Issues

code up adjacency list representation - will be useful to discard edges whose weight are unlikely

rediscuss adj list necessity and k(n)

complete cube implementation

complete basic implementation

time all the necessary functions - create matrix, and time to compute prim, etc.

will need to fix arguments so they can be passed into the command line, also may need to use std::vector to do this

create graph with n | average weight | average time

code up adjacency matrix representation

complete hypercube implementation

need to figure out how to have the heap store float values

decide on prim vs. kruskal

add in discard weights for adj matrix

plot all graphs on jupiter notebook

finish the 0, 3 and 4 dimensions

compute the averages

complete square implementation

compare MST averages with others to confirm correctness

code up prim's algorithm

compile code with make

determine k(n) for edge deletion - refer to literature for dimensions 0, 2, 3, and 4 to determine the optimal k

implement n-ary heap to be used for Prims

determine whether we should use adj list

implement a set?