exp_1.c

//Exp 1 all parts 
//Author: KS [not to be shared till Mon evening!]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int NODE_COUNT=12;
int MAX_COST=99;
float Dg = 1.8;
#define SRAND 1
#define INF MAX_COST+1  //for init min_val

void print_mat(int mat[NODE_COUNT][NODE_COUNT], int row_sz, int col_sz);
void find_spanning_tree(int adj_mat[NODE_COUNT][NODE_COUNT], int mst_adj_mat[NODE_COUNT][NODE_COUNT], int row_sz, int col_sz);
void addLinks(int mst_adj_mat[NODE_COUNT][NODE_COUNT],int adj_mat2[NODE_COUNT][NODE_COUNT],int row_sz,int col_sz);
int *gen_N_rand_nos(int M, int N, int vektor[M]);


int main(int argc, char *argv[])
{
	if(argc>=2)
	{
		Dg = atof(argv[1]);
	}
	if(argc>=3) 
	{
		NODE_COUNT = atoi(argv[2]);
	}
	if(argc>=4)
	{
		MAX_COST = atoi(argv[3]);
	}
	//else if(argc>3) {printf("Too May Args!\n")};

	printf("[*]HELP: ./OUT density_grad node_count max_cost\n[*]Total Nodes:%d, Max Cost:%d, Density Grad:%f\n\n",NODE_COUNT,MAX_COST,Dg);
	int i=0, j=0;
	int adj_mat[NODE_COUNT][NODE_COUNT], mst_adj_mat[NODE_COUNT][NODE_COUNT], adj_mat2[NODE_COUNT][NODE_COUNT], mst_adj_mat2[NODE_COUNT][NODE_COUNT];
	int link_count = 0;
	link_count = Dg*(NODE_COUNT-1);
	if(SRAND) srand(time(0));

	for(i=0;i<NODE_COUNT;i++)
	{
		for(j=i;j<NODE_COUNT;j++)
		{
			if(i==j)
			{
				adj_mat[i][j] = 0;
				mst_adj_mat[i][j] = 0; mst_adj_mat[j][i] = 0;
				mst_adj_mat2[i][j] = 0; mst_adj_mat2[j][i] = 0;
			}
			else
			{
				adj_mat[i][j] = rand() % MAX_COST + 1;
				adj_mat[j][i] = adj_mat[i][j];
				mst_adj_mat[i][j] = 0; mst_adj_mat[j][i] = 0;
				mst_adj_mat2[i][j] = 0; mst_adj_mat2[j][i] = 0;
			}
				//printf("%d ",adj_mat[i][j]);
			}
		}

	printf("\n[+]Original Adjacent MAt:\n");
	print_mat(adj_mat,NODE_COUNT,NODE_COUNT);

	//memset(mst_adj_mat,0,sizeof(mst_adj_mat)); 	//to  initiliasie with 0
	//print_mat(mst_adj_mat,NODE_COUNT,NODE_COUNT);

	find_spanning_tree(adj_mat,mst_adj_mat,NODE_COUNT,NODE_COUNT);
	printf("\n[+]Actual MST:\n");
	print_mat(mst_adj_mat,NODE_COUNT,NODE_COUNT);

	addLinks(mst_adj_mat,adj_mat2,NODE_COUNT,NODE_COUNT);  //adds extra links radomly based on Dg
	printf("\n[+]After adding Links randomly...\n");
	print_mat(adj_mat2,NODE_COUNT,NODE_COUNT);

	find_spanning_tree(adj_mat2,mst_adj_mat2,NODE_COUNT,NODE_COUNT);
	printf("\n[+]Actual MST after modifying n/w:\n");
	print_mat(mst_adj_mat2,NODE_COUNT,NODE_COUNT);


	return 0;
}

