#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include "liste.h"

/*	Auteur: Benoit Papillault
	Creation: Mardi 4 Novembre 1997
	Derniere modification: 16/11/1997

	Etudier diverses operations sur des graphes particuliers. Ici,
	un graphe G=(N,E,h).
	N = ensemble des noeuds. (node set)
	E = ensemble des aretes orientees. (edge set)
	h = noeud de depart (header)

	On representera ce graphe par une structure donnant le numero du noeud
	de depart, suivi d'une liste d'arete. Chaque arete est designee par
	le couple (noeud_de_depart,noeud_d_arrivee). On n'impose pour l'instant
	aucune restriction sur le choix des numeros de noeuds. Par contre,
	il ne peux exister plus de deux aretes partant d'un meme noeud.

	19/11/1997: Pour representer le graphe, on donne une liste d'aretes
	dont les extremites sont les indices des noeuds dans la liste des 
	noeuds. De meme, noeud_depart est aussi un indice.

	Les fonctions de calcul des intervalles et la construction de la suite
	de graphe sont au points. Reste a rendre cela plus pratique et plus
	propre en ce qui concerne la gestion memoire. (liste de liste...)

	21/11/1997: Attention, realloc(ptr,0) ne renvoie pas NULL.

	04/02/1998: ajout des fontions de reconnaissance de motif sur les 
		graphes. Correction d'un bug dans tabadd [il manquait le zero 
		terminal].

*/

typedef int bool;

struct noeud
{
	int	no_noeud;	/* le numero du noeud, lu dans le fichier */
	int	no_intervalle;	/* un indice de l'entete de l'intervalle */
	int	deja_visite;	/* si le noeud figure dans un intervalle */
	int	nb_arc_entrant;
	int	nb_arc_sortant;

	char	*chaine;
};

struct arete
{
	int	noeud_depart;	/* indice du noeud dans la liste les_noeuds */
	int	noeud_arrivee;	/* idem */
};

LISTE(liste_arete,struct arete)
LISTE(liste_noeud,struct noeud)

struct graphe
{
	int	noeud_depart;	/* indice dans la liste les_noeuds */

	/* le nombre d'arc entrant/sortant vers des noeuds exterieurs au
		graphe */

	struct liste_arete les_aretes;
	struct liste_noeud les_noeuds;
};

LISTE(liste_entier,int)
LISTE2(liste_intervalle,liste_entier)

char *stradd(const char *s1,...)
{
	int	len;
	char	*result, *s;
	va_list	var;

	len = strlen(s1);
	result = strdup(s1);

	va_start(var,s1);

	while ((s=va_arg(var,char *)) != NULL)
	{
		len += strlen(s);
		result = (char *)realloc(result,len+1);
		if (result == NULL)
			printf("stradd: realloc failed\n");
		strcat(result,s);
	}

	va_end(var);

	return result;
}

/* ajoute une tabulation au debut de chaque ligne */

char *tabadd(const char *s)
{
	int	len, first_char = 1;
	char	*result, *r;

	len = strlen(s);
	result = (char *)malloc(len+100);	/* max 99 tab */
	if (result == NULL)
		printf("tabadd: malloc failed\n");
	for (r=result;*s!=0;s++)
	{
		if (first_char)
		{
			first_char = 0;
			*r++ = '\t';
		}
		*r++ = *s;
		if (*s == '\n') first_char = 1;
	}
	*r = 0;

	return result;
}

/* ======================== GRAPHES ========================================= */

/* retourne l'indice du nouveau noeud ou d'un noeud deja existant */

int graphe_ajouter_noeud(struct graphe *g,int no_noeud)
{
	int i;
	struct noeud le_noeud;
	char	buffer[100];

	for (i=0;i<g->les_noeuds.nb;i++)
		if (g->les_noeuds.liste[i].no_noeud == no_noeud)
		{
			printf("graphe_ajouter_noeud: le noeud %d existe deja\n",
				no_noeud);
			return i;
		}

	le_noeud.no_noeud = no_noeud;
	le_noeud.deja_visite = 0;
	le_noeud.nb_arc_entrant = 0;
	le_noeud.nb_arc_sortant = 0;

	sprintf(buffer,"inst %d;\n",no_noeud);
	le_noeud.chaine = strdup(buffer);

	liste_noeud_ajouter(&g->les_noeuds,&le_noeud);
	return (g->les_noeuds.nb-1);
}

void graphe_init(struct graphe *g,int depart)
{
	int i;

	liste_arete_init(&g->les_aretes);
	liste_noeud_init(&g->les_noeuds);
	i = graphe_ajouter_noeud(g,depart);
	g->noeud_depart = i;
}

void graphe_copy(struct graphe *dst,const struct graphe *src)
{
	dst->noeud_depart = src->noeud_depart;
	liste_arete_copy(&dst->les_aretes,&src->les_aretes);
	liste_noeud_copy(&dst->les_noeuds,&src->les_noeuds);
}

void graphe_done(struct graphe *g)
{
	liste_arete_done(&g->les_aretes);
	liste_noeud_done(&g->les_noeuds);
}

