source_code.cpp

/*
we are using kruskal's algorithm to generate the minimum spanning tree.
the graph is a complete graph
all the edges in the graph are sorted in an increasing order
the first 2 edges are added to the minimum spanning tree graph G, as 2 edges cant form a cycle
for the third edge, we apply bfs on the two vertices of the edge (and the graph is G), if a path is found that means a cycle will exist, hence we move on to the next edge
we do this until r-1 edges are added to g   (r is the total number of points we have taken)
hence a minimum spanning tree is formed
*/
#include <iostream>
#include <cmath>
#include<time.h>
#define r 15    //r = total number of points
#define pos 105  //pos = total number of possible edges in the complete graph
using namespace std;
int rear[r+2] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};  //after an edge enters the mst,the adjacency list of the vertices of the edge needs to be updated
int head[r+2] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};  //therefore for 15 vertices there will be 15 queues, storing the neighbour vertices
int MAX = 5000;
int queue_bsf[500];//temporary array thats stores the neighbours of a vertex v in the mst graph (required during breadth first searching;
class node{
public:
    int x;    //stores the coordinates of the point
    int y;  //to make the coding implementation easier, each 2-D coordinate is indexed to a number between 0 and 14, and we refer to the coordinates with this index
};

struct points {
    int coord_1;   //this stores the indices of the vertices of the edges and also the weight of the edge , which is the eucledian distance
    int coord_2;
    double weight;
};

struct neighbours {
    int neigh[r-1]; //each indexed coordinate has its adjacency list, this struct stores the adjacency list of the indexed vertex
};                  //the graph is the mst graph

struct mst{
    struct points p[r-1]; // mst struct which stores the details about the edges, coordinates, weights of the minimum spanning tree graph
};


void swap(struct points *p1, struct points *p2);
void equate(struct points *p1, struct points *p2);
void enqueue(int, int[], int);  //functions on queues
int dequeue(int[], int);
int delete_element(int[], int, int, int);
double euclid(node node1, node node2); //finding the weight of the edge

int bfs(struct neighbours n[], int, int);   //checks whether a path between two points is possible given the adjacency lists
void clustering_1(mst m, neighbours n[], int); //clustering based on the given menu
void clustering_2(mst m, neighbours n[], double);

struct points edges[pos];   // declaring the object of the struct
struct neighbours neighbour[r-1];
struct mst mt;
struct mst form_mst(struct points p1[], struct neighbours n[], struct mst m);



int main() {

    struct mst temp;       //we are generating 15 2-D coordinates from 3 clusters
    srand(time(0));
    int num_ver = 15;

    node nodes[num_ver];

    for (int i = 0; i < num_ver; i++)
    {
        if (i < 5)
        {
            nodes[i].x=rand()%20;
            nodes[i].y=rand()%20;
        }
        else if ((i >= 5) && (i < 10))
        {
            nodes[i].x=(30+rand()%20);
            nodes[i].y=(30+rand()%20);
        }
        else
        {
            nodes[i].x=(60+rand()%20);
            nodes[i].y=(60+rand()%20);
        }
    }

    int no_edges = 0;
    for (int i = 0; i < r; i++)   //updating the details regarding the coordinates and weights of edges
    {
        for (int j = i+1; j < r; j++)
        {
            edges[no_edges].coord_1 = i;
            edges[no_edges].coord_2 = j;
            edges[no_edges].weight = euclid(nodes[i], nodes[j]);
            no_edges++;
        }
    }

    for (int i = 0; i < no_edges; i++)  //sorting the edge lengths in increasing order
    {
        for (int j = i-1; j >= 0; j--)
        {
            if (edges[j].weight >= edges[j+1].weight)
            {
                swap(&edges[j], &edges[j+1]);
            }
        }
    }

    for (int i = 0 ; i < r; i++)  //printing the coordinates to get an idea of the index of each coordinate
    {
        cout << "coord[" << i << "] = (" << nodes[i].x << ", " << nodes[i].y << ")" << endl;
    }

    cout << endl;
    cout << "Edges in the MST generated by the above 15 Coordinates: " << endl;
    cout << endl;

    temp = form_mst(edges,neighbour,mt); //generating the mst

    cout << endl << endl;
    cout << "Choose any given option for criteria of termination" << endl << endl;
    cout << "1 -> Number of pre-determined clusters" << endl;
    cout << "2 -> Setting a minimum threshold below which edges will not be removed to make new clusters" << endl;
    cout << "3 -> Thresholded by average distance within clusters" << endl;

    int input;
    cin >> input;
    switch (input)
    {
        case 1:
            int pre_k;
            cout << "Choose the number of pre-determined clusters: ";
            cin >> pre_k;
            if (pre_k >= 15) {
                throw runtime_error ("Error: Maximum number of points are 15");
            }
            clustering_1(temp, neighbour, pre_k-1);
            break;

        case 2:
            clustering_2(temp, neighbour, 10.00);
            break;

        case 3:
            //            Threshold_distance();
            break;

        default:
            break;
    }

    return 0;
}


