Algo1.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>

using namespace std;

// Define a structure for a point (object)
struct Point {
    double x;
    double y;
};

// Function to calculate distance between two points
double calculateDistance(const Point& p1, const Point& p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

// Function to calculate clustering factor
double calculateClusteringFactor(double distanceMean, double distanceVariance) {
    return 1 / (distanceMean + 0.5 * distanceVariance);
}

// Function to perform cluster setup
// K is optimal number of clusters
vector<vector<Point>> clusterSetup(const vector<Point>& objects, int k) {
    vector<vector<Point>> clusters;
    for (const auto& obj : objects) {
        clusters.push_back({obj}); // Each object constitutes an initial cluster
    }
    
    int kPrime = clusters.size();
    
    while (kPrime > k) {
        double maxClusteringFactor = -1;
        pair<int, int> mergeIndices;
        
        for (int i = 0; i < kPrime; ++i) {
            for (int j = i+1; j < kPrime; ++j) {
                if (i != j) {
                    vector<double> distanceSet;
                    for (const auto& p1 : clusters[i]) {
                        for (const auto& p2 : clusters[j]) {
                            distanceSet.push_back(calculateDistance(p1, p2));
                        }
                    }

                    double distanceMean = 0;
                    for(int i=0; i<distanceSet.size(); i++){
                        distanceMean = distanceMean + distanceSet[i];
                    }
                    distanceMean = distanceMean / distanceSet.size();

                    double distanceVariance = 0;
                    for (const auto& distance : distanceSet) {
                        distanceVariance += pow(distance - distanceMean, 2);
                    }
                    distanceVariance /= distanceSet.size();

                    double clusteringFactor = calculateClusteringFactor(distanceMean, distanceVariance);
                    
                    if (clusteringFactor > maxClusteringFactor) {
                        maxClusteringFactor = clusteringFactor;
                        mergeIndices = {i, j};
                    }
                }
            }
        }
        
        if (maxClusteringFactor > -1) {
            clusters[mergeIndices.first].insert(clusters[mergeIndices.first].begin(), clusters[mergeIndices.second].begin(), clusters[mergeIndices.second].end());
            clusters.erase(clusters.begin() + mergeIndices.second);
            kPrime--;
        }
    }
    
    return clusters;
}

int main() {
    // Example usage:
    vector<Point> objects = {{1, 20}, {13, 4}, {5, 9}, {7, 8}, {19, 10}, {15,20}};

    // Define optimal number of clusters 
    int k = 2;

    vector<vector<Point>> result = clusterSetup(objects, k);
    
    // Print clusters
    for (const auto& cluster : result) {
        cout << "Cluster:";
        for (const auto& point : cluster) {
            cout << " (" << point.x << ", " << point.y << ")";
        }
        cout << endl;
    }
     return 0; 
}