/* ajoute une arete dans un graphe, noeud_depart et noeud_arrivee corespondent
	aux numeros des noeuds */

void graphe_ajouter_arete(struct graphe *g,int noeud_depart,int noeud_arrivee)
{
	struct arete l_arete;
	int i,j;

	i = graphe_ajouter_noeud(g,noeud_depart);
	j = graphe_ajouter_noeud(g,noeud_arrivee);

	l_arete.noeud_depart = i;
	l_arete.noeud_arrivee = j;

	liste_arete_ajouter(&g->les_aretes,&l_arete);
}

/* elimine l'arete d'indice i du graphe. On decremente aussi le nombre d'arcs entrants
	et sortants des noueuds correspondants */

void graphe_enlever_arete(struct graphe *g,int i)
{
	int j;

	if (i<0 || i>=g->les_aretes.nb)
	{
		printf("graphe_enlever_arete: %d indice invalide\n",i);
		return;
	}

	g->les_noeuds.liste[g->les_aretes.liste[i].noeud_depart].nb_arc_sortant --;
	g->les_noeuds.liste[g->les_aretes.liste[i].noeud_arrivee].nb_arc_entrant --;

	/* on decale les aretes restantes */
	for (j=i+1;j<g->les_aretes.nb;j++)
		g->les_aretes.liste[j-1] = g->les_aretes.liste[j];

	/* on decremente le nombre d'aretes */
	g->les_aretes.nb --;

	/* on ne realloue pas la memoire, ce n'est pas tres important */
}

void graphe_ecrire(FILE *fp,const struct graphe *g)
{
	int i;
	int no_depart, no_arrivee;

	if (g->les_noeuds.nb == 0)
	{
		printf("graphe vide\n");
		return;
	}

	fprintf(fp,"%d\n",g->les_noeuds.liste[g->noeud_depart].no_noeud);
	for (i=0;i<g->les_aretes.nb;i++)
	{
		no_depart = g->les_aretes.liste[i].noeud_depart;
		no_depart = g->les_noeuds.liste[no_depart].no_noeud;
		no_arrivee = g->les_aretes.liste[i].noeud_arrivee;
		no_arrivee = g->les_noeuds.liste[no_arrivee].no_noeud;
		fprintf(fp,"%d %d\n",no_depart,no_arrivee);
	}

	for (i=0;i<g->les_noeuds.nb;i++)
		printf("noeud %d =>\n%s",g->les_noeuds.liste[i].no_noeud,
			g->les_noeuds.liste[i].chaine);
}

/* renvoie 1 si la lecture du graphe a partir du fichier est correcte,
	0 sinon */

int graphe_lire(const char *file,struct graphe *g)
{
	int n1,n2;
	FILE *fp;

	fp = fopen(file,"r");
	if (fp == NULL)
	{
		perror(file);
		return 0;
	}

	if (fscanf(fp,"%d",&n1) != 1)
	{
		fclose(fp);
		return 0;
	}

	graphe_init(g,n1);

	/* comme on considere que le graphe represente une fonction, il y a
		un arc entrant vers le noeud de depart */

	while (fscanf(fp,"%d %d",&n1,&n2) == 2)
		graphe_ajouter_arete(g,n1,n2);

	fclose(fp);

	return 1;
}

/* ajoute l'entier s'il n'existe pas deja dans la liste */

void liste_entier_rajouter(struct liste_entier *les_entiers,int *p_no)
{
	int i;

	for (i=0;i<les_entiers->nb;i++)
		if (les_entiers->liste[i] == *p_no)
			return;

	liste_entier_ajouter(les_entiers,p_no);
}

/* ========================= MANIPULATIONS ================================== */

/* calcule les successeurs immediat d'un noeud dont l'indice est donne,
	les indices des successeurs sont ajoutes dans liste_succ */

void calculer_successeurs(const struct graphe *g,int i_noeud,
	struct liste_entier *liste_succ)
{
	int i, no_noeud;

	for (i=0;i<g->les_aretes.nb;i++)
		if (g->les_aretes.liste[i].noeud_depart == i_noeud)
		{
			no_noeud = g->les_aretes.liste[i].noeud_arrivee;
			liste_entier_rajouter(liste_succ,&no_noeud);
		}
}

int est_dans_liste(int no_noeud,const struct liste_entier *les_noeuds)
{
	int i;

	for (i=0;i<les_noeuds->nb;i++)
		if (les_noeuds->liste[i] == no_noeud)
			return 1;
	return 0;
}

/* enleve un entier de la liste et le retourne. retourne 0 s'il n'y a plus
	d'entier dans la liste */

int liste_entier_enlever(struct liste_entier *les_entiers)
{
	int result;

	if (les_entiers->nb == 0)
	{
		printf("attention: la liste d'entiers est vide!\n");
		return 0;
	}

	result = les_entiers->liste[les_entiers->nb-1];

	les_entiers->nb--;
	if (les_entiers->nb != 0)
	{
		les_entiers->liste = (int *)realloc(les_entiers->liste,
				les_entiers->nb*sizeof(int));
		if (les_entiers->liste == NULL)
			printf("liste_entier_enlever: realloc failed\n");
	}
	else
	{
		free(les_entiers->liste);
		les_entiers->liste = NULL;
	}

	return result;
}

