/* Ce programme doit servir à traduire une représentation d'un graphe selon
l'une des trois représentations ci-dessous :
	- matrice d'adjacence
	- listes chaînées des "fils"
	- listes chaînées des "pères"
en l'une quelconque des autres représentations.
Le graphe sera construit de façon aléatoire en définissant la matrice d'adjacence, chaque arc
ayant la probabilité 1/2 d'exister.
On pourra choisir entre les différentes traductions possibles ; un affichage de vérification
sera effectué. Le choix sera reproposé jusqu'à ce que l'utilisateur demande de quitter.
Au départ, seules les traductions à partir de la matrice d'adjacence seront proposées.

	Le programme principal a été écit pour vous. Il utilse en particulier :
- la fontion time
	dont le prototype, qui se trouve dans time.h, est :
		time_t time(time_t *);
	time_t est un type entier.
	Quand on exécute la fonction time_t, la valeur retournée est l'heure calendaire
	avec une précision correspondant aux secondes. La valeur pointée par le paramètre
	devient aussi l'heure calendaire.
- La fonction srand dont le prototype, qui se trouve dans stdlib.h, est :
		void srand(unsigned int);
	Cette fonction est en général utilisée une seule fois pour "initialiser" le "générateur
	aléatoire de nombre entiers constitué par la fonction rand décrite ci_dessous. Si on n'utilise
	pas la fonction srand, la fonction rand retourne toujours la même suite de nombres.
	Si on utilise la fonction srand, le comportement de rand sera entièrement
	déterminé par la valeur du paramètre de la fonction srand. Ce paramètre peut :
		-soit être indiqué par l'utilisateur : cela permettra d'avoir plusieurs fois de suite
		le même commportement à l'exécution.
		- soit être si possible lui-même aléatoire. Pour cela, on utilise souvent un stratagème qui
		consiste à récupérer l'heure (avec par exemple la fonction time) et de prendre cette heure
		comme paramètre de la fonction srand.
- la fonction rand dont le prototype, qui se trouve dans stdlib.h, est :
		int srand(void);
	qui retourne un entier compris entre 0 et RAND_MAX ; cette dernière constante vaut au moins 32767.
	La valeur retournée est calculée la première fois à partir d'une valeur calculée par la fonction
	srand (ou d'une constante en l'absence d'utilisation de celle-ci), les fois suivantes en fonction
	de la dernière valeur calculée.

	L'ordre du graphe est noté ordre. Les sommets sont notés 0, 1, ..., ordre-1.
	La matrice d'adjacence est construite comme un tableau à une seule dimension destiné à contenir
ordre*ordre entiers (si ordre désigne l'ordre du graphe) de façon à pouvoir à la fois faire une allocation
dynamique de mémoire et un passage en paramètre de cette matrice d'adjacence. Le seul inconvénient
est que l'élément situé à la ligne i et à la colonne j sera en position (i*ordre)+j du tableau
au lieu d'être en position [i}[j} d'une matrice à deux dimensions.*/

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

typedef struct sommet   /*Pour chaîner les listes de "fils" ou de "pères"*/
{
	int voisin;
	struct sommet * suivant;
} Sommet;

typedef Sommet * Arc;

int * ConstruireAdj(int); /*Allocation mémoire et tirage aléatoire pour la matrice
									d'adjacence initiale*/
void ImprAdj(int *, int); /*Pour imprimer à l'écran une matrice d'adjacence*/
void ImprFils(Arc *, int); /*Pour imprimer à l'écran les fils des sommets*/
void ImprPeres(Arc *, int); /*Pour imprimer à l'écran les pères des sommets*/
Arc * AdjVersFils(int *, int);
Arc * AdjVersPeres(int *, int);
int * FilsVersAdj(Arc *, int);
int * PeresVersAdj(Arc *, int);
Arc * FilsVersPeres(Arc *, int);
Arc * PeresVersFils(Arc *, int);
void LibereAdj(int *);  /*Pour libérer l'espace mémoire d'une matrice d'adjacence*/
void LibereFils(Arc *, int); /*Pour libérer l'espace mémoire d'un tableau de listes de fils*/
void LiberePeres(Arc *, int); /*Pour libérer l'espace mémoire d'un tableau de listes de pèrers*/