struct mst form_mst(struct points p1[], struct neighbours n[], struct mst m)
{
    int k = r-2;  //the edge with the largest weight in the mst is stored first, this helps while clustering

    for (int i = 0 ; i < pos; i++)
    {
        if(k < 0) //we stop when the total number of edges added becomes 14 (r-1)
        {
            break;
        }
        else
        {
            if (i == 0 || i ==1)
            {
                enqueue(p1[i].coord_2, n[p1[i].coord_1].neigh, p1[i].coord_1);  //first 2 edges are directly added
                enqueue(p1[i].coord_1, n[p1[i].coord_2].neigh, p1[i].coord_2);  //updating the adjacency list
                equate(&p1[i], &m.p[k]);
                k--;
            }
            else
            {
                if (bfs(n, p1[i].coord_1, p1[i].coord_2) == 0)   //if no path is found between the 2 points, they are added to the mst
                {
                    enqueue(p1[i].coord_2, n[p1[i].coord_1].neigh, p1[i].coord_1); //the 2 new points added are neighbours, hence we update the adjacency list
                    enqueue(p1[i].coord_1, n[p1[i].coord_2].neigh, p1[i].coord_2);
                    equate(&p1[i], &m.p[k]);
                    k--;
                }
            }
        }
    }

    for (int i = 0 ; i < r-1; i++)  //printing the mst graph
    {
        {
            cout << m.p[i].coord_1 << " - " << m.p[i].coord_2 << " -- " << m.p[i].weight << endl;
        }
    }
    return m;
}

//queue functions
void enqueue(int item, int queue_array[], int i)
{
    if (rear[i] == MAX-1)
    {
        cout << "Queue Overflow" << endl;
    }
    else
    {
        if (head[i] == -1)
        {
            head[i] = 0;

        }
        rear[i] = rear[i]+1;
        queue_array[rear[i]] = item;
    }
}


int dequeue(int queue_array[], int i)
{
    if(head[i] == -1 || head[i] > rear[i])
    {
        printf("Queue Underflow \n");
    }
    if(head[i]!=-1)
    {
        int k = queue_array[head[i]];
        head[i] = head[i]+1 ;
        return k;
    }
    return -1;
}


int delete_element(int arr[], int n, int x,int s)
{
    int i;
    for (i=0; i<n; i++)
        if (arr[i] == x)
            break;
    if (i < n)
    {
        n = n - 1;
        for (int j=i; j<n; j++)
            arr[j] = arr[j+1];
    }
    rear[s]=rear[s]-1;

    return n;
}


void equate(struct points *p1, struct points *p2)
{
    *p2 = *p1;
}


int bfs(struct neighbours n[], int coord_1, int coord_2) //n[] is the neighbours of vertices in the mst graph
{
    if(head[coord_1]!=-1)
    {int temp = coord_1;
        int dist[r];
        for (int i = 0 ; i<r;i++)
        {
            dist[i]=989; //initializing it to 989 implies this vertex hasnt been visited,989 was randomly chosen as no visited vertex can have this value
        }
        int v=0;
        enqueue(temp,queue_bsf,r);  //temporary array that decides the queue of vertices we are going to visit in the mst graph
        while(head[r]<=rear[r] && head[r]!=-1)
        {

            v = dequeue(queue_bsf,r);
            int i = 0;
            int j;
            int temp_1[50]; //temporary array that stores the neighbours of v in the mst graph G
            int l =0;
            while(l<=rear[v])
            {
                enqueue(n[v].neigh[l],temp_1,r+1);
                l++;
            }

            while(i<l)
            {

                j = dequeue(temp_1,r+1);
                dist[v]=v; //updating the dist[v], essentially marking it as visited
                if(dist[j]!=j) //visiting the unvisited vertex
                {enqueue(j,queue_bsf,r);
                    temp = j;}
                i++;
            }


        }
        head[r]=-1;  //since temp_1, queue_bsf are temporary arrays, they keep on changing for every different cooridinate
        head[r+1]=-1;  //therefore initializing it to its original value for a new edge
        rear[r]=-1;
        rear[r+1]=-1;
        if (dist[coord_2]==989)
        {
            return 0; //means the coordinate is unvisited, no path was found
        }
        else
        {

            return 1;//path was found

        }

    }
    else
        return 0; //if the vertex has no neighbours, then no path is possible

}

