#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <sys/types.h>

// #include <iostream.h>
// #include <iomanip.h>
#include <time.h>     // for seconds()

#define MaxDim  100
#define Rand_Max  100000

// Prototypes

void seedRandom(unsigned int );     
double randomn(void );
double seconds(void );
double randshannon ( void );

void gera_grafo(int , double);     
void gera_grafo_sim(int , double);     
void print_grafo(int );     
void print_listas(int );     
void constroi_lista(int );     
void alcance(int, int);
void print_alcance(void);
void init_buscaP(void);
void buscaP(int );
void print_alc_buscaP(int );
void FordBellman(int );
void Dijkstra(int );

// Variáveis Globais

int MAdj[MaxDim][MaxDim];
int Dist[MaxDim][MaxDim];

int LisAdjP[MaxDim][MaxDim];
int LisAdjN[MaxDim][MaxDim];
int CardP[MaxDim];
int CardN[MaxDim];
int Q[MaxDim];
int mark[MaxDim];
int M_arcos; // Numero de Arcos no Grafo
int I_arco[MaxDim*MaxDim]; //  I_arco[k] Inicio(Origem) do Arco k
int J_arco[MaxDim*MaxDim]; //  J_arco[k] Fim(Destino) do Arco k

int Hq, Tq;
int Dim;

int DistInfinita;
long int I_SEED = 123456789;

// Programa Principal

int main()
{
	int v,a;
	float  faux;
	double dens;

	printf(" Digite o numero de vertices no grafo: ");
	scanf("%d", &Dim);

	printf(" Digite a densidade o grafo: ");
	scanf("%f", &faux);

	dens = faux;


	// Geração do Grafo

	gera_grafo(Dim, dens);

	constroi_lista (Dim);

	// Imprime Grafo

	print_grafo(Dim);


	printf("Tecle <enter>");
	getch();

	print_listas(Dim);

	printf("Digite o numero do vertice (inicial) para saber seu alcance: ");
	scanf("%d",&v);

	//printf("Digite o numero maximo de arestas: ");
	//scanf("%d",&a);

	a = Dim;

	alcance(v,a);
	print_alcance();

	getch();

    init_buscaP();
	buscaP(v);
	print_alc_buscaP(v);

	getch();
	printf(" Ford Bellman   \n");
	
	FordBellman(v);

	getch();
	printf(" Dijkstra   \n");
	
	Dijkstra(v);

	return(0);
}


// Algoritmo de Dijkstra para caminho mais curto de
// s  a todos os outros.
//
//  Só funciona se Dist[i][j] >= 0 para qualquer (i,j)
//
//  Este algoritmo sai da prova do teorema abaixo.
// 
//  Teo (k):  Sabe-se obter os k  vértices mais próximos de s, suas 
//            respectivas distâncias de s, o os seus respectivos
//            predecessores no cmc de s ao vértice.
//

void Dijkstra(int s)
{
	int v,w,k,l, vmin, dmin;   
	int d_temp[MaxDim];   // Estimativa pessimista da distância do cmc de s a v (d_temp[v])
	int pred[MaxDim];     // pred[v] é o predecessor de v no cmc de s a v
	int pos_prox[MaxDim]; // pos_prox[v] = k indica que v é o k-ésimo vértice mais próximo de s


    // Inicializacao: d_temp contem um estimativa pessimista
	// da distancia de s a v,  ao final d_temp[v] contém exatamente a
	// distância do cmc de s a v.

	for (v=1; v<=Dim; v++)
	{
		d_temp[v] = DistInfinita;
		pos_prox[v] = 0;
		pred[v] = -1;
	}

    // Caso Base - conhece-se o vértice mais próximo de s
	// (ele mesmo).

	d_temp[s] = 0;
	pred[s] = -1;


	// Passo Indutivo  T(1) =>  T(2)

	k = 1;
	pos_prox[s] = k;


	// Agora pode-se atualizar as estimativas pessimistas 
	// das distancias.
	
	for(l=1; l<=CardP[s]; l++)
	{
		v = LisAdjP[s][l];
		if (d_temp[v] > d_temp[s]+Dist[s][v])
		{
           d_temp[v] = d_temp[s]+Dist[s][v];
		   pred[v] = s;
		}
	}



	// Repetição dos passos indutivos

    for (k=2; k<=Dim; k++)
	{

       // Passo Indutivo  T(k-1) =>  T(k)
	   // Conhece-se os k vértices mais próximos de s
	   // Então conhece-se os k+1 vertices mais próximos de s

       //  O k-ésimo mais próximo é o que possui o menor d_temp

       //  Encontra o k-ésimo vértice mais próximo de s
	
	   vmin = 0;
	   dmin = DistInfinita+1;
       for (v=1; v<=Dim; v++)
	   {
		   if ((d_temp[v] < dmin) && (pos_prox[v] == 0))
		   {
               vmin = v;
               dmin = d_temp[v];
		   }
	   }

	   if(vmin == 0)
	   {
		   printf("\n ERROR !! No vertex found. %d \n", k);
		   return;
	   }

	   pos_prox[vmin] = k;

	  // Atualiza-se as estimativas pessimistas 
	  // das distancias.
	
   	  for(l=1; l<=CardP[vmin]; l++)
	  {
	 	 v = LisAdjP[vmin][l];
		 if (d_temp[v] > d_temp[vmin]+Dist[vmin][v])
		 {
            d_temp[v] = d_temp[vmin]+Dist[vmin][v];
		    pred[v] = vmin;
		 }
	  }

	}

	// Distancias e caminhos mais curtos

	printf(" DIJKSTRA -- CMC a partir de %d \n",s);
	for (v=1; v<=Dim; v++)
	{
		printf(" %d D=%d %d-esimo mais proximo Caminho: ",
			v, d_temp[v], pos_prox[v]);
		w = v;
		while (pred[w] > 0)
		{
			printf(" %d ",pred[w]);
			w = pred[w];
		}
		printf("\n");
	}

}


