Untitled

//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; 
}