/*
for clustering_1: we want to generate k+1 clusters, we remove the first k largest edges, and this leads to the formation of k+1 clusters
*/
/*
for generating the clusters, we delete the edge we want to remove from the mst graph and update the adjacency lists of the points
we breadth first search every point to every point, if a path is found it means they are connected, thus form a cluster
if no path is found they are in different clusters
*/
void clustering_1(mst m,neighbours n[],int k)  //k is the number of edges to be removed
{
    if (k == 0) {
        cout << "The MST itself is a cluster" << endl;
        exit(0);
    }

    int temp_k = k;
    int j =0;
    int a_temp_coord_1[k]; //stores vertex_1 of the edge being removed
    int a_temp_coord_2[k]; //stores vertex_2 of the edge being removed
    while(k>0)
    {
        a_temp_coord_1[j]=m.p[j].coord_1;
        a_temp_coord_2[j]=m.p[j].coord_2;

        delete_element(n[a_temp_coord_1[j]].neigh,rear[a_temp_coord_1[j]],a_temp_coord_2[j],a_temp_coord_1[j]); //we delete vertex_2 from vertex_1's adjacency list as we are removing that edge in the mst
        delete_element(n[a_temp_coord_2[j]].neigh,rear[a_temp_coord_2[j]],a_temp_coord_1[j],a_temp_coord_2[j]);//we do the same for vertex_2's adjaceny list
        if(rear[a_temp_coord_1[j]]==-1)
        {
            enqueue(a_temp_coord_1[j],n[a_temp_coord_1[j]].neigh,a_temp_coord_1[j]); //every point is its own neighbour, adding that to the adjacency list
        }
        if(rear[a_temp_coord_2[j]]==-1)
        {
            enqueue(a_temp_coord_2[j],n[a_temp_coord_2[j]].neigh,a_temp_coord_2[j]);
        }
        k--;
        j++;
    }
    int j_1 = j;
    int j_2 =j;
    //the sets of points in a_temp_coord_1 , a_temp_coord_2 can have points that are connected to each other, hence to avoid repitition of cluster, we remove the such points
    for (int i =0; i<j_1;i++)
    {
        for (int k = i+1;k<j_1;k++)
        {
            if(a_temp_coord_1[i]==a_temp_coord_1[k])
            {
                for(int f=k;f<j_1;f++)
                {
                    a_temp_coord_1[f]=a_temp_coord_1[f+1];
                }
                j_1--;
            }
            if (bfs(n, a_temp_coord_1[i], a_temp_coord_1[k]) == 1) {
                for(int f=k;f<j_1;f++)
                {
                    a_temp_coord_1[f]=a_temp_coord_1[f+1];
                }
                j_1--;
            }
        }
    }
    for (int i =0; i<j_2;i++)
    {
        for (int k = i+1;k<j_2;k++)
        {
            if(a_temp_coord_2[i]==a_temp_coord_2[k])
            {
                for(int f=k;f<j_2;f++)
                {
                    a_temp_coord_2[f]=a_temp_coord_2[f+1];
                }
                j_2--;
            }
            if (bfs(n, a_temp_coord_2[i], a_temp_coord_2[k]) == 1) {
                for(int f=k;f<j_2;f++)
                {
                    a_temp_coord_2[f]=a_temp_coord_2[f+1];
                }
                j_2--;
            }
        }
    }
    for (int i =0; i<j_1;i++)
    {
        for(int k=0; k<j_2;k++)
        {
            if(a_temp_coord_1[i]==a_temp_coord_2[k])
            {
                for(int f=k;f<j_2;f++)
                {
                    a_temp_coord_2[f]=a_temp_coord_2[f+1];
                }
                j_2--;
            }

            if (bfs(n, a_temp_coord_1[i], a_temp_coord_2[k]) == 1) {
                for(int f=k;f<j_2;f++)
                {
                    a_temp_coord_2[f]=a_temp_coord_2[f+1];
                }
                j_2--;

            }
        }
    }
//printing the clusters
    for (int h = 0 ; h<j_1;h++)
    {
        for (int i =0; i<r;i++)
        {
            if(bfs(n,a_temp_coord_1[h],i)==1)
            {
                printf("cluster %d of %d is: %d\n",h+1,a_temp_coord_1[h],i);
            }
        }
    }
    for (int h = 0; h < (temp_k-j_1+1); h++)
    {
        for (int i =0; i<r;i++)
        {
            if(bfs(n,a_temp_coord_2[h],i)==1)
            {
                printf("cluster %d of %d is: %d\n",h+j_1+1,a_temp_coord_2[h],i);
            }
        }
    }



}
/*
we set a threshold, all the edges of weight larger than the threshold are removed
*/
/*
generating the clusters uses the same algorithm as clustering_1
*/
void clustering_2 (mst m, neighbours n[], double k) {
    int j = 0;
    int temp_k=0;
    int a_temp_coord_1[16];
    for (int i = 0; i < 16; i++) {
        a_temp_coord_1[i] = -1;
    }
    int a_temp_coord_2[16];
    for (int i = 0; i < 16; i++) {
        a_temp_coord_2[i] = -1;
    }

    while (m.p[j].weight >= k && j < 16) {
        a_temp_coord_1[j]=m.p[j].coord_1;
        a_temp_coord_2[j]=m.p[j].coord_2;

        delete_element(n[a_temp_coord_1[j]].neigh,rear[a_temp_coord_1[j]],a_temp_coord_2[j],a_temp_coord_1[j]);
        delete_element(n[a_temp_coord_2[j]].neigh,rear[a_temp_coord_2[j]],a_temp_coord_1[j],a_temp_coord_2[j]);
        if(rear[a_temp_coord_1[j]]==-1)
        {
            enqueue(a_temp_coord_1[j],n[a_temp_coord_1[j]].neigh,a_temp_coord_1[j]);
        }
        if(rear[a_temp_coord_2[j]]==-1)
        {
            enqueue(a_temp_coord_2[j],n[a_temp_coord_2[j]].neigh,a_temp_coord_2[j]);
        }
        temp_k++;
        j++;
    }
    if(temp_k!=0)
    { int j_1 = j;
        int j_2 = j;
        for (int i =0; i<j_1;i++)
        {
            for (int k = i+1;k<j_1;k++)
            {
                if(a_temp_coord_1[i]==a_temp_coord_1[k])
                {
                    for(int f=k;f<j_1;f++)
                    {
                        a_temp_coord_1[f]=a_temp_coord_1[f+1];
                    }
                    j_1--;
                }
                if (bfs(n, a_temp_coord_1[i], a_temp_coord_1[k]) == 1) {
                    for(int f=k;f<j_1;f++)
                    {
                        a_temp_coord_1[f]=a_temp_coord_1[f+1];
                    }
                    j_1--;
                }
            }
        }
        for (int i =0; i<j_2;i++)
        {
            for (int k = i+1;k<j_2;k++)
            {
                if(a_temp_coord_2[i]==a_temp_coord_2[k])
                {
                    for(int f=k;f<j_2;f++)
                    {
                        a_temp_coord_2[f]=a_temp_coord_2[f+1];
                    }
                    j_2--;
                }
                if (bfs(n, a_temp_coord_2[i], a_temp_coord_2[k]) == 1) {
                    for(int f=k;f<j_2;f++)
                    {
                        a_temp_coord_2[f]=a_temp_coord_2[f+1];
                    }
                    j_2--;
                }
            }
        }
        for (int i =0; i<j_1;i++)
        {
            for(int k=0; k<j_2;k++)
            {
                if(a_temp_coord_1[i]==a_temp_coord_2[k])
                {
                    for(int f=k;f<j_2;f++)
                    {
                        a_temp_coord_2[f]=a_temp_coord_2[f+1];
                    }
                    j_2--;
                }

                if (bfs(n, a_temp_coord_1[i], a_temp_coord_2[k]) == 1) {
                    for(int f=k;f<j_2;f++)
                    {
                        a_temp_coord_2[f]=a_temp_coord_2[f+1];
                    }
                    j_2--;

                }
            }
        }

        //    cout<<j_1<<"J_1"<<endl;
        //    cout<<j_2<<"J_2"<<endl;
        for (int h = 0 ; h<j_1;h++)
        {
            for (int i =0; i<r;i++)
            {
                if(bfs(n,a_temp_coord_1[h],i)==1)
                {
                    printf("coord_1 cluster %d of %d is: %d\n",h+1,a_temp_coord_1[h],i);
                }
            }
        }
        for (int h = 0; h < temp_k-j_1+1; h++)  //since we know the no.of edges being removed, the total number of clusters is fixed
        {
            for (int i =0; i<r;i++)
            {
                if(bfs(n,a_temp_coord_2[h],i)==1)
                {
                    printf("coord_2 cluster %d of %d is: %d\n",h+j_1+1,a_temp_coord_2[h],i);
                }
            }
        }

    }
    else
    {
        printf("the mst is the only cluster\n");
    }


}


void swap (struct points *p1, struct points *p2)
{
    struct points temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

double euclid (node node1, node node2) {
    int temp_x;
    int temp_y;
    double dist;
    temp_x = pow(abs(node1.x - node2.x), 2);
    temp_y = pow(abs(node1.y - node2.y), 2);
    dist = sqrt(temp_x + temp_y);
    return dist;
}