Untitled
unknown
plain_text
2 months ago
5.5 kB
15
Indexable
//MST implementation + graphs #include <iostream> #include <vector> #include <algorithm> #include <map> #include <set> #include <cmath> #include <random> #include <cstring> #include <climits> using namespace std; // ~~~~~ Normal Graph with randomly chosen edge weights (0,1) ~~~~~~~ // graphs represented as an adjacency matrix vector<vector<pair<int, double>>> BuildZero(int n){ vector<vector<pair<int, double>>> graph(n); random_device rd; mt19937 gen(rd()); uniform_real_distribution<double> dist01(0.0, 1.0); for(int u = 0; u < n; u++){ for(int v = u+1; v < n; v++){ double w = dist01(gen); graph[u].push_back({v, w}); graph[v].push_back({u, w}); } } return graph; } //helper func bool isPowerOfTwo(long long x){ return x > 0 && (x & x-1 == 0); } vector<vector<pair<int, double>>> BuildOne(int n){ vector<vector<pair<int, double>>> graph(n); random_device rd; mt19937 gen(rd()); uniform_real_distribution<double> dist01(0.0, 1.0); for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ long long diff = (long long)j - (long long)i; if(isPowerOfTwo(diff)){ double w = dist01(gen); graph[i].push_back({j, w}); graph[j].push_back({i, w}); } } } return graph; } vector<vector<pair<int, double>>> BuildTwo(int n){ vector<vector<pair<int, double>>> graph(n); vector<vector<double>> coords(n, vector<double>(2, 0)); random_device rd; mt19937 gen(rd()); uniform_real_distribution<double> dist01(0.0, 1.0); for(int i = 0; i < n; i++){ for(int d = 0; d < 2; d++){ coords[i][d] = dist01(gen); } } for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ double sumsquared = 0.0; for(int d = 0; d < 2; d++){ double diff = coords[i][d] - coords[j][d]; sumsquared += diff*diff; } double dist = sqrt(sumsquared); graph[i].push_back({j, dist}); graph[j].push_back({i, dist}); } } return graph; } vector<vector<pair<int, double>>> BuildThree(int n){ vector<vector<pair<int, double>>> graph(n); vector<vector<double>> coords(n, vector<double>(3, 0)); random_device rd; mt19937 gen(rd()); uniform_real_distribution<double> dist01(0.0, 1.0); for(int i = 0; i < n; i++){ for(int d = 0; d < 3; d++){ coords[i][d] = dist01(gen); } } for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ double sumsquared = 0.0; for(int d = 0; d < 3; d++){ double diff = coords[i][d] - coords[j][d]; sumsquared += diff*diff; } double dist = sqrt(sumsquared); graph[i].push_back({j, dist}); graph[j].push_back({i, dist}); } } return graph; } vector<vector<pair<int, double>>> BuildFour(int n){ vector<vector<pair<int, double>>> graph(n); vector<vector<double>> coords(n, vector<double>(4, 0)); random_device rd; mt19937 gen(rd()); uniform_real_distribution<double> dist01(0.0, 1.0); for(int i = 0; i < n; i++){ for(int d = 0; d < 4; d++){ coords[i][d] = dist01(gen); } } for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ double sumsquared = 0.0; for(int d = 0; d < 4; d++){ double diff = coords[i][d] - coords[j][d]; sumsquared += diff*diff; } double dist = sqrt(sumsquared); graph[i].push_back({j, dist}); graph[j].push_back({i, dist}); } } return graph; } // Prim's MST -- returns weight of MST double MST(vector<vector<pair<int, double>>> graph, int n, int start=0){ vector<double> dist(n, INT64_MAX); vector<bool> inMST(n, false); double totalWeight = 0; dist[start] =0; for(int i = 0; i < n; i++){ double best = INT64_MAX; int u = -1; for(int v = 0; v < n; v++){ if(!inMST[v] && dist[v] < best){ best = dist[v]; u = v; } } inMST[u] = true; totalWeight += dist[u]; //cout << totalWeight << "\n"; for(int j = 0; j < graph[u].size(); j++){ int wnode = graph[u][j].first; double wcost = graph[u][j].second; if(!inMST[wnode] && wcost < dist[wnode]){ dist[wnode] = wcost; } } } return totalWeight; } int main(int argc, char* argv[]){ int nv = stoi(argv[2]); int nt = stoi(argv[3]); int dim = stoi(argv[4]); vector<vector<pair<int, double>>> graph; double trialSum = 0.0; for(int i = 0; i < nt; i++){ if(dim == 0){ graph = BuildZero(nv); } else if (dim == 1){ graph = BuildOne(nv); } else if (dim == 2){ graph = BuildTwo(nv); } else if (dim == 3){ graph = BuildThree(nv); } else if (dim == 4){ graph = BuildFour(nv); } double trial = MST(graph, nv); trialSum += trial; } double avg = 0.0; if(nt > 0){ avg = trialSum/nt; } cout << avg << " " << nv << " " << nt << " " << dim << "\n"; return 0; }
Editor is loading...
Leave a Comment