#include <stdio.h>
#include <cstdlib>
#include <time.h>

int N = 40;//número de nós
int M = 4;//número de comunidades
int K = 16; //número médio de conexões
int node1, node2;//nós
float In, Out;
int conections = 0;//Número de conexões

main () {
	In = 0.9;//Probabilidade de conexao intracomunidade
	Out = 0.4;//Probabilidade de conexao intercomunidade

	//Declaração do vetor de excentricidade
	int excentricidade[N];

	//matriz de adjacência
	int MA[N][N];
	//Esvaziar matriz de adjacência
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			MA[i][j] = 0;

	srand(time(NULL)); //semente de números aleatórios

	while(conections < K * N) {
	   //Conexao intracomunidade
	   node1 = rand()%N;//sortear primeiro nó

	   //sorteia um novo nó até que os nós sejam da
	   //mesma comunidade e diferentes entre si
	   do
	   {
	      node2 = rand()%N;//sortear segundo nó
	   }while(node1/(N/M)!=node2/(N/M) || node1==node2);

	   //Conectar nós
	   if(rand()%100+1 <= In*100)
	   {
	      MA[node1][node2] = 1;
	      MA[node2][node1] = 1;
		  conections += 2;
		}

		//Conexao intercomunidade
	   node1 = rand()%N;//sortear primeiro nó

	   //sorteia um novo nó até que os nós sejam de
	   //comunidade diferentes
	   do
	   {
	      node2 = rand()%N;//sortear segundo nó
	   }while(node1/(N/M) == node2/(N/M));

	   //Conectar nós
	   if(rand()%100+1 <= Out*100)
	   {
	      MA[node1][node2] = 1;
	      MA[node2][node1] = 1;
		  conections += 2;
		}
	}

	//Exibir matriz de adjacência
	for(int i = 0; i < N; i++)
	{
      for(int j = 0; j < N; j++)
	  {
	    printf("%d ",MA[i][j]);
	  }
	  printf("\n");
	}


	int distance[N][N];

	for(int i = 0; i < N; i++)
	   for(int j = 0; j < N; j++)
	     if(MA[i][j] == 1)
		   distance[i][j] = 1;
		else
		   distance[i][j] = -1;

	for(int i = 0; i < N; i++)
	   distance[i][i] = 0;

	for(int k = 0; k < N; k++)
	   for(int i = 0; i < N; i++)
	      for(int j = 0; j < N; j++)
	         if((distance[i][j] > distance[i][k] + distance[k][j] ||
	           distance[i][j] == -1) &&
			   distance[i][k] > 0 &&
			   distance[k][j] > 0 )
			   distance[i][j] = distance[i][k] + distance[k][j];

	//Exibir matriz de distância
	for(int i = 0; i < N; i++)
	{
      for(int j = 0; j < N; j++)
	  {
	    printf("%d ",distance[i][j]);
	  }
	  printf("\n");
	}


}

void encontrarExcentricidade(){
	for(int i = 0; i < N; i++) {

		excentricidade[i] = 0;
	}

	printf("Excentricidade:\n");

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if(excentricidade[i] < distance[i][j])
				excentricidade[i] = distance[i][j];
		}
	   printf("%d ", excentricidade[i]);
	}
}

//Encontrar raio de cada nó

int calculoRaio(int excentricidade[]) {

	int raio = excentricidade[0];


	for(int i=0; i < N; i++){

	   if(excentricidade[i] < raio)
	      raio = excentricidade[i];
	}

	return raio;

}

//Encontrar diâmetro de cada nó

int calculoDiametro(int excentricidade[]){

	int diametro = excentricidade[0];

	for(int i = 0; i < N; i++){

		if(excentricidade[i] > diametro)
			diametro = excentricidade[i];
	}

	return diametro;
}