#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <graph.h>

struct graphe{
  int ordre; /*l'ordre du graphe*/
  int** adj; /*la matrice d'adjacence, donnée par un double tableau dynamique*/
  int oriente; /*vaut 0 si le graphe est non orienté, 1 sinon*/
};

typedef struct graphe graphe;

struct file {
  	int data;
  	struct file* succ;
};

typedef struct file fifo;

fifo* enqueue(fifo **fi,int v){
  fifo *nf=malloc(sizeof(fifo));
  nf->data=v;
  nf->succ=*fi;
  return nf;
}

int dequeue(fifo **fi){
  fifo *lect=*fi;
  if(lect->succ==NULL){
    int res=lect->data;
    *fi=NULL;
    return res;
  }
  while(lect->succ->succ!=NULL){
    lect=lect->succ;
  }
  int res=lect->succ->data;
  fifo *temp=lect->succ;
  lect->succ=NULL;
  free(temp);
  return res;
}
int empty(fifo *fi){
  return fi==NULL;
}

void afficheFile(fifo *fi){
	fifo *affichage=malloc(sizeof(fifo));
	affichage=fi;
	while(affichage->succ!=NULL){
		printf("%hu ",affichage->data);
		affichage=affichage->succ;
	}free(affichage);
}

fifo* fileVoisins(graphe g,int v){
	fifo *res=malloc(sizeof(fifo));
	int i;
	for(i=0;i<g.ordre;i++){
		if(g.adj[i][v]==1){
			enqueue(&res,g.adj[i][v]);
		}
	} return res;
}

graphe creergraphe(int ord,int or){
	int i;
	int j;
	graphe NouvGraphe;
	NouvGraphe.ordre=ord;
	NouvGraphe.oriente=or;
	NouvGraphe.adj=calloc(ord,sizeof(int*));
	for (i=0;i<ord;i++){
		NouvGraphe.adj[i]=calloc(ord,sizeof(int));
	} for (i=0;i<ord;i++){
		for (j=0;j<ord;j++){
			NouvGraphe.adj[i][j]=0;
		}
	}
	return NouvGraphe;
}

void ajoutArete(graphe g,int v,int w){
	if (g.oriente==0){
		g.adj[v][w]=1;
		g.adj[w][v]=1;
	} else{
		g.adj[v][w]=1;
	}
}

void voisinage(graphe g,int s){
	int i;
	int voisin;
	if(g.oriente==0){
		printf("Les voisins du sommet %d sont:\n",s);
		for(i=0;i<g.ordre;i++){
			if(g.adj[i][s]==1){
				printf("%d\n",i);
				voisin=1;
			}
		} if(voisin!=1){
			printf("Il n'a pas de voisin.\n");
		}
	} else{
		printf("Les voisins entrants du sommet %d sont:\n",s);
		for(i=0;i<g.ordre;i++){
			if(g.adj[i][s]==1){
				printf("%d\n",i);
				voisin=1;
			}
		} if(voisin!=1){
			printf("Il n'en a pas.\n");
		} voisin=0;
		printf("Les voisins sortants du sommet %d sont:\n",s);
		for(i=0;i<g.ordre;i++){
			if(g.adj[s][i]==1){
				printf("%d\n",i);
				voisin=1;
			}
		} if(voisin!=1){
			printf("Il n'en a pas.\n");
		}
	}
}

int nbrVoisin(graphe g,int s){
	int i;
	int nbrVoisin=0;
	int nbrVoisinEntrant=0;
	int nbrVoisinSortant=0;
	if(g.oriente==0){
		for(i=0;i<g.ordre;i++){
			if(g.adj[i][s]==1){
				nbrVoisin++;
			}
		} printf("Le sommet %d possede %d voisin(s)\n",s,nbrVoisin);
		return nbrVoisin;
	} else{
		for(i=0;i<g.ordre;i++){
			if(g.adj[i][s]==1){
				nbrVoisinEntrant++;
			}
		} printf("Le sommet %d possede %d voisin(s) entrant(s)\n",s,nbrVoisinEntrant);
		for(i=0;i<g.ordre;i++){
			if(g.adj[s][i]==1){
				nbrVoisinSortant++;
			}
		} printf("Le sommet %d possede %d voisin(s) sortant(s)\n",s,nbrVoisinSortant);
	} return nbrVoisinSortant+nbrVoisinEntrant;
}