/* rajoute un noeud inexistant dans le graphe avec un nombre d'arcs entrants
	et sortants nuls. On retourne l'indice du noeud dans les_noeuds */

int graphe_nouveau_noeud(struct graphe *g)
{
	int i,no = 0;

	for (i=0;i<g->les_noeuds.nb;i++)
		if (g->les_noeuds.liste[i].no_noeud >= no)
			no = g->les_noeuds.liste[i].no_noeud + 1;

	return graphe_ajouter_noeud(g,no);
}

/* dans la liste des arcs (ainsi que le noeud de depart) , remplace le noeud j
	par le noeud k. Le nombre d'arcs entrants/sortants est recalcule */

void graphe_remplacer_noeud(struct graphe *g,int j, int k)
{
	int i;

	if (g->noeud_depart == j)
		g->noeud_depart = k;

	for (i=0;i<g->les_aretes.nb;i++)
	{
		if (g->les_aretes.liste[i].noeud_depart == j)
		{
			g->les_aretes.liste[i].noeud_depart = k;
			g->les_noeuds.liste[k].nb_arc_sortant ++;
		}
		if (g->les_aretes.liste[i].noeud_arrivee == j)
		{
			g->les_aretes.liste[i].noeud_arrivee = k;
			g->les_noeuds.liste[k].nb_arc_entrant ++;
		}
	}

	printf("noeud %d -> arc_entrants %d, arc_sortants %d\n",
		g->les_noeuds.liste[k].no_noeud,
		g->les_noeuds.liste[k].nb_arc_entrant,
		g->les_noeuds.liste[k].nb_arc_sortant);

	/* on detruit le noeud (pas bo) */
	g->les_noeuds.liste[j].nb_arc_entrant = 0;
	g->les_noeuds.liste[j].nb_arc_sortant = 0;
}

/* calcule le nombre d'arcs entrants et sortants de chaque noeud, ceci doit
	etre fait a la fin de la construction du graphe et avant les calculs
	qui utilisent les champs 'nb_arc_entrant' et 'nb_arc_sortant'
*/

void graphe_nb_arc(struct graphe *g)
{
	int i, noeud_depart, noeud_arrivee;

	for (i=0;i<g->les_aretes.nb;i++)
	{
		noeud_depart = g->les_aretes.liste[i].noeud_depart;
		noeud_arrivee = g->les_aretes.liste[i].noeud_arrivee;
		g->les_noeuds.liste[noeud_depart].nb_arc_sortant ++;
		g->les_noeuds.liste[noeud_arrivee].nb_arc_entrant ++;
	}

	/* les conclusions */

	for (i=0;i<g->les_noeuds.nb;i++)
		printf("noeud %d, arc_entrant %d, arc_sortant %d\n",
			g->les_noeuds.liste[i].no_noeud,
			g->les_noeuds.liste[i].nb_arc_entrant,
			g->les_noeuds.liste[i].nb_arc_sortant);
}

/* verifie si tous les predecesseurs du noeud i_noeud sont dans 
	intervalle et renvoie 1 dans ce cas, 0 sinon */

int tester_noeud(const struct graphe *g,int i_noeud,
	const struct liste_entier *intervalle)
{
	int i,n1;

	for (i=0;i<g->les_aretes.nb;i++)
		if (g->les_aretes.liste[i].noeud_arrivee == i_noeud)
		{
			n1 = g->les_aretes.liste[i].noeud_depart;
			if (!est_dans_liste(n1,intervalle))
				return 0;
		}

	return 1;
}

/* a_suivre est la liste des noeuds avec lesquelles on pourra calculer
	les prochains intervalles */

void calculer_intervalle(struct graphe *g,int i_depart,
	struct liste_entier *l_intervalle,struct liste_entier *a_suivre)
{
	struct liste_entier a_examiner;
	int n1;

	liste_entier_init(&a_examiner);

	g->les_noeuds.liste[i_depart].deja_visite = 1;
	g->les_noeuds.liste[i_depart].no_intervalle = i_depart;
	liste_entier_ajouter(l_intervalle,&i_depart);
	calculer_successeurs(g,i_depart,&a_examiner);

	while (a_examiner.nb > 0)
	{
		n1 = liste_entier_enlever(&a_examiner);
		if (g->les_noeuds.liste[n1].deja_visite)
			continue;

		printf("on examine %d ",g->les_noeuds.liste[n1].no_noeud);

		/* on examine les predecesseurs du premier noeud */
		if (tester_noeud(g,n1,l_intervalle))
		{
			printf("ok\n");
			g->les_noeuds.liste[n1].deja_visite = 1;
			g->les_noeuds.liste[n1].no_intervalle = i_depart;
			liste_entier_ajouter(l_intervalle,&n1);
			calculer_successeurs(g,n1,&a_examiner);
		}
		else
		{
			printf("pas ok\n");
			liste_entier_rajouter(a_suivre,&n1);
		}
		
	}

