//Author: Kevin Achenbach
//Date: 4/20/14
//Description: Given coordinates, will find the total distance of a MST
// using Prim and Kruskals MST
#include <stdio.h>
#include <math.h>
//distance can not be greater than INF
#define INF 100000
//probably unneccessary, just make array if time
struct Vertex {
int rep;
};
void prim(int numinput, double graph[][2]);
void kruskal(int numinput, double graph[][2]);
void unionVert(struct Vertex[],int len, int rep1, int rep2);
/* Expected input:
# of test cases
# of coordinates
x1coord y2coord
etc..
*/
int main() {
int testcase, numinput, i, j;
scanf("%d", &testcase);
for(j=0; j<testcase; j++){
scanf("%d", &numinput);
double graph[numinput][2];
//get input and place in graph array
for(i=0;i<numinput; i++) {
scanf("%lf", &graph[i][0]);
scanf("%lf", &graph[i][1]);
}
prim(numinput, graph);
kruskal(numinput, graph);
}
return 0;
}
struct Edge {
double weight;
int p1, p2;
};
// Kruskal union, makes 2 trees into 1
void unionVert(struct Vertex* vertGraph,int len, int rep1, int rep2) {
int i;
if(rep1<rep2)
for(i=0; i<len; i++) {
if(vertGraph[i].rep == rep2) {
vertGraph[i].rep = rep1;
}
}
else {
for(i=0; i<len; i++) {
if(vertGraph[i].rep == rep1) {
vertGraph[i].rep = rep2;
}
}
}
}
void kruskal(int numinput, double graph[][2]) {
//pg 631 MST-Kruskal ALG
//First checks for <2 inputs
if(!numinput) {
printf("\nError: Number of inputs must be greater than 0\n");
return;
}
else if(numinput == 1) {
printf("\n0.00\n");
return;
}
//total number of unique distances is given by n(n-1)/2
int totalNumDist = (numinput*(numinput-1))/2;
//contains all edges
struct Edge edgeGraph[totalNumDist];
int count = 0;
int i,j;
double first,second,totalDist;
//map out the distances
//only write distances once as opposed to prim's
for(i=0; i<numinput; i++) {
for(j=0; j<numinput; j++) {
if(i<j) {
first = graph[i][0]-graph[j][0];
first = pow(first,2);
second = graph[i][1]-graph[j][1];
second = pow(second,2);
first += second;
edgeGraph[count].weight= sqrt(first);
edgeGraph[count].p1 = i;
edgeGraph[count].p2 = j;
count++;
}
}
}
//insertion sort of the edges
double storeWeight;
int storeP1, storeP2;
//insertion sort to put lowest edge weights at top of the array
for(i=1; i<totalNumDist; i++) {
j=i;
while(j>0 && edgeGraph[j].weight < edgeGraph[j-1].weight) {
storeWeight = edgeGraph[j].weight;
storeP1 = edgeGraph[j].p1;
storeP2 = edgeGraph[j].p2;
edgeGraph[j].weight = edgeGraph[j-1].weight;
edgeGraph[j].p1 = edgeGraph[j-1].p1;
edgeGraph[j].p2 = edgeGraph[j-1].p2;
edgeGraph[j-1].weight = storeWeight;
edgeGraph[j-1].p1 = storeP1;
edgeGraph[j-1].p2 = storeP2;
j--;
}
}
struct Vertex vertGraph[numinput];
//each vert is a seperate tree
for(i=0; i<numinput; i++) {
vertGraph[i].rep = i;
}
//check off the first edge
totalDist = edgeGraph[0].weight;
//intial smallest edge is used to connect the seperate trees
unionVert(vertGraph, numinput, edgeGraph[0].p1, edgeGraph[0].p2);
//go through edges, smallest to largest, if they are unique trees
//union them into the same tree
for(i=1; i<totalNumDist;i++) {
if(vertGraph[edgeGraph[i].p1].rep != vertGraph[edgeGraph[i].p2].rep) {
totalDist += edgeGraph[i].weight;
unionVert(vertGraph, numinput, vertGraph[edgeGraph[i].p1].rep, vertGraph[edgeGraph[i].p2].rep);
}
}
printf("\n%.2lf\n", totalDist);
}
void prim(int numinput, double graph[][2]) {
//initial check for <2 input
if(!numinput) {
printf("\nError: Number of inputs must be greater than 0");
return;
}
else if(numinput == 1) {
printf("\n0.00\n");
return;
}
//keeps track of inputs already used
int inMST[numinput];
double distances[numinput][numinput];
int i,j,key;
double first, second;
double total = 0;
int done = 0;
//first find distance between all points
//This is a slower version than kruskal's
//it repeats distances
for(i=0; i<numinput; i++) {
//set all inMST to 0
inMST[i] = 0;
for(j=0; j<numinput; j++) {
if(i==j)
distances[i][i] == INF;
else {
first = graph[i][0]-graph[j][0];
first = pow(first,2);
second = graph[i][1]-graph[j][1];
second = pow(second,2);
first += second;
distances[i][j]= sqrt(first);
}
}
}
//Assume that vertex 0 is the starting point
inMST[0] = 1;
int count = 1;
//waits until every dist has been checked
while(!done) {
//Num of vertices in MST
double minDist = INF;
int startVert = 0;
int endVert = 0;
//find the closest vertex not yet in MST
for(i=0; i < numinput; i++) {
if(inMST[i]) {
for(j=0; j < numinput; j++) {
if(i!=j && distances[i][j] < minDist && inMST[j] == 0) {
startVert = i;
endVert = j;
minDist = distances[i][j];
}
}
}
}
//found next vertex mark it off and add edge to total
inMST[endVert] = 1;
total += minDist;
distances[startVert][endVert] = INF;
distances[endVert][startVert] = INF;
count++;
if(count >= numinput)
done++;
}
printf("\n%.2lf\n", total);
}
Sunday, July 13, 2014
Minimum Spanning Tree in C
One of my projects in algorithms class was to create a MST in C. I was given 5 sample inputs with answers, and 5 without answers. I had to create the MST using two different algorithms: Prim and Kruskal. The complete folder with the tests and results can be downloaded here. I completed this project in about 5 days.
Java's RNG
Lately I've been making small Java programs to refresh my skills. I've been using C and Ruby this last semester for the more complicated programs (I'll post those soon), but I'd like to get to the point where I'm comfortable doing them in Java.
Today's program is a simple dice roll program that tests the proficiency of java.util.random. I got the idea from /r/dailyprogrammer.
Results:
The results were as expected. Java.util.Random did not favor any number in particular as the number of rolls increased. A few things I learned while doing this:
Today's program is a simple dice roll program that tests the proficiency of java.util.random. I got the idea from /r/dailyprogrammer.
1: /*
2: Name: Kevin Achenbach
3: Date: 7/12/2014
4: Project: test a RNG to see how random it actually is. Use 6 sided dice as the test
5: */
6: package dice;
7: import java.util.Random;
8: public class Dice {
9: static int diceRolls[] = {10,100,1000,10000,100000,1000000};
10: public static void main(String[] args) {
11: System.out.print("# of Rolls 1s 2s 3s 4s 5s 6s\n");
12: System.out.print("====================================================\n");
13: for(int i = 0; i< diceRolls.length; i++) {
14: System.out.format("%-11d", diceRolls[i]);
15: float percent[] = rollDice(6,diceRolls[i]);
16: //Display results
17: for(int j = 1; j<percent.length;j++) {
18: percent[j] = percent[j]*100;
19: String str = String.format("%2.02f", percent[j]);
20: System.out.print(str + "% ");
21: }
22: System.out.print("\n");
23: }
24: }
25: static float[] rollDice(int arraySize ,int numberOfRolls) {
26: //can assume the all array values are zero at initialization
27: int testData[] = new int[arraySize+1];
28: Random rand = new Random();
29: int x;
30: float percent[] = new float[arraySize+1];
31: for(int i = 0; i<numberOfRolls; i++) {
32: x = rand.nextInt(6)+1;
33: testData[x]++;
34: }
35: for(int j = 0; j<arraySize+1;j++) {
36: percent[j] = ((float)testData[j])/numberOfRolls;
37: }
38: return percent;
39: }
40: }
Results:
The results were as expected. Java.util.Random did not favor any number in particular as the number of rolls increased. A few things I learned while doing this:
- line 36: converting two ints to a float by dividing is a bit tricky. The conversion to a float happens after the division occurs. This means that two integers dividing into a percentage will always come out as 0.0 unless the percentage is 100%. To avoid this cast the numerator as a float before dividing.
- Java.util.Random is INCREDIBLY quick. I ran the nextInt method over a million times yet the total run time was still under a second.
Subscribe to:
Posts (Atom)