// Algoritmo de Ford Bellman para caminho mais curto
// do vértice s a todos os outros.
//
//   Este algoritmo encontra o cmc de s a v ou detecta que não
//   existe um tal caminho, pois existe um ciclo de comprimento
//   negativo.
//
//   O grafo pode ter arcos de comprimento negativo.
//
//  Este algoritmo sai da prova do teorema abaixo.
// 
//  Teo (k):  Sabe-se obter os cmc de s a todos os demais vértices que
//            utilizam k ou menos arcos.
//
//
//

void FordBellman(int s)
{
	int v,w,k, ll;
	int d_temp[MaxDim];
	int pred[MaxDim];

    // Inicializacao: Caso Base - conhece o CMC de s 
	// a todos os outros vertices utilizando no máximo ZERO
	// arcos.

	for (v=1; v<=Dim; v++)
	{
		d_temp[v] = DistInfinita;
		pred[v] = -1;
	}

	d_temp[s] = 0;
	pred[s] = 0;




	// Repetição dos passos indutivos

    for (k=1; k<= Dim - 1; k++)
	{

        // Passo Indutivo
	    // Conhece-se caminho mais curto de s a um vertice q utilizando
	    // no minimo k-1 arcos.
	    // Para obter o cmc de s a w utilizando no máximo k arcos,
	    // testa-se para cada arco no grafo se d_temp(v) + Dist[v][w]
	    // e' menor que d_temp[w], em caso afirmativo o atual cmc de
    	// s a w nao e' um cmc e portanto atualizamos d_temp[w] e pred[w]

		for(ll=1; ll<=M_arcos; ll++)
		{
			v = I_arco[ll];
			w = J_arco[ll];
			if( d_temp[ v ] +  Dist[v][w] < d_temp[w] )
			{
				d_temp[w] = d_temp[ v ] +  Dist[v][w];
				pred[w] = v;
			}
		}

	}


    //  Testa se tem circuito negativo


		for(ll=1; ll<=M_arcos; ll++)
		{
			v = I_arco[ll];
			w = J_arco[ll];
			if( d_temp[ v ] +  Dist[v][w] < d_temp[w] )
			{
            // Existe Circuito Negativo !!!!
		      printf(" CIRCUITO NEGATIVO !!!!!!\n\n ");
            return(1);
         }
		}


	// Distancias e caminhos mais curtos

	printf(" Ford Bellman -- CMC a partir de %d \n",s);
	for (v=1; v<=Dim; v++)
	{
		printf(" %d D=%d Caminho: ",v, d_temp[v]);
		w = v;
		while (pred[w] > 0)
		{
			printf(" %d ",pred[w]);
			w = pred[w];
		}
		printf("\n");
	}

}






// Print Alcance via busca em profundidade

void print_alc_buscaP(int v)
{
	int i;
		printf("\n Vertices alcancaveis a partir de %d \n",v);
	    
		for (i=1;i<=Dim;i++)
		{
			if( mark[i] == 1)
			{
				printf(" %d ",i);
			}
		}
		printf(" \n");
}

// INicializa busca em profundidade

void init_buscaP()
{
	int i;
		for (i=1;i<=Dim;i++)
		{
			mark[i] = 0;
		}
}

// Busca em Profundidade a partir da Origem do Alcance

void buscaP(int v)
{
	int w,i;

	if (mark[v] == 0)
	{
      printf(" %d\n", v);
		mark[v] = 1;
		for (i=1;i<=CardP[v];i++)
		{
			w=LisAdjP[v][i];
			buscaP(w);
		}
	}
}


// Imprime Alcance

void print_alcance(void){
	int i;
	printf("Os vertices atingidos sao:\n");
	for(i=1;i<=Tq;i++){
		printf(" %d ", Q[i]);
	}
	printf("\n");
}

//  Alcance

void alcance(int v, int n){
	int u,i,k,j,w,I,F;
	Q[1]=v;
	Hq=1;
	Tq=1;
	for(i=1;i<=n;i++) mark[i]=0;
	mark[v]=1;
	for(k=1;k<=n;k++){
		I=Hq;
		F=Tq;
		for (j=I;j<=F;j++){
			w=Q[j];
			for (i=1;i<=CardP[w];i++){
				u=LisAdjP[w][i];
				if (mark[u]==0){
					mark[u]=1;
					Q[++Tq]=u;
				}
			}
		}
		Hq=F+1;
	}
}


