/*************************************** * * * Copyright (c) 2006 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /**************************************************** * * Blocs.c Jean-Eric Pin 21/08/2006 * ****************************************************/ #include <stdlib.h> #include <stdio.h> #include <string.h> #include "Main.h" #include "Memoire.h" #include "Initialisation.h" #include "DclassesIteratif.h" #include "Sortie.h" #include "Blocs.h" extern info *Table; extern info2 *Table2; extern unsigned long *TableIdempotents; extern unsigned short NbLettres, PossedeUnNeutre, TypeCalcul; extern unsigned long CalculsEffectues; extern unsigned long NbElements, NbRclasses, NbLclasses, NbDclasses, NbHclasses, NbIdempotents, DernierMot; unsigned long *B, *Taille; /**************************************************** * * CalculBlocs. OK Aout 2006 * ****************************************************/ /********************************************************************************* * Ce calcul consiste a determiner les composantes connexes du graphe bipartite * dont les sommets sont R U L (R = ensemble des R-classes, L = ensemble des L-classes) * et dont les arcs sont donnes par les idempotents: arc (r,l) si l'intersection * de r et l contient un idempotent. * On utilise cette fois "Union-Find" *********************************************************************************/ unsigned long Trouver(unsigned long x) { unsigned long r; r = x; while (B[r] != r) r = B[r]; /* remonte l'arbre de x */ while (B[x] != x) { B[x] = r; /* x devient fils de r */ x = B[x]; } return r; } void Union(unsigned long x, unsigned long y) { unsigned long r, s; r = Trouver(x); s = Trouver(y); if (Taille[r] > Taille[s]) { B[s] = r; Taille[r] = Taille[r] + Taille[s]; } else { B[r] = s; Taille[s] = Taille[r] + Taille[s]; } } void CalculBlocs(void) { unsigned long i, r, l, n; unsigned long TailleTable = 0; unsigned short Longueur = 0; if (!(CalculsEffectues & CALCUL_BLOCS)) { TailleTable = NbRclasses + NbLclasses; B = AlloueMemoireTableau(TailleTable); Taille = AlloueMemoireTableau(TailleTable); for (i = 0; i < TailleTable; i++) { B[i] = i; Taille[i] = 1; } if (CalculsEffectues & CALCUL_LISTE_IDEMPOTENTS) for (i = 0; i < NbIdempotents; i++) { r = Trouver(Table2[TableIdempotents[i]].Rclasse - 1); l = Trouver(NbRclasses + Table2[TableIdempotents[i]].Lclasse - 1); Union(r, l); } else for (i = IDENTITE + !PossedeUnNeutre; i <= NbElements; i++) { if (Table[i].Statut & IDEMPOTENT) { r = Trouver(Table2[i].Rclasse - 1); l = Trouver(NbRclasses + Table2[i].Lclasse - 1); Union(r, l); } } } for (r = 0; r < TailleTable; r++) Trouver(r); for (n = IDENTITE; n != DernierMot; ) { n = Table[n].Suivant; Longueur = Table[n].Longueur; r = Table2[n].Rclasse-1; } printf("\n"); free(Taille); CalculsEffectues |= CALCUL_BLOCS; /* On prend note : le calcul des blocs est termine */ }