int main()
{
	int ordre;  /*ordre du graphe*/
	int * Adj;   /*Pour la matrice d'adjacence, écrite en "en ligne", qui sera choisie
								aléatoirement après avoir alloué l'espace mémoire nécessaire*/
	Arc * ListesFils=NULL;   /*Pour le tableau des listes chaînées des "fils"*/
	Arc * ListesPeres=NULL; /*Pour le tableau des listes chaînées des "pères"*/
	char fini=0;
	char choix;

	printf("quel est l'ordre de graphe que vous choisissez ? ");
	scanf("%d",&ordre);
	Adj=ConstruireAdj(ordre);
	ImprAdj(Adj, ordre);
	while (!fini)
	{
   	printf("\n");
		printf("Tapez le chiffre correspondant à votre choix\n");
		printf("   0) Quitter\n");
		printf("   1) Matrice d'adjacence -> Listes chaînées des fils\n");
		printf("   2) Matrice d'adjacence -> Listes chaînées des pères\n");
		if (ListesFils!=NULL)
		{
			printf("   3) Listes chaînées des fils -> Matrice d'adjacence\n");
			printf("   4) Listes chaînées des fils -> Listes chaînées des pères\n");
		}
		if (ListesPeres!=NULL)
		{
			printf("   5) Listes chaînées des pères -> Matrice d'adjacence\n");
			printf("   6) Listes chaînées des pères -> Listes chaînées des fils\n");
		}
		fflush(stdin);
		scanf("%c",&choix);
		switch(choix)
		{
			case '0' :
				fini=1;
				break;
			case '1' :
				if (ListesFils!=NULL) LibereFils(ListesFils,ordre);
				ListesFils=AdjVersFils(Adj,ordre);
				ImprFils(ListesFils,ordre);
				break;  
			case '2' :
				if (ListesPeres!=NULL) LiberePeres(ListesPeres,ordre);
				ListesPeres=AdjVersPeres(Adj,ordre);
				ImprPeres(ListesPeres,ordre);
				break;
			case '3' :
				LibereAdj(Adj);
				Adj=FilsVersAdj(ListesFils,ordre);
				ImprAdj(Adj,ordre);
				break;
			case '4' :
				if (ListesPeres!=NULL) LiberePeres(ListesPeres,ordre);
				ListesPeres=FilsVersPeres(ListesFils,ordre);
				ImprPeres(ListesPeres,ordre);
				break;
			case '5' :
				LibereAdj(Adj);
				Adj=PeresVersAdj(ListesPeres,ordre);
				ImprAdj(Adj,ordre);
				break; 
			case '6' :
				if (ListesFils!=NULL) LibereFils(ListesFils,ordre);
				ListesFils=PeresVersFils(ListesPeres,ordre);
				ImprFils(ListesFils,ordre);
				break;
		}
	}
   return 0;
}

int * ConstruireAdj(int ordre)
{
	time_t AdresseHeure;
	int i,j;
	int * MatAdj;

	srand((unsigned int)time(& AdresseHeure));
	MatAdj =(int *)malloc(ordre*ordre*sizeof(int));
	for (i=0;i<ordre;i++)
		for (j=0;j<ordre;j++) MatAdj[i*ordre+j]=rand()%2; /*la probabilité d'existence
																d'un arc est 1/2*/
	for (i=0;i<ordre;i++) MatAdj[i*ordre+i]=0; /*suppression des arcs d'un sommet i à lui-même*/
	return MatAdj;
}

Arc * AdjVersFils(int * Adj, int ordre)
{
	Arc * Fils;

	/*A COMPLETER sans oublier l'allocation mémoire du tableau des listes de fils*/

	return Fils;
}

Arc * AdjVersPeres(int * Adj, int ordre)
{
	Arc * Peres;

	/*A COMPLETER sans oublier l'allocation mémoire du tableau des listes de peres*/

	return Peres;
}

int * FilsVersAdj(Arc * Fils, int ordre)
{   
	int * Adj;
		/*A COMPLETER sans oublier l'allocation mémoire du tableau Adj devant contenir
	la matrice d'adjacence*/

	return Adj;
}

int * PeresVersAdj(Arc * Peres, int ordre)
{
	int * Adj;

	/*A COMPLETER sans oublier l'allocation mémoire du tableau Adj devant contenir
	la matrice d'adjacence*/

	return Adj;
}

Arc * FilsVersPeres(Arc * Fils, int ordre)
{
	Arc * Peres;

	/*A COMPLETER sans oublier l'allocation mémoire du tableau des listes de peres*/

	return Peres;
}

Arc * PeresVersFils(Arc * Peres, int ordre)
{
	Arc * Fils;

	/*A COMPLETER sans oublier l'allocation mémoire du tableau des listes de fils*/

	return Fils;
}


void ImprAdj(int * MatAdj, int ordre)
{
	int i,j;

	for (i=0;i<ordre;i++)
	{
		for (j=0;j<ordre;j++) printf("%d ",MatAdj[i*ordre+j]);
		printf("\n");   
	}
}

void ImprFils(Arc * Fils, int ordre)
{
	int i;
	Arc  p;

	for(i=0;i<ordre;i++)
	{
		printf("Fils du sommet %d : ",i);
		p=Fils[i];
		while(p!=NULL)
		{
			printf("%d ",p->voisin);
			p=p->suivant;
		}
		printf("\n");
	}
}

void ImprPeres(Arc * Peres, int ordre)
{
	int i;
	Arc  p;

   for(i=0;i<ordre;i++)
	{
		printf("Peres du sommet %d : ",i);
		p=Peres[i];
		while(p!=NULL)
		{
			printf("%d ",p->voisin);
			p=p->suivant;
		}
		printf("\n");
	}
}

void LibereAdj(int * Adj)
{
	free(Adj);
}

void LibereFils(Arc * Fils, int ordre)
{
	int i;
	Arc  p, q;

	for(i=0;i<ordre;i++)
	{
		p=Fils[i];
		while(p!=NULL)
		{
			q=p;
			p=p->suivant;
			free(q);
		}
	}
	free(Fils);
}

void LiberePeres(Arc * Peres, int ordre)
{
	int i;
	Arc  p, q;

	for(i=0;i<ordre;i++)
	{
		p=Peres[i];
		while(p!=NULL)
		{
			q=p;
			p=p->suivant;
			free(q);
		}
	} 
	free(Peres);
}