	liste_entier_done(&a_examiner);
}

void calculer_intervalles(struct graphe *g,
	struct liste_intervalle *les_intervalles)
{
	int n1;
	struct liste_entier prochains_noeuds;
	struct liste_entier intervalle_courant;
	int pas_fini;

	n1 = g->noeud_depart;
	liste_entier_init(&prochains_noeuds);

	do
	{
		liste_entier_init(&intervalle_courant);

		/* on calcule le premier intervalle */
		calculer_intervalle(g,n1,&intervalle_courant,&prochains_noeuds);
		liste_intervalle_ajouter(les_intervalles,&intervalle_courant);

		liste_entier_done(&intervalle_courant);

		/* on cherche un noeud d'entete pour le prochain intervalle */

		pas_fini = 0;
		while (prochains_noeuds.nb > 0)
		{
			n1 = liste_entier_enlever(&prochains_noeuds);
			if ( !g->les_noeuds.liste[n1].deja_visite )
			{
				pas_fini = 1;
				break;
			}
		}
	}
	while (pas_fini); 

	liste_entier_done(&prochains_noeuds);
}

void afficher_intervalle(const struct graphe *g,
	const struct liste_entier *les_entiers)
{
	int i,n1;

	
	printf("les noeuds de l'intervalle sont");
	for (i=0;i<les_entiers->nb;i++)
	{
		n1 = les_entiers->liste[i];
		printf(" %d",g->les_noeuds.liste[n1].no_noeud);
	}
	printf("\n");
}

void liste_intervalle_afficher(const struct graphe *g,
	const struct liste_intervalle *les_intervalles)
{
	int i;

	for (i=0;i<les_intervalles->nb;i++)
		afficher_intervalle(g,&les_intervalles->liste[i]);
}

/* on doit avoir au prealable calculer tout les intervalles de g1,
	g2 est non initialise */

void construire_nouveau_graphe(struct graphe *g1,struct graphe *g2)
{
	int i,n1,n2;
	int inter1,inter2;

	n1 = g1->noeud_depart;
	n1 = g1->les_noeuds.liste[n1].no_intervalle;
	graphe_init(g2,g1->les_noeuds.liste[n1].no_noeud);

	/* on transforme les aretes */

	for (i=0;i<g1->les_aretes.nb;i++)
	{
		n1 = g1->les_aretes.liste[i].noeud_depart;
		n2 = g1->les_aretes.liste[i].noeud_arrivee;
		n1 = g1->les_noeuds.liste[n1].no_intervalle;
		n2 = g1->les_noeuds.liste[n2].no_intervalle;
		inter1 = g1->les_noeuds.liste[n1].no_noeud;
		inter2 = g1->les_noeuds.liste[n2].no_noeud;
		if (inter1 != inter2)
			graphe_ajouter_arete(g2,inter1,inter2);
	}
}

/* construits la suite des graphes jusqu'a arriver a un graphe limite
	irreductible */

void calculer_suite_graphe(const struct graphe *g)
{
	struct graphe g1,g2;
	struct liste_intervalle ma_liste;
	int i;

	graphe_copy(&g1,g);

	for (i=1;;i++)
	{
		liste_intervalle_init(&ma_liste);
		calculer_intervalles(&g1,&ma_liste);
		printf("g%d:\n",i);
		graphe_ecrire(stdout,&g1);
		liste_intervalle_afficher(&g1,&ma_liste);
		liste_intervalle_done(&ma_liste);
		construire_nouveau_graphe(&g1,&g2);

		/* la condition d'arret suivante n'est pas demontree:
			on s'arrete si le nombre de noeuds du graphe n'a
			pas diminue */

		if (g1.les_noeuds.nb == g2.les_noeuds.nb)
			break;

		graphe_done(&g1);
		graphe_copy(&g1,&g2);
		graphe_done(&g2);
	}

	graphe_done(&g1);
}

/* un nouveau graphe est contruit a partir du premier en restreignant
	l'ensemble des (numero des) noeuds a la liste donnee en parametres.
	Par convention,
	le premier indice de noeud correspond au noeud de depart
*/

void construire_sous_graphe(struct graphe *dst,const struct graphe *src,
	struct liste_entier *les_noeuds)
{
	int i;
	int indice_depart, indice_arrivee;
	int	no_depart, no_arrivee;

	if (les_noeuds->nb == 0)
	{
		printf("erreur: liste de noeuds vide\n");
		return;
	}

	graphe_init(dst,les_noeuds->liste[0]);

	for (i=0;i<src->les_aretes.nb;i++)
	{
		indice_depart = src->les_aretes.liste[i].noeud_depart;
		indice_arrivee = src->les_aretes.liste[i].noeud_arrivee;
		no_depart = src->les_noeuds.liste[indice_depart].no_noeud;
		no_arrivee = src->les_noeuds.liste[indice_arrivee].no_noeud;
		if (est_dans_liste(no_depart,les_noeuds)
			&& est_dans_liste(no_arrivee,les_noeuds))
		{
			graphe_ajouter_arete(dst,no_depart,no_arrivee);
		}
	}
}

