/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * Syntactique.c Jean-Eric Pin 08/04/97 *-------------------------------------------------------------------*/ /*------------------------------------------------------------------- * Calcul du preordre syntactique <=P d'une partie P d'un monoide M. * Ce preordre est defini comme suit. On a u <=P v ssi * pour tout x, y dans M, xvy dans P entraine xuy dans P. * L'algorithme de calcul est decrit dans l'article de Froidure et Pin. * * (1) On construit le graphe G dont les sommets sont les couples (u, v) * d'elements de M et dont les aretes sont de la forme * (ua, va) --> (u, v) ou (au, av) --> (u, v) * * (2) On etiquette chaque sommet (u, v) comme suit : * (0, 1) si u n'est pas dans P et si v est dans P * (1, 0) si u est dans P et si v n'est pas dans P * (1, 1) sinon * Le codage de l'etiquette se fait dans les deux bits de droite de Graphe[u][v].Label * * (3) On effectue un parcours en profondeur d'abord de G, en partant * successivement de chaque sommet etiquete (0, 1), et on met a 0 * la premiere composante de l'etiquette des sommets visites. * Le cinquieme bit de Graphe[u][v].Label est utilise pour marquer les etats * durant ce parcours. * * (4) On effectue un parcours en profondeur d'abord de G, en partant * successivement de chaque sommet etiquete (0, 0) ou (1, 0), et on met a 0 * la seconde composante de l'etiquette des sommets visites. * Le quatrieme bit de Graphe[u][v].Label est utilise pour marquer les etats * durant ce parcours. * * (5) L'etiquette de chaque sommet donne un codage du preordre syntactique * (1, 1) si u =P v * (1, 0) si u <P v * (0, 1) si u >P v * (0, 0) si u et v sont incomparables * Le codage se fait dans les deux bits de droite de Graphe[u][v].Label * * (6) Pour extraire le squelette transitif, on elimine les relations * u < w pour lesquelles il existe v tel que u < v et v < w. * Le codage s'effectue dans le troisieme bit (en partant de la droite) * de Graphe[u][v].Label * *---------------------------------------------------------------------------*/ #include <stdlib.h> #include <stdio.h> #include <memory.h> #include "Globales.h" #include "Main.h" #include "Initialisation.h" #include "InitiauxFinaux.h" #include "Memoire.h" #include "Sortie.h" #include "SortieLaTeX.h" #include "Syntactique.h" #include "Transitions.h" extern unsigned short NbLettres, NbEtats, PossedeUnNeutre; extern unsigned long CalculsEffectues; extern unsigned long NbElements; extern EntreePartie_ EntreePartie; extern char **Messages; extern info *Table; /* La table contenant les informations sur les elements */ extern element *TableDesValeurs; /* Les valeurs des elements du semigroupe dans l'univers. */ infoSommet **Graphe; /* Le graphe syntactique */ Liste2Numeros PileGraphe; /* Pile utilisee pour le parcours en profondeur du graphe. */ /*************************************************************************** * * CreationGraphe. * * On cree le graphe dont M x M est l'ensemble de sommets et les aretes sont * de la forme (ua, va) -> (u, v) ou (au, av) -> (u, v), avec a dans A. * On calcule au passage le degre sortant de chaque sommet. * ***************************************************************************/ void CreationGraphe(void) { unsigned long u, v, ua, va, au, av; lettre a; Liste2Numeros Temporaire; for (u = IDENTITE; u <= NbElements; u++) for (v = IDENTITE; v <= NbElements; v++) { for (a = 0; a < NbLettres; a++) /* tant pis pour les doublons ! */ { ua = Table[u].Produits[a].D & ~EST_REDUIT; va = Table[v].Produits[a].D & ~EST_REDUIT; Temporaire = AlloueMemoireArete(); Temporaire->u = u; Temporaire->v = v; Temporaire->suivant = Graphe[ua][va].Aretes; Graphe[ua][va].Aretes = Temporaire; au = Table[u].Produits[a].G; av = Table[v].Produits[a].G; Temporaire = AlloueMemoireArete(); Temporaire->u = u; Temporaire->v = v; Temporaire->suivant = Graphe[au][av].Aretes; Graphe[au][av].Aretes = Temporaire; } if ((Table[u].Statut & EST_DANS_P) == (Table[v].Statut & EST_DANS_P)) Graphe[u][v].Label = CHAR_TROIS; /* 11 en binaire, si (u, v \in P ou si u, v \notin P) */ else if ((Table[u].Statut & EST_DANS_P) > (Table[v].Statut & EST_DANS_P)) Graphe[u][v].Label = CHAR_DEUX; /* 10 si (u \in P et v \notin P) */ else Graphe[u][v].Label = CHAR_UN; /* 01 si (u \notin P et v \in P) */ } } /********************** * * InitPileGraphe. * **********************/ void InitPileGraphe(Liste2Numeros MyPileGraphe) { unsigned long n; for (n = 0; n < NbElements * NbElements; n++) MyPileGraphe[n].suivant = NULL; } /*************************************************************************** * * PremierParcoursGraphe. * * On effectue un parcours en profondeur d'abord de G en partant du sommet (u0, v0). * ***************************************************************************/ void PremierParcoursGraphe(unsigned long u0, unsigned long v0) { register unsigned long u, v, u1, v1; register long i = 0; struct Wagon2Numeros *p; PileGraphe[0].u = u0; PileGraphe[0].v = v0; PileGraphe[0].suivant = Graphe[u0][v0].Aretes; do { u = PileGraphe[i].u; /* Sommet courant (u, v) */ v = PileGraphe[i].v; p = PileGraphe[i].suivant; Graphe[u][v].Label |= PARCOURS_UN; /* Premiere visite dans (u, v) */ if (p != NULL) { u1 = p->u; /* (u1, v1) voisin courant de (u, v) */ v1 = p->v; if ((Graphe[u1][v1].Label & PARCOURS_UN) == 0) /* Sommet non marque : on descend */ { Graphe[u1][v1].Label &= ~CHAR_DEUX; PileGraphe[++i].suivant = Graphe[u1][v1].Aretes; PileGraphe[i].u = u1; PileGraphe[i].v = v1; } else /* Sommet marque : on prend le sommet voisin suivant */ PileGraphe[i].suivant = p->suivant; } else /* Plus rien a explorer a ce niveau : on met a jour et on remonte */ i--; } while (i != -1); } /*************************************************************************** * * SecondParcoursGraphe. * * On effectue un parcours en profondeur d'abord de G en partant du sommet (u0, v0). * ***************************************************************************/ void SecondParcoursGraphe(unsigned long u0, unsigned long v0) { register unsigned long u, v, u1, v1; register long i = 0; struct Wagon2Numeros *p; PileGraphe[0].u = u0; PileGraphe[0].v = v0; PileGraphe[0].suivant = Graphe[u0][v0].Aretes; do { u = PileGraphe[i].u; /* Sommet courant (u, v) */ v = PileGraphe[i].v; p = PileGraphe[i].suivant; Graphe[u][v].Label &= ~CHAR_UN; Graphe[u][v].Label |= PARCOURS_DEUX; /* Premiere visite dans (u, v) */ if (p != NULL) { u1 = p->u; /* (u1, v1) voisin courant de (u, v) */ v1 = p->v; if ((Graphe[u1][v1].Label & PARCOURS_DEUX) == 0) /* Sommet non marque : on descend */ { PileGraphe[++i].suivant = Graphe[u1][v1].Aretes; PileGraphe[i].u = u1; PileGraphe[i].v = v1; } else /* Sommet marque : on prend le sommet voisin suivant */ PileGraphe[i].suivant = p->suivant; } else /* Plus rien a explorer a ce niveau : on met a jour et on remonte */ i--; } while (i != -1); } /*************************************************************************** * * CalculSyntactique. Voir documentation en debut de fichier. * ***************************************************************************/ void CalculSyntactique(void) { unsigned long u, v; if (!(CalculsEffectues & CALCUL_SYNTACTIQUE)) { AlloueMemoireGraphe(); CreationGraphe(); PileGraphe = AlloueMemoirePileGraphe(NbElements * NbElements); for (u = IDENTITE; u <= NbElements; u++) if ((Table[u].Statut & EST_DANS_P) == 0) /* Si u n'est pas dans P */ { for (v = IDENTITE; v <= NbElements; v++) if ((Graphe[u][v].Label & (PARCOURS_UN | CHAR_TROIS)) == CHAR_UN) /* Si (u, v) n'a pas encore ete visite et si v est dans P */ { InitPileGraphe(PileGraphe); PremierParcoursGraphe(u, v); } } for (v = IDENTITE; v <= NbElements; v++) if ((Table[v].Statut & EST_DANS_P) == 0) /* Si v n'est pas dans P */ { for (u = IDENTITE; u <= NbElements; u++) if ((Graphe[u][v].Label & (PARCOURS_DEUX | CHAR_UN)) == 0) /* Si (u, v) n'a pas encore ete visite et si l'etiquette de (u, v) est (?, 0) */ { InitPileGraphe(PileGraphe); SecondParcoursGraphe(u, v); } } CalculsEffectues |= CALCUL_SYNTACTIQUE; } } /*************************************************************************** * * CalculSqueletteSyntactique. Calcul du squelette du preordre syntactique. * On elimine les relations obtenues par transitivite * ***************************************************************************/ void CalculSqueletteSyntactique(void) { unsigned long u, v, w; if (!(CalculsEffectues & CALCUL_SYNTACTIQUE)) CalculSyntactique(); for (u = IDENTITE + !PossedeUnNeutre; u <= NbElements; u++) for (v = u + 1; v <= NbElements; v++) for (w = v + 1; w <= NbElements; w++) if ((Graphe[v][w].Label & CHAR_TROIS) == CHAR_DEUX) /* Si v < w */ { if ((Graphe[u][v].Label & CHAR_TROIS) == CHAR_DEUX) /* si u < v */ Graphe[u][w].Label |= TRANSITIF; /* u < w */ else if ((Graphe[u][w].Label & CHAR_TROIS) == CHAR_UN) /* si w < u */ Graphe[u][v].Label |= TRANSITIF; /* v < u */ } else if ((Graphe[v][w].Label & CHAR_TROIS) == CHAR_UN) /* Si w < v */ { if ((Graphe[u][w].Label & CHAR_TROIS) == CHAR_DEUX) /* si u < w */ Graphe[u][v].Label |= TRANSITIF; /* u < v */ else if ((Graphe[u][v].Label & CHAR_TROIS) == CHAR_UN) /* si v < u */ Graphe[u][w].Label |= TRANSITIF; /* w < u */ } }