kargerAnalysis.R

library(ggplot2)

v <- c(20, 70, 80, 90, 100, 120, 140, 150, 170, 190, 200, 210, 230, 250, 260, 270, 290, 15, 25, 35, 55, 65, 85, 95, 125, 135, 155, 185, 205, 225, 245, 255, 265, 275, 20, 30, 40, 60, 80, 100, 110, 180, 200, 210, 230, 240, 250, 280, 290, 9, 25, 41, 57, 81, 89, 105, 113, 137, 145, 185, 201, 209, 233, 241)
karger <- c(0.015, 0.017, 0.012, 0.015, 0.016, 0.02, 0.02, 0.02, 0.022, 0.024, 0.029, 0.03, 0.042, 0.031, 0.029, 0.035, 0.036, 0.012, 0.005, 0.005, 0.006, 0.004, 0.009, 0.009, 0.01, 0.011, 0.014, 0.016, 0.015, 0.019, 0.023, 0.023, 0.025, 0.035, 0.006, 0.007, 0.004, 0.007, 0.008, 0.01, 0.01, 0.017, 0.014, 0.021, 0.02, 0.017, 0.021, 0.021, 0.024, 0.022, 0.009, 0.007, 0.005, 0.008, 0.008, 0.009, 0.007, 0.013, 0.015, 0.011, 0.016, 0.017, 0.028, 0.019)
mincut <- c(1.097, 4.097, 5.211, 6.708, 8.286, 12.943, 20.954, 22.949, 40.863, 68.052, 70.431, 81.572, 114.242, 168.426, 169.663, 194.038, 259.768, 0.223, 0.409, 0.302, 0.805, 1.171, 2.42, 2.902, 6.539, 8.843, 13.953, 27.056, 41.13, 58.119, 93.411, 109.786, 120.899, 145.65, 0.297, 0.619, 0.49, 1.128, 2.003, 3.348, 4.547, 25.228, 39.435, 46.196, 73.941, 91.122, 114.089, 171.047, 197.421, 0.077, 0.378, 0.363, 0.831, 2.128, 2.771, 3.753, 4.844, 9.241, 11.13, 26.953, 38.832, 45.703, 66.68, 92.011)
tmincut <- c(0.913, 3.604, 4.706, 6.145, 7.95, 13.962, 21.367, 22.722, 38.548, 49.649, 59.206, 65.365, 128.241, 132.488, 156.733, 180.355, 238.412, 0.118, 0.331, 0.242, 0.663, 1.003, 1.87, 2.127, 6.058, 8.291, 13.475, 26.616, 40.7, 57.499, 84.719, 97.859, 111.59, 127.336, 0.274, 0.354, 0.396, 0.691, 1.377, 2.816, 4.056, 24.779, 38.185, 44.715, 65.108, 77.064, 99.259, 154.667, 189.16, 0.088, 0.406, 0.311, 0.579, 1.285, 2.227, 3.326, 4.302, 8.71, 10.662, 27.696, 38.227, 45.367, 65.149, 78.457)
ks <- c(0.433, 2.689, 3.609, 4.785, 6.192, 10.442, 16.836, 19.139, 33.349, 45.444, 53.53, 60.985, 104.534, 122.044, 140.913, 159.389, 217.724, 0.105, 0.3, 0.188, 0.406, 0.606, 1.473, 1.85, 5.25, 7.163, 10.903, 23.547, 33.752, 53.438, 80.415, 90.852, 101.401, 124.918, 0.25, 0.202, 0.41, 0.553, 1.149, 2.313, 3.555, 22.414, 34.089, 41.557, 57.572, 69.008, 94.116, 147.691, 171.514, 0.068, 0.208, 0.27, 0.44, 1.1, 1.692, 2.875, 3.463, 7.059, 8.623, 23.868, 33.908, 40.402, 61.504, 69.268)
tks <- c(0.227, 1.925, 2.617, 3.399, 4.394, 7.361, 11.827, 15.146, 24.932, 33.665, 39.141, 44.375, 74.016, 84.297, 95.978, 109.451, 145.101, 0.053, 0.095, 0.078, 0.247, 0.381, 0.989, 1.296, 3.609, 4.99, 7.802, 16.512, 24.485, 39.938, 63.316, 73.961, 76.889, 93.997, 0.072, 0.052, 0.101, 0.287, 0.744, 1.531, 2.354, 15.3, 25.471, 32.945, 42.933, 49.989, 66.352, 102.537, 116.114, 0.055, 0.09, 0.106, 0.248, 0.732, 1.139, 1.97, 2.411, 4.99, 6.084, 16.865, 23.171, 29.596, 47.698, 50.709)
length(v)
length(ks)

library(ggplot2)
df <- data.frame(v, karger, mincut, tmincut, ks, tks)
ggplot(df, aes(v, xlab = "RunTime", ylab = "Number of Verticies"))+ggtitle("Runtime Analysis") +
  xlab("Verticies")+ylab("Runtime (in seconds)")+
  geom_point(aes(y = karger, col = "Karger")) + 
  geom_point(aes(y = mincut, col = "Min-Cut")) + 
  geom_point(aes(y = tmincut, col = "Threaded Min-Cut")) + 
  geom_point(aes(y = ks, col = "Karger-Stein")) + 
  geom_point(aes(y = tks, col = "Threaded Karger-Stein")) +
  geom_smooth(aes(y = karger), method = "lm", formula=y~x, fill = NA, size=0.5, color = "orange") +
  geom_smooth(aes(y = mincut), method="lm", se=TRUE, fill=NA, formula=y ~ poly(x, 2, raw=TRUE),size=0.5,colour="green") +
  geom_smooth(aes(y = tmincut), method="lm", se=TRUE, fill=NA, formula=y ~ poly(x, 2, raw=TRUE),size=0.5,colour="magenta1") +
  geom_smooth(aes(y = ks), method="lm", se=TRUE, fill=NA, formula=y ~ poly(x, 2, raw=TRUE),size=0.5,colour="yellow")+
  geom_smooth(aes(y = tks), method = "lm", formula=y~ poly(x, 2, raw=TRUE), fill = NA, size=0.5, color = "dodgerblue1")