/* retourne 1 si l'on a reconnu une construction inst1; inst2. inst1
correspond au noeud i et inst2 au noeud j. On a donc un seul arc
sortant de i et un seul arc entrant en j et il s'agit de l'arc (i->j) */

int reconnaitre_composition(struct graphe *g,int i)
{
	int j,k,arete;

	/* le noeud i doit avoir un et un seul successeur */

	if (g->les_noeuds.liste[i].nb_arc_sortant != 1)
		return 0;

	for (arete=0;arete<g->les_aretes.nb;arete++)
		if (g->les_aretes.liste[arete].noeud_depart == i)
			break;

	/* j est le sucesseur de i */
	j = g->les_aretes.liste[arete].noeud_arrivee;

	/* on regarde si j n'a qu'un seul predecesseur */
	if (g->les_noeuds.liste[j].nb_arc_entrant != 1)
		return 0;

	/* afin d'eviter d'inclure un noeud ayant plusieurs successeurs,
		on fait une verification supplementaire */
	/*	if (g->les_noeuds.liste[j].nb_arc_sortant > 1)
		return 0;
	*/

	/* on peut regouper le noeuds i+j en un nouveau noeud k */

	k = graphe_nouveau_noeud(g);

	printf("on transforme %d; %d en %d\n",
		g->les_noeuds.liste[i].no_noeud,g->les_noeuds.liste[j].no_noeud,
		g->les_noeuds.liste[k].no_noeud);

	g->les_noeuds.liste[k].chaine = stradd(g->les_noeuds.liste[i].chaine,
			g->les_noeuds.liste[j].chaine,NULL);

	graphe_enlever_arete(g,arete);
	graphe_remplacer_noeud(g,i,k);
	graphe_remplacer_noeud(g,j,k);

	return 1;
}

/* retourne 1 si l'on reconnait if (i) then suc1 avec arete1=(i->suc1)
et arete2=(i->suc2). On modifie le graphe initial en consequence */

int reconnaitre_if_then_arete(struct graphe *g,int i,int arete1,
	int suc1,int arete2,int suc2)
{
	int	j= -1,k,if_ok = 0;

	/* on essaye la construction if (i) then suc1 */

	if (g->les_noeuds.liste[suc1].nb_arc_entrant == 1)
	{
		/* cas ou suc1 est un return => cas elimine provisoirement
			car peut entrer en conflit avec un while_do */

		/* if (g->les_noeuds.liste[suc1].nb_arc_sortant == 0)
		{
			if_ok = 1;
		} */

		/* cas ou l'on a (suc1->suc2) */

		if (g->les_noeuds.liste[suc1].nb_arc_sortant == 1)
		{
			for (j=0;j<g->les_aretes.nb;j++)
			{
				if (g->les_aretes.liste[j].noeud_depart == suc1
				    && g->les_aretes.liste[j].noeud_arrivee == suc2)
				{
					if_ok = 1;
					break;
				}
			}
		}
	}

	if (!if_ok)
		return 0;

	k = graphe_nouveau_noeud(g);
	printf("on transforme if %d then %d en %d\n",
		g->les_noeuds.liste[i].no_noeud,
		g->les_noeuds.liste[suc1].no_noeud,
		g->les_noeuds.liste[k].no_noeud);

	g->les_noeuds.liste[k].chaine = stradd("if (",
		g->les_noeuds.liste[i].chaine,")\n{\n",
		tabadd(g->les_noeuds.liste[suc1].chaine),"}\n",
		NULL);

	graphe_enlever_arete(g,arete1);
	if (j >= 0)
	{
		if (j > arete1) j--; /* petit bug */
		graphe_enlever_arete(g,j);
	}
	graphe_remplacer_noeud(g,i,k);
	graphe_remplacer_noeud(g,suc1,k);
	
	return 1;
}

/* retourne 1 si l'on a reconnu une structure if_then du style if (i)
then j. Dans ce cas, i doit avoir deux successeurs et l'un de ces
sucesseurs, soit ne possede pas d'arc sortant, soit l'arc sortant a
pour noeud d'arrivee le noeud d'arrivee de l'autre arc sortant de
i. Si on a (i->suc1) et (i->suc2) alors si suc1 a un arc sortant, il
doit s'agir de (suc1->suc2) */

int reconnaitre_if_then(struct graphe *g,int i)
{
	int	suc1, suc2;
	int	arete1, arete2;

	if (g->les_noeuds.liste[i].nb_arc_sortant != 2)
		return 0;

	for (arete1=0;arete1<g->les_aretes.nb;arete1++)
		if (g->les_aretes.liste[arete1].noeud_depart == i)
		{
			suc1 = g->les_aretes.liste[arete1].noeud_arrivee;
			break;
		}

	/* on poursuit la recherche */

	for (arete2=arete1+1;arete2<g->les_aretes.nb;arete2++)
		if (g->les_aretes.liste[arete2].noeud_depart == i)
		{
			suc2 = g->les_aretes.liste[arete2].noeud_arrivee;
			break;
		}

	printf("suc1=%d, suc2=%d\n",
		g->les_noeuds.liste[suc1].no_noeud,
		g->les_noeuds.liste[suc2].no_noeud);

	if (reconnaitre_if_then_arete(g,i,arete1,suc1,arete2,suc2))
		return 1;
	if (reconnaitre_if_then_arete(g,i,arete2,suc2,arete1,suc1))
		return 1;
	
	return 0;
}

