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