void afficherMatrice(int **m,int taille){
	int i;
	int j;
	putchar('\n');
	for (i=0;i<taille;i++){
		for (j=0;j<taille;j++){
			printf("%3d ",m[i][j]);
		} putchar('\n');
	}
}

void afficherAdjacence(graphe g){
	int i;
	int j;
	putchar('\n');
	for (i=0;i<g.ordre;i++){
		for (j=0;j<g.ordre;j++){
			printf("%3d ",g.adj[i][j]);
		} putchar('\n');
	}
}

int** multiplicationMatriceCarre(int **a,int **b,int taille){
	int** res=calloc(taille,sizeof(int*));
    int i,j,k;
  	for(i=0;i<taille;i++){
    	res[i]=calloc(taille,sizeof(int));
  	} for(i=0;i<taille;i++){
      	for(j=0;j<taille;j++){
    	    for(k=0;k<taille;k++){
      	    res[i][j]+=a[i][k]*b[k][j];
     	    }
        }
    } return res;
}

int** additionMatriceCarre(int **a,int **b,int taille){
	int** res=calloc(taille,sizeof(int*));
    int i,j,k;
  	for(i=0;i<taille;i++){
    	res[i]=calloc(taille,sizeof(int));
  	} for(i=0;i<taille;i++){
      	for(j=0;j<taille;j++){
    	    for(k=0;k<taille;k++){
      	    res[i][j]=a[i][k]+b[k][j];
     	    }
        }
    } return res;
}

int** nombreDeChemins(graphe g,int longueur){
	int** res=calloc(g.ordre,sizeof(int*));
    int i,j;
  	for(i=0;i<g.ordre;i++){
    	res[i]=calloc(g.ordre,sizeof(int));
  	} for (i=0;i<g.ordre;i++){
		for (j=0;j<g.ordre;j++){
			res[i][j]=g.adj[i][j];
		}
	} for (i=0;i<longueur-1;i++){
		res=multiplicationMatriceCarre(res,g.adj,g.ordre);
	} return res;
}

int estConnexe(graphe g){
	int v=1;
	int** res=calloc(g.ordre,sizeof(int*));
    int i,j;
  	for(i=0;i<g.ordre;i++){
    	res[i]=calloc(g.ordre,sizeof(int));
  	} for (i=0;i<g.ordre;i++){
  		res=additionMatriceCarre(res,(nombreDeChemins(g,i)),g.ordre);
	} for (i=0;i<g.ordre;i++){
		for (j=0;j<g.ordre;j++){
			if(res[i][j]==0){
				v=0;
				break;
			}
		}
	} return v;
}

int estEulerien(graphe g){
	int v=1;
	int i;
	int deg;
	if(estConnexe(g)){
		for(i=0;i<g.ordre;i++){
			deg=nbrVoisin(g,i);
			if(deg%2==1){
				v=0;
			}
		} return v;
	}else{
		return 0;
	}
}

void visuelGraphe(graphe g){
	#define M_PI 3.14159265358979323846
	int taille=1000;
    int origine=taille/2;
    int distance=4*origine/5;
    int tailleVert=taille/20;

	    InitialiserGraphique();
    CreerFenetre(10,10,taille,taille);

    int i,j;
    int x,y;
    char* nV=malloc(2);
    *nV='0';
    *(nV+1)='\0';
    int* cX=calloc(g.ordre,sizeof(int));
    int* cY=calloc(g.ordre,sizeof(int));
    for(i=0;i<g.ordre;i++){
    	x=(int) origine+distance*cos(2*M_PI*i/g.ordre);
    	y=(int) origine+distance*sin(2*M_PI*i/g.ordre);
    	cX[i]=x+tailleVert/2;
    	cY[i]=y+tailleVert/2;
    	RemplirArc(x,y,tailleVert,tailleVert,0,360); 
    	EcrireTexte(x,y,nV,2);
    	(*nV)++;

    }

    for(i=0;i<g.ordre;i++){
    	    for(j=0;j<g.ordre;j++){
    	    	if(g.adj[i][j]!=0){
    	    		DessinerSegment(cX[i],cY[i],cX[j],cY[j]);
    	    	}
    	    }
    	}
    Touche();
    FermerGraphique();
}