/* retourne 1 si l'on a reconnu une structure if_then_else du style if (i)
then suc1 else suc2. Dans ce cas, i doit avoir deux successeurs et
chaque successeur soit ne possede pas de successeurs, soit possede
tous les deux le meme sucesseurs. Dans le cas, ou un des deux noeuds
ne possede pas de successeurs seulement, il s'agit en fait d'un
if_then et non un if_then_else */

int reconnaitre_if_then_else(struct graphe *g,int i)
{
	int	suc1, suc2, suc3, suc4;
	int	arete1, arete2, arete3, arete4;
	int	k;

	if (g->les_noeuds.liste[i].nb_arc_sortant != 2)
		return 0;

	for (arete1=0;arete1<g->les_aretes.nb;arete1++)
		if (g->les_aretes.liste[arete1].noeud_depart == i)
		{
			suc1 = g->les_aretes.liste[arete1].noeud_arrivee;
			break;
		}

	/* on poursuit la recherche */

	for (arete2=arete1+1;arete2<g->les_aretes.nb;arete2++)
		if (g->les_aretes.liste[arete2].noeud_depart == i)
		{
			suc2 = g->les_aretes.liste[arete2].noeud_arrivee;
			break;
		}

	printf("suc1=%d, suc2=%d\n",
		g->les_noeuds.liste[suc1].no_noeud,
		g->les_noeuds.liste[suc2].no_noeud);

	/* on traite le cas ou les deux noeuds ne possedent pas de
		successeurs */
	if (g->les_noeuds.liste[suc1].nb_arc_sortant == 0
		&& g->les_noeuds.liste[suc2].nb_arc_sortant)
	{
		k = graphe_nouveau_noeud(g);


		g->les_noeuds.liste[k].chaine = stradd("if (",
			g->les_noeuds.liste[i].chaine,")\n{\n",
			tabadd(g->les_noeuds.liste[suc1].chaine),
			"}\nelse\n{\n",
			tabadd(g->les_noeuds.liste[suc2].chaine),
			"}\n",NULL);

		graphe_enlever_arete(g,arete1);
		if (arete2 > arete1)	arete2--; /* petit bug */
		graphe_enlever_arete(g,arete2);
		graphe_remplacer_noeud(g,i,k);
		graphe_remplacer_noeud(g,suc1,k);
		graphe_remplacer_noeud(g,suc2,k);

		return 1;		
	}

	/* on traite le cas ou les deux noeuds possedent le meme
		sucesseur */

	if (g->les_noeuds.liste[suc1].nb_arc_sortant == 1
		&& g->les_noeuds.liste[suc2].nb_arc_sortant == 1)
	{
		/* on cherche les deux sucesseurs: a et b */

		for (arete3=0;arete3<g->les_aretes.nb;arete3++)
			if (g->les_aretes.liste[arete3].noeud_depart==suc1)
			{
			    suc3 = g->les_aretes.liste[arete3].noeud_arrivee;
			    break;
			}

		for (arete4=0;arete4<g->les_aretes.nb;arete4++)
			if (g->les_aretes.liste[arete4].noeud_depart==suc2)
			{
			    suc4 = g->les_aretes.liste[arete4].noeud_arrivee;
			    break;
			}

		if (suc3 != suc4)
			return 0;

		/* c'est bon */

		k = graphe_nouveau_noeud(g);
		g->les_noeuds.liste[k].chaine = stradd("if (",
			g->les_noeuds.liste[i].chaine,")\n{\n",
			tabadd(g->les_noeuds.liste[suc1].chaine),
			"}\nelse\n{\n",
			tabadd(g->les_noeuds.liste[suc2].chaine),
			"}\n",NULL);

		printf("on transforme if %d then %d else %d en %d\n",
			g->les_noeuds.liste[i].no_noeud,
			g->les_noeuds.liste[suc1].no_noeud,
			g->les_noeuds.liste[suc2].no_noeud,
			g->les_noeuds.liste[k].no_noeud);

		graphe_enlever_arete(g,arete1);
		if (arete2 > arete1)	arete2--; /* petit bug */
		graphe_enlever_arete(g,arete2);
		if (arete3 > arete2)	arete3--; /* idem */
		graphe_enlever_arete(g,arete3);
		graphe_remplacer_noeud(g,i,k);
		graphe_remplacer_noeud(g,suc1,k);
		graphe_remplacer_noeud(g,suc2,k);

		return 1;		
	}

	return 0;
}

/* essaye de reconnaitre une structure while () {} dont le premier noeud est
	celui d'indice i. On a une struture du style (a->b) avec a
	ayant une autre sortie et un arc (b->a) */

