/***************************************
* *
* Copyright (c) 1998 Jean-Eric Pin *
* All rights reserved. *
* *
* TAB = 2 spaces *
* *
***************************************/
/*-------------------------------------------------------------------
* Dclasses.c Jean-Eric Pin 07/12/96
*-------------------------------------------------------------------
* Probleme majeur : les procedures recursives provoquent des erreurs
* 28 : "Stack has moved into application heap"
* La solution sur Mac 68k est SetApplLimit(GetApplLimit() - 16384)
* pour augmenter la pile de 16k. Cependant, pour des graphes tres
* grands, la pile augmente trop vite (80 octets par noeud semble-t-il)
* d'ou la decision des procedures iteratives.
*-------------------------------------------------------------------
* Algorithme de calcul des D-classes. Principe general :
* Les R-classes sont les composantes fortement connexes du graphe de Cayley droit
* Les L-classes sont les composantes fortement connexes du graphe de Cayley gauche
* On calcule les numeros de R-classes en utilisant l'algorithme de Tarjan
* (voir ci-dessous). On calcule ensuite les numeros de L-classes par un parcours
* du graphe de Cayley gauche. On gere simultanement un tableau TableRD qui donne le
* numero de D-classe de chaque R-classe. S'il y a par exemple 7 R-classes telles
* que les R-classes 1 et 4, d'une part, 2, 3 et 6 d'autre part, soient dans la meme
* D-classe, le tableau final aura la forme suivante :
* ----------------------------
* | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
* -----------------------------
* | 1 | 2 | 2 | 1 | 3 | 2 | 4 |
* -----------------------------
*
* Au depart, le tableau est initialise a 0.
* ----------------------------
* | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
* -----------------------------
* | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
* -----------------------------
*
* Lors du calcul des L-classes, on regarde si le sommet courant s est point d'entree
* d'une L-classe. Si c'est le cas, on regarde le numero de D-classe d = TableRD[R(s)]
* ou R(s) est le numero de R-classe de s. L'idee est de propager ce numero d dans toute
* la L-classe de s. Si d = 0, on commence une nouvelle D-classe. On incremente alors
* le nombre courant de D-classes, et on attribue a d cette nouvelle valeur. Il reste
* alors a effectuer le parcours de la L-classe.
*
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Main.h"
#include "Memoire.h"
#include "Initialisation.h"
#include "DclassesIteratif.h"
extern info *Table;
extern info2 *Table2;
extern unsigned short NbLettres, PossedeUnNeutre, TypeCalcul, CalculsEffectues;
extern numero NbRclasses, NbLclasses, NbDclasses, NbLclassesMinimales, TailleRIdealMinimal;
elementpile *Pile;
numero *PileComposanteConnexe;
numero *TableRD;
static unsigned short EstElementRegulier;
/***************************************************************************
*
* ParcoursRAttache. Determine les points d'attache du graphe de Cayley
* puis les composantes fortement connexes du graphe, ce qui donne les R-classes.
* On utilise l'algorithme de Tarjan.
*
* s = &Table[s], sa_ = &Table[sa], as = &Table[as]
*
* On effectue un parcours en profondeur d'abord.
* Le point d'attache de s est le minimum de son numero de parcours, des points
* d'attache de ses fils dans l'arbre de parcours et des extremites des arcs transverses
* ou de retour d'origine s.
* Le drapeau R_VISITE est mis a 1 lors du premier passage. Cette information est
* utilisee pour connaitre la nature d'un arc :
* - Arc de descente de s vers sa : (Table2[s].NumeroDeParcours < (*sa_).NumeroDeParcours)
* - Arc retour de s vers sa : (R_VISITE = 0) en sa
*
* A l'issue de ParcoursRAttache, les points d'entree dans une R-classe sont
* ceux egaux a leur point d'attache.
*
* Gestion de la pile : chaque niveau de pile contient une lettre et la
* valeur cumulee du mot de pile situe dessous. Par exemple, si la pile est :
* --------------------------------
* | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
* --------------------------------
* | a | b | a | b | b | a | b | a |
* --------------------------------
*
* le niveau 7 contiendra aussi l'adresse de l'element correspondant a ababbab.
* A la fin du parcours, les champs Pile[i].Lettre sont revenus a 0.
*
***************************************************************************/
void ParcoursRclassesIteratif(void)
{
register lettre a;
register numero i = 0;
register numero sa, s, sk;
numero nPassage = 0;
numero HauteurPile = 0;
NbRclasses = 0;
TailleRIdealMinimal = 0;
Pile[0].Adresse = IDENTITE;
PileComposanteConnexe[0] = 0; /* Sentinelle */
do
{
s = Pile[i].Adresse;
if ((Table2[s].Statut & R_VISITE) == 0)
{
Table2[s].PointDAttache = Table2[s].NumeroDeParcours = ++nPassage;
PileComposanteConnexe[++HauteurPile] = s; /* On empile s sur la pile de la composante connexe */
Table2[s].Statut |= R_VISITE; /* Premiere visite dans s */
}
a = Pile[i].Lettre;
sa = Table[s].Produits[a].D & ~EST_REDUIT;
if ((Table2[sa].Statut & R_VISITE) == 0) /* Si possible, on descend en profondeur. */
Pile[++i].Adresse = sa;
else if (a < (NbLettres - 1)) /* Sinon, on explore les autres branches */
{
if ((Table2[s].NumeroDeParcours < Table2[sa].NumeroDeParcours) && (Table2[sa].PointDAttache < Table2[s].PointDAttache)) /* Arc de descente de s vers sa */
Table2[s].PointDAttache = Table2[sa].PointDAttache;
else if (((Table2[sa].Statut & R_DEJA_CALCULE) == 0) && (Table2[sa].NumeroDeParcours < Table2[s].PointDAttache)) /* Arc de retour de s vers sa */
Table2[s].PointDAttache = Table2[sa].NumeroDeParcours;
Pile[i].Lettre++;
}
else /* Plus rien a explorer a ce niveau : on met a jour et on remonte */
{
if ((Table2[s].NumeroDeParcours < Table2[sa].NumeroDeParcours) && (Table2[sa].PointDAttache < Table2[s].PointDAttache)) /* Arc de descente de s vers sa */
Table2[s].PointDAttache = Table2[sa].PointDAttache;
else if (((Table2[sa].Statut & R_DEJA_CALCULE) == 0) && (Table2[sa].NumeroDeParcours < Table2[s].PointDAttache)) /* Arc de retour de s vers sa */
Table2[s].PointDAttache = Table2[sa].NumeroDeParcours;
if (Table2[s].NumeroDeParcours == Table2[s].PointDAttache) /* Si s est egal a son point d'attache, on a un point d'entree de la R-classe */
{
NbRclasses++;
if (NbRclasses == 1) /* Ideal minimal */
do
{
TailleRIdealMinimal++;
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Rclasse = NbRclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une R-classe */
Table2[sk].Statut |= R_DEJA_CALCULE; /* Le calcul de la R-classe de s est acheve. On peut eliminer ce sommet. */
}
while (sk != s);
else
do
{
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Rclasse = NbRclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une R-classe */
Table2[sk].Statut |= R_DEJA_CALCULE; /* Le calcul de la R-classe de s est acheve. On peut eliminer ce sommet. */
}
while (sk != s);
}
Pile[i--].Lettre = 0;
}
}
while (i != -1); /* Bien que i soit unsigned, i-- s'applique */
}
/* if (Table[s].Statut & IDEMPOTENT) Mise a jour du statut
EstElementRegulier = 1;
if (EstElementRegulier)
Table[s].Statut |= REGULIER;
if (Table2[s].NumeroDeParcours == Table2[s].PointDAttache) Lorsque l'un sommet est egal a son point d'attache, on commence une nouvelle R-classe
EstElementRegulier = 0;
if (((Table[s].Statut & REGULIER) == 0) && ((Table[Table2[s].PointDAttache].Statut & REGULIER) != 0)
Table[s].Statut |= REGULIER; */
/****************************************************
*
* CalculRclasses. OK
*
****************************************************/
void CalculRclassesIteratif(void)
{
Table2 = AlloueMemoireTable2();
Table2[IDENTITE].xOmega = IDENTITE;
Pile = AlloueMemoirePile();
PileComposanteConnexe = AlloueMemoirePileComposanteConnexe();
InitPile(Pile);
InitDrapeaux();
EstElementRegulier = 0;
ParcoursRclassesIteratif();
CalculsEffectues |= CALCUL_R_CLASSES; /* On prend note : le calcul des D-classes est termine */
}
/***************************************************************************
*
* ParcoursLAttache. Determine les points d'attache du graphe de Cayley a gauche
*
***************************************************************************/
void ParcoursLclassesIteratif(void)
{
register lettre a;
register numero i = 0;
register numero as, s, sk;
numero nPassage = 0;
numero HauteurPile = 0;
numero Dclasse;
if (NbLettres == 0) /* Monoide trivial */
{
NbLclasses = 1;
Table2[IDENTITE].Lclasse = 1;
return;
}
NbLclasses = 0;
NbDclasses = 0;
NbLclassesMinimales = 0;
Pile[0].Adresse = IDENTITE;
PileComposanteConnexe[0] = 0; /* Sentinelle */
do
{
s = Pile[i].Adresse;
if ((Table2[s].Statut & L_VISITE) == 0)
{
Table2[s].PointDAttache = Table2[s].NumeroDeParcours = ++nPassage;
PileComposanteConnexe[++HauteurPile] = s; /* On empile s sur la pile de la composante connexe */
Table2[s].Statut |= L_VISITE; /* Premiere visite dans s */
}
a = Pile[i].Lettre;
as = Table[s].Produits[a].G;
if ((Table2[as].Statut & L_VISITE) == 0) /* Si possible, on descend en profondeur. */
Pile[++i].Adresse = as;
else if (a < (NbLettres - 1)) /* Sinon, on explore les autres branches */
{
if ((Table2[s].NumeroDeParcours < Table2[as].NumeroDeParcours) && (Table2[as].PointDAttache < Table2[s].PointDAttache)) /* Arc de descente de s vers as */
Table2[s].PointDAttache = Table2[as].PointDAttache;
else if (((Table2[as].Statut & L_DEJA_CALCULE) == 0) && (Table2[as].NumeroDeParcours < Table2[s].PointDAttache)) /* Arc de retour de s vers as */
Table2[s].PointDAttache = Table2[as].NumeroDeParcours;
Pile[i].Lettre++;
}
else /* Plus rien a explorer a ce niveau : on met a jour et on remonte */
{
if ((Table2[s].NumeroDeParcours < Table2[as].NumeroDeParcours) && (Table2[as].PointDAttache < Table2[s].PointDAttache)) /* Arc de descente de s vers as */
Table2[s].PointDAttache = Table2[as].PointDAttache;
else if (((Table2[as].Statut & L_DEJA_CALCULE) == 0) && (Table2[as].NumeroDeParcours < Table2[s].PointDAttache)) /* Arc de retour de s vers as */
Table2[s].PointDAttache = Table2[as].NumeroDeParcours;
if (Table2[s].NumeroDeParcours == Table2[s].PointDAttache) /* Si s est egal a son point d'attache, on a un point d'entree de la L-classe */
{
NbLclasses++;
Dclasse = TableRD[Table2[s].Rclasse];
if (Dclasse == 0) /* Nouvelle D-classe */
{
NbDclasses++;
if (NbDclasses == 1) /* Ideal minimal */
{
NbLclassesMinimales++;
do
{
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Lclasse = NbLclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une L-classe */
Table2[sk].Statut |= L_DEJA_CALCULE | EST_D_MINIMAL; /* Le calcul de la L-classe de s est acheve. On peut eliminer ce sommet. */
Table2[sk].Dclasse = 1;
TableRD[Table2[sk].Rclasse] = 1;
}
while (sk != s);
}
else /* D-classe autre que l'ideal minimal */
{
do
{
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Lclasse = NbLclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une L-classe */
Table2[sk].Statut |= L_DEJA_CALCULE; /* Le calcul de la L-classe de s est acheve. On peut eliminer ce sommet. */
Table2[sk].Dclasse = NbDclasses;
TableRD[Table2[sk].Rclasse] = NbDclasses;
}
while (sk != s);
}
}
else
{
if (Dclasse == 1) /* Ideal minimal */
{
NbLclassesMinimales++;
do
{
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Lclasse = NbLclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une R-classe */
Table2[sk].Statut |= L_DEJA_CALCULE | EST_D_MINIMAL; /* Le calcul de la L-classe de s est acheve. On peut eliminer ce sommet. */
Table2[sk].Dclasse = 1;
}
while (sk != s);
}
else /* D-classe autre que l'ideal minimal */
{
do
{
sk = PileComposanteConnexe[HauteurPile--];
Table2[sk].Lclasse = NbLclasses; /* On depile : on parcours la composante connexe issue de s, ce qui donne une R-classe */
Table2[sk].Statut |= L_DEJA_CALCULE; /* Le calcul de la L-classe de s est acheve. On peut eliminer ce sommet. */
Table2[sk].Dclasse = Dclasse;
}
while (sk != s);
}
}
}
Pile[i--].Lettre = 0;
}
}
while (i != -1); /* Bien que i soit unsigned, i-- s'applique */
}
/* if (Table[s].Statut & IDEMPOTENT) Mise a jour du statut
EstElementRegulier = 1;
if (EstElementRegulier)
Table[s].Statut |= REGULIER;
if (Table2[s].NumeroDeParcours == Table2[s].PointDAttache) Lorsque l'un sommet est egal a son point d'attache, on commence une nouvelle R-classe
EstElementRegulier = 0;
if (((Table[s].Statut & REGULIER) == 0) && ((Table[Table2[s].PointDAttache].Statut & REGULIER) != 0)
Table[s].Statut |= REGULIER; */
/****************************************************
*
* CalculDclasses. OK
*
****************************************************/
void CalculDclasses(void)
{
if (!(CalculsEffectues & CALCUL_D_CLASSES))
{
if (NbLettres == 0) /* Monoide trivial */
{
NbDclasses = NbRclasses = NbLclasses = 1;
Table2[IDENTITE].Dclasse = Table2[IDENTITE].Rclasse = Table2[IDENTITE].Lclasse = 1;
Table2[IDENTITE].Statut |= EST_D_MINIMAL;
CalculsEffectues |= CALCUL_D_CLASSES; /* On prend note : le calcul des D-classes est termine */
return;
}
CalculRclassesIteratif();
EstElementRegulier = 0;
TableRD = AlloueMemoireTableau(NbRclasses + 1); /* +1, car on met une sentinelle en fond de pile */
ParcoursLclassesIteratif();
if (!PossedeUnNeutre && (TypeCalcul == Semigroupe))
{
NbDclasses--;
NbLclasses--;
NbRclasses--;
}
free(Pile);
free(PileComposanteConnexe);
free(TableRD);
CalculsEffectues |= CALCUL_D_CLASSES; /* On prend note : le calcul des D-classes est termine */
}
/* printf("TailleRIdealMinimal = %u, NbLclassesMinimales = %u, TailleGroupeMinimal = %u\n", TailleRIdealMinimal, NbLclassesMinimales, TailleGroupeMinimal); */
}