/* 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.

	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(Sommet**, 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;
	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;
	int i,j;
	Arc  p;

	Fils=(Arc *)malloc(ordre*sizeof(Arc ));
	for (i=0;i<ordre;i++) Fils[i]=NULL;
	for (i=0;i<ordre;i++)
		for (j=0;j<ordre;j++)
		{
			if (Adj[i*ordre+j])
			{
				p=(Arc )malloc(sizeof(Sommet));
				p->voisin=j;
				p->suivant=Fils[i];
				Fils[i]=p;
			}
		}
	return Fils;
}

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

	Peres=(Arc *)malloc(ordre*sizeof(Arc ));
	for (i=0;i<ordre;i++) Peres[i]=NULL;
	for (i=0;i<ordre;i++)
		for (j=0;j<ordre;j++)
		{
			if (Adj[i*ordre+j])
			{
				p=(Arc )malloc(sizeof(Sommet));
				p->voisin=i;
				p->suivant=Peres[j];
				Peres[j]=p;
			}
		}
	return Peres;
}

int * FilsVersAdj(Arc * Fils, int ordre)
{
	int * Adj;
	Arc  p;
	int i, j;

	Adj =(int *)malloc(ordre*ordre*sizeof(int));
	for (i=0;i<ordre;i++)
		for (j=0;j<ordre;j++) Adj[i*ordre+j]=0;
	for(i=0;i<ordre;i++)
	{
		p=Fils[i];
		while(p!=NULL)
		{
			Adj[i*ordre+p->voisin]=1;;
			p=p->suivant;
		}
	}
	return Adj;
}

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

	Adj =(int *)malloc(ordre*ordre*sizeof(int));
	for (i=0;i<ordre;i++)
		for (j=0;j<ordre;j++) Adj[i*ordre+j]=0;
	for(j=0;j<ordre;j++)
	{
		p=Peres[j];
		while(p!=NULL)
		{
			Adj[p->voisin*ordre+j]=1;;
			p=p->suivant;
		}
	}
	return Adj;
}

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

	Peres=(Arc *)malloc(ordre*sizeof(Arc ));
	for (i=0;i<ordre;i++) Peres[i]=NULL;
	for (i=0;i<ordre;i++)
	{
		p=Fils[i];
		while(p!=NULL)
		{
			q=(Arc )malloc(sizeof(Sommet));
			q->voisin=i;
			q->suivant=Peres[p->voisin];
			Peres[p->voisin]=q;
			p=p->suivant;
		}
	}
	return Peres;
}

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

	Fils=(Arc *)malloc(ordre*sizeof(Arc ));
	for (i=0;i<ordre;i++) Fils[i]=NULL;
	for (i=0;i<ordre;i++)
	{
		p=Peres[i];
		while(p!=NULL)
		{
			q=(Arc )malloc(sizeof(Sommet));
			q->voisin=i;
			q->suivant=Fils[p->voisin];
			Fils[p->voisin]=q; 
			p=p->suivant;
		}
	}
	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);
}