int reconnaitre_while(struct graphe *g,int i)
{
	int	arete1,arete2;
	int	j,k;

	/* on sait deja que le noeud i doit avoir plusieurs arc_entrant
	   (un pour rentrer dans la boucle, l'autre pour la repeter)
	   et plusieurs arcs sortants (un pour executer la boucle,
	   l'autre pour en sortir)
	   */

	if (g->les_noeuds.liste[i].nb_arc_entrant < 2
		|| g->les_noeuds.liste[i].nb_arc_sortant < 2)
			return 0;

	/* on cherche un noeud j tel que (i->j) et (j->i) */

	for (arete1=0;arete1<g->les_aretes.nb;arete1++)
	{
		if (g->les_aretes.liste[arete1].noeud_depart == i)
		{
			j = g->les_aretes.liste[arete1].noeud_arrivee;
			/* on a UNE arete (i->j), on cherche l'arete (j->i),
			   mais on sait deja que j doit avoir un seul arc
			   entrant et un seul arc sortant */

			if (g->les_noeuds.liste[j].nb_arc_entrant != 1
				|| g->les_noeuds.liste[j].nb_arc_sortant != 1)
					continue;

			for (arete2=0;arete2<g->les_aretes.nb;arete2++)
			{
				if (g->les_aretes.liste[arete2].noeud_depart == j
					&& g->les_aretes.liste[arete2].noeud_arrivee == i)
				{
					k = graphe_nouveau_noeud(g);

					g->les_noeuds.liste[k].chaine = stradd("while (",
						g->les_noeuds.liste[i].chaine,")\n{\n",
						tabadd(g->les_noeuds.liste[j].chaine),
						"}\n",NULL);

					printf("transforme while %d { %d } en %d\n",
						g->les_noeuds.liste[i].no_noeud,
						g->les_noeuds.liste[j].no_noeud,
						g->les_noeuds.liste[k].no_noeud);

					graphe_enlever_arete(g,arete1);
					if (arete2 > arete1) arete2--; /* petit bug */
					graphe_enlever_arete(g,arete2);
					graphe_remplacer_noeud(g,i,k);
					graphe_remplacer_noeud(g,j,k);

					return 1;
				}
			}
		}
	}

	return 0;
}

/* essaye de reconnaitre une structure do {} while (); dont le premier noeud
	est celui d'indice i. On a une struture du style (a->b) avec b ayant
	une autre sortie et un arc (b->a) */

int reconnaitre_do_while(struct graphe *g,int i)
{
	int	arete1,arete2;
	int	j,k;

	/* on sait deja que le noeud i doit avoir plusieurs arc_entrant
		(un pour rentrer dans la boucle, l'autre pour la repeter)
	*/

	if (g->les_noeuds.liste[i].nb_arc_entrant < 2
		|| g->les_noeuds.liste[i].nb_arc_sortant != 1)
			return 0;

	/* on cherche un noeud j tel que (i->j) et (j->i) */

	for (arete1=0;arete1<g->les_aretes.nb;arete1++)
	{
		if (g->les_aretes.liste[arete1].noeud_depart == i)
		{
			j = g->les_aretes.liste[arete1].noeud_arrivee;
			/* on a UNE arete (i->j), on cherche l'arete (j->i),
				mais on sait deja que j doit avoir un arc 
				entrant et un seul arc sortant */

			if (g->les_noeuds.liste[j].nb_arc_entrant != 1
				|| g->les_noeuds.liste[j].nb_arc_sortant < 2)
					continue;

			for (arete2=0;arete2<g->les_aretes.nb;arete2++)
			{
				if (g->les_aretes.liste[arete2].noeud_depart == j
					&& g->les_aretes.liste[arete2].noeud_arrivee == i)
				{
					k = graphe_nouveau_noeud(g);

					g->les_noeuds.liste[k].chaine = stradd("do\n{\n",
						tabadd(g->les_noeuds.liste[i].chaine),
						"}\nwhile (",
						g->les_noeuds.liste[j].chaine,
						");\n",NULL);

					printf("transforme do { %d } while (%d) en %d\n",
						g->les_noeuds.liste[i].no_noeud,
						g->les_noeuds.liste[j].no_noeud,
						g->les_noeuds.liste[k].no_noeud);

					graphe_enlever_arete(g,arete1);
					if (arete2 > arete1) arete2--; /* petit bug */
					graphe_enlever_arete(g,arete2);
					graphe_remplacer_noeud(g,i,k);
					graphe_remplacer_noeud(g,j,k);

					return 1;
				}
			}
		}
	}

	return 0;
}

/* on essaye de reconnaitre une construction du style for (;;) { } */

int reconnaitre_for_infini(struct graphe *g,int i)
{
	int	arete;

	/* on doit avoir un seul arc sortant de i et celui ci doit
		aller vers i lui-meme */

	if (g->les_noeuds.liste[i].nb_arc_sortant != 1)
		return 0;

	for (arete=0;arete<g->les_aretes.nb;arete++)
	{
		if (g->les_aretes.liste[arete].noeud_depart == i
			&& g->les_aretes.liste[arete].noeud_arrivee == i)
		{
			g->les_noeuds.liste[i].chaine = stradd("for (;;)\n{\n",
				tabadd(g->les_noeuds.liste[i].chaine),"}\n",
					NULL);
			graphe_enlever_arete(g,arete);
			return 1;
		}
	}

	return 0;
}