//  Gera Grafo
//
//            Grafo direcionado
//

void gera_grafo(int n, double dens)
{
	int i,j;

	M_arcos = 0;
	DistInfinita = 1;
	printf("\n\n Gerando Grafo Aleatório de Densidade: %f #Vertices: %d\n\n",dens,n);
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(randshannon() < dens)
			{
				M_arcos++;
				I_arco[M_arcos] = i;
				J_arco[M_arcos] = j;
				MAdj[i][j]=1;
				Dist[i][j]= (int)(randshannon() * 1000.);
		        DistInfinita += Dist[i][j];
			}
			else
			{
				MAdj[i][j]=0;
			}
			if (i == j)MAdj[i][j]=0;
		}
	}

	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if(MAdj[i][j]==0)
			{
				Dist[i][j]=DistInfinita;
			}
		}
	}

}

//
//  Gera Grafo Simetrico
//
//        Se o grafo é simétrico, pode ser visto como um grafo não-direcionado
//

void gera_grafo_sim(int n, double dens)
{
	int i,j;

	M_arcos = 0;
	DistInfinita = 1;
	printf("\n\n Gerando Grafo Aleatório de Densidade: %f #Vertices: %d\n\n",dens,n);
	for(i=1; i<=n; i++)
	{
		for(j=i; j<=n; j++)
		{
			if(randshannon() < dens)
			{
				M_arcos++;
				I_arco[M_arcos] = i;
				J_arco[M_arcos] = j;
				MAdj[i][j]=1;
				MAdj[j][i]=1;

				Dist[i][j]= (int)(randshannon() * 1000.);
				Dist[j][i]= Dist[i][j];

				DistInfinita += 2*Dist[i][j];
			}
			else
			{
				MAdj[i][j]=0;
				MAdj[j][i]=0;
			}
			if (i == j)
			{
				MAdj[i][j]=0;
				MAdj[j][i]=0;
			}
		}
	}

	for(i=1; i<=n; i++)
	{
		for(j=i; j<=n; j++)
		{
			if(MAdj[i][j]==0)
			{
				Dist[i][j]=DistInfinita;
				Dist[j][i]=DistInfinita;
			}
		}
	}

}


//  Print Grafo

void print_grafo(int n)
{
	int i,j;
	printf("\n GRAFO: Matriz de Adjacencia\n");
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			printf("%d:%d %d ",i,j,MAdj[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("\n GRAFO: Distancias dos Arcos (quando o arco nao existe a dist eh infinita)\n");
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			printf("%d:%d %d ",i,j,Dist[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}


// Constroi Lista de Adjacência

void  constroi_lista(int n)
{
	int i,j,p;

	for (i=1; i<=n; i++)
	{
		CardP[i] = 0;
		CardN[i] = 0;
	}

	for(i=1; i<=n; i++)
	{
		for(j=1; j<=n; j++)
		{
			if (MAdj[i][j] == 1)
			{
				p = CardP[i] + 1;
				LisAdjP[i][p] = j;
				CardP[i] = p;

				p = CardN[j] + 1;
				LisAdjN[j][p] = i;
				CardN[j] = p;
			}
		}
	}

}


// Print Listas

void print_listas(int n)
{
	int i,j, p, sum;
	sum = 0;
	printf("\n GRAFO: Listas de Adjacência\n");
	printf("\n  Listas de Saida de Arcos \n");
	for(i=1; i<=n; i++)
	{
		printf("%d | %d Arcos Saindo : ", i, CardP[i]);
		p = CardP[i];
		for(j=1; j<=p; j++)
		{
			printf(" %d ",LisAdjP[i][j]);
		}
		printf("\n");
	}
	printf("\n  Listas de Entrada de Arcos \n");
	for(i=1; i<=n; i++)
	{
		printf("%d | %d Arcos Chegando : ", i, CardN[i]);
		p = CardN[i];
		for(j=1; j<=p; j++)
		{
			printf(" %d ",LisAdjN[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}


// System dependent routines
// File: system.cpp


void seedRandom(unsigned int seed)
// seed for random number generator.
{
  srand(seed);
  return;   
}
	      
double randomn(void)
// random number between 0.0 and 1.0 (uncluded).
{
  double rrr;
  
  rrr = (double) rand() / (double) RAND_MAX;
  return rrr;
}
 
double seconds()
// cpu time in seconds since start of run.
{
  double secs;
   
  secs = (double)(clock() / 1000.0);
  return(secs);
}


// random number between 0.0 and 1.0  Shannon random number generator.
double randshannon ( void )
{
  double   random;
  long int i,j;

  I_SEED = 16807 * I_SEED;

  if (I_SEED < 0)
    {
      I_SEED += 2147483647;
    }

  i = I_SEED / 32767;
  j = I_SEED - i * 32767;

  random = j/32767.;

  /*  printf("%f\n",*random); */

  return (random);
}