void addLinks(int mst_adj_mat[NODE_COUNT][NODE_COUNT],int adj_mat2[NODE_COUNT][NODE_COUNT],int row_sz,int col_sz)
{
	int i=0,j=0, k=0, unconnected_node_index=0, free_selected_index=0, free_index=0;
	int th_no_of_links = 0, max_links=0, extra_links=0, mst_adj_curr_val=0;
	if(SRAND) srand(time(0));

	max_links = (NODE_COUNT*(NODE_COUNT-1))/2;
	th_no_of_links = (int) ceil(Dg*(NODE_COUNT-1)); //ceil or floor ??
	extra_links = th_no_of_links-NODE_COUNT;
	printf("\n[*]Theoretical no of links(based in Dg): %d, Max Possible Links: %d",th_no_of_links,max_links);

	if(th_no_of_links <= max_links && extra_links > 0)
	{
		printf("\n[*]Adding %d Links to MST Randomly...\n",th_no_of_links-NODE_COUNT);
		int rand_link_index_arr[extra_links];

		gen_N_rand_nos(extra_links,max_links-NODE_COUNT+1,rand_link_index_arr);  //extra 1 is for acyclic nature of MST

		for(i=0;i<NODE_COUNT;i++)
		{
			for(j=i;j<NODE_COUNT;j++)
			{
				mst_adj_curr_val = mst_adj_mat[i][j];

				if(mst_adj_curr_val!=0 || i==j)
				{
					adj_mat2[i][j] = mst_adj_curr_val;
				}
				else
				{
					if(free_index == rand_link_index_arr[free_selected_index])
					{
						adj_mat2[i][j] = rand() % MAX_COST +1;
						printf("[%d]Added a rand cost link:(%d,%d):%d \n",free_selected_index,i,j,adj_mat2[i][j]);
						free_selected_index++;
					}
					else
					{
						adj_mat2[i][j] = 0;   //means it will remain disconnected (but itwasn't init)
					}
					free_index++;
					
				}

				adj_mat2[j][i] = adj_mat2[i][j];
			}
		}
		printf("%d new links made! Expected was: %d.\n",free_selected_index,extra_links);

	}
	else
	{
		printf("\n\n[-]Theoretical No of links either Exceeds Max Possible or is LESS/Equal to Total no of NODES! Check Dg val....\n\n");
	}

	return;
}


void find_spanning_tree(int adj_mat[NODE_COUNT][NODE_COUNT], int mst_adj_mat[NODE_COUNT][NODE_COUNT], int row_sz, int col_sz)
{
	int i=0, j=0, min_val=0, node_in_MST=0, node_not_in_MST=0, mst_Length=1;
	int node_1=0, node_2=0, cost=0;
	int mstSet[NODE_COUNT], remSet[NODE_COUNT-1];

	for(i=1;i<NODE_COUNT;i++)
	{
		remSet[i] = i;
	}
	mstSet[0] = 0;

	printf("\nFinding Spanning Tree:\n");

	for(mst_Length=1;mst_Length<NODE_COUNT;mst_Length++)
	{
		min_val = INF;
		for(i=0;i<mst_Length;i++)
		{
			for(j=1;j<NODE_COUNT;j++)
			{
				cost = adj_mat[mstSet[i]][j];
				if(cost!=0 && remSet[j-1]!=-1)  //cost non-0 means connected & -1 means already in mstSet
				{
					if(cost<=min_val)
					{
						min_val = cost;
						node_1 = mstSet[i];
						node_2 = j;
					}
				}

				//printf("%d ",adj_mat[i][j]);
			}
		}
		mst_adj_mat[node_1][node_2] = min_val;
		mst_adj_mat[node_2][node_1] = min_val;
		mstSet[mst_Length] = node_2;
		remSet[node_2-1] = -1; 	//like deleting this element
	}

	return;
}

int *gen_N_rand_nos(int M, int N, int vektor[M])
{
    int in=0,im=0;
    srand(time(0));

    for (in = 0; in < N && im < M; ++in) {
      int rn = N - in;
      int rm = M - im;
      if (rand() % rn < rm)
        /* Take it */
        vektor[im++] = in; /* +1 since your range begins from 1 */
    }

    /*printf("\n");
    for(im=0;im<M;im++)
    {
        printf("%d ",vektor[im]);
    }
    printf("\n");*/

    return vektor;
}


void print_mat(int mat[NODE_COUNT][NODE_COUNT], int row_sz, int col_sz)
{
	int i=0, j=0;

	//printf("\nGiven Matrix:\n");
	for(i=0;i<row_sz;i++)
	{
		for(j=0;j<col_sz;j++)
		{
			printf("%d  ",mat[i][j]);
		}
		printf("\n");
	}

	return;
}