/* on essaye de reconnaitre les returns. En fait, le compilo ne genere
pas de return lorsque l'on ecrit un return x; en plein milieu d'une
boucle, mais un jump vers le dernier bloc (celui qui contient le
ret). Or ces jumps faussent toute la structure du programme, on
remplace donc des noeuds (i->j) avec j=ret par (i;j; return;)

Il existe peut-etre une meilleure strategie. Oui, on regarde si i ne
possede pas de successeurs (nb_arc_sortant == 0) dans ce cas il s'agit
surement d'un return. Si ce noeud possede plusieurs predecesseurs,
alors on duplique ce noeud et on change les arcs.

*/

int reconnaitre_return(struct graphe *g,int i)
{
	int	arete;
	int	j,k;

	if (g->les_noeuds.liste[i].nb_arc_sortant != 0
		|| g->les_noeuds.liste[i].nb_arc_entrant < 2)
		return 0;

	printf("return en %d\n",
		g->les_noeuds.liste[i].no_noeud);

	/* pas bo */
	g->les_noeuds.liste[i].nb_arc_entrant = 0;
	g->les_noeuds.liste[i].nb_arc_sortant = 0;

	for (arete=0;arete<g->les_aretes.nb;arete++)
	{
		if (g->les_aretes.liste[arete].noeud_arrivee == i)
		{
			j =  g->les_aretes.liste[arete].noeud_depart;
			k =graphe_nouveau_noeud(g);

			printf("modification de l'arete (%d->%d) en (%d,%d)\n",
				g->les_noeuds.liste[j].no_noeud,
				g->les_noeuds.liste[i].no_noeud,
				g->les_noeuds.liste[j].no_noeud,
				g->les_noeuds.liste[k].no_noeud);

			g->les_noeuds.liste[k].chaine = stradd(
				g->les_noeuds.liste[i].chaine,"return;\n",
				NULL);
			g->les_aretes.liste[arete].noeud_arrivee = k;

			g->les_noeuds.liste[k].nb_arc_entrant = 1;
		}
	}

	return 1;
}
	

/* on essaye de reconnaitre des constructions elementaires a partir d'un noeud
	racine */

void reconnaitre_programme(struct graphe *g)
{
	int result;
	int i;

	/* on applique cette transformation qu'une seule fois, car
		elle duplique du code, et on veut eviter de dupliquer
		du code de maniere incontrolable */

	reconnaitre_return(g,i);

	do
	{
		result = 0;
		for (i=0;i<g->les_noeuds.nb;i++)
		{
			printf("on essaye le noeud %d\n",
				g->les_noeuds.liste[i].no_noeud);
			if (reconnaitre_composition(g,i))
				result ++;
			if (reconnaitre_if_then(g,i))
				result ++;
			if (reconnaitre_while(g,i))
				result ++;
			if (reconnaitre_do_while(g,i))
				result ++;
			if (reconnaitre_for_infini(g,i))
				result ++;
			if (reconnaitre_if_then_else(g,i))
				result ++;
		}
		graphe_ecrire(stdout,g);
	}
	while (result > 0);

	if (g->les_aretes.nb == 0)
	{
		printf("on a gagne,le resultat final est le noeud %d\n",
			g->les_noeuds.liste[g->noeud_depart].no_noeud);
	}
	else
		printf("on a perdu, ce graphe n'est pas reconnu\n");
}

void usage()
{
	printf("usage: traducteur_3 graph-file.g\n");
	exit(-1);
}

/* ======================= PROGRAMME PRINCIPAL ============================== */

int main(int argc,char *argv[])
{
	struct graphe g;
	const char *file = NULL;
	int i;
	/* struct liste_entier mes_noeuds; */

	for (i=1;i<argc;i++)
	{
		if (file == NULL)
			file = argv[i];
		else
			usage();
	}

	if (file == NULL)
		usage();

	if (!graphe_lire(file,&g))
		return -1;

	printf("graphe initial:\n");
	graphe_ecrire(stdout,&g);

/*	printf("sous_graphe {6, 7, 8, 9, 10 }:\n");

	liste_entier_init(&mes_noeuds);
	i = 6;
	liste_entier_ajouter(&mes_noeuds,&i);
	i = 7;
	liste_entier_ajouter(&mes_noeuds,&i);
	i = 8;
	liste_entier_ajouter(&mes_noeuds,&i);
	i = 9;
	liste_entier_ajouter(&mes_noeuds,&i);
	i = 10;
	liste_entier_ajouter(&mes_noeuds,&i);

	construire_sous_graphe(&g2,&g,&mes_noeuds);
	graphe_ecrire(stdout,&g2);
*/

	graphe_nb_arc(&g);

	reconnaitre_programme(&g);
/*	graphe_ecrire(stdout,&g); */

	/* calculer_suite_graphe(&g); */
	graphe_done(&g);

/*	liste_entier_done(&mes_noeuds);
	graphe_done(&g2);
*/

	return 0;
}