/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * MatricesMaxPlus.c Jean-Eric Pin 07/12/96 *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include <ctype.h> #include <limits.h> #include "Globales.h" #include "Main.h" #include "InitiauxFinaux.h" #include "Matrices.h" #include "MatricesMaxPlus.h" #include "Memoire.h" #include "Utilitaires.h" extern unsigned short NbEtats, NbLettres, PartiePointee, InitiauxDejaSpecifies, FinauxDejaSpecifies; extern unsigned long Periode, Seuil; extern element *Generateurs; extern unsigned long TailleElement; extern char **Messages; /****************** * * Ecrete. OK * ******************/ long Ecrete(long x) { if (x > Seuil) x = Seuil; return(x); } /****************** * * PlusMinMax. OK * ******************/ long PlusMinMax(long x, long y) { if ((x == LONG_MAX) || (y == LONG_MAX)) return(LONG_MAX); if ((x == LONG_MIN) || (y == LONG_MIN)) return(LONG_MIN); return(x + y); } /**************************************************** * * EntreeSemiAnneauMaxPlusTropical. OK * ****************************************************/ void EntreeSemiAnneauMaxPlusTropical(void) { printf("%s\n", Messages[M_Semiring_minus_infinity]); /* Semianneau {-infini, 0, 1, ..., s} ou s est le seuil */ EntreeSeuil(); Periode = 0; } /**************************************************** * * EntreeSemiAnneauMaxPlusTropical. OK * ****************************************************/ void EntreeSemiAnneauMinPlusTropical(void) { printf("%s\n", Messages[M_Semiring_plus_infinity]); /* Semianneau {0, 1, ..., s, +infini} ou s est le seuil */ EntreeSeuil(); Periode = 0; } /**************************************************** * * EntreeMatricesMaxPlus. OK * ****************************************************/ void EntreeMatricesMaxPlus(void) { short p, q; lettre a; static char s[] = " "; printf("%s ", Messages[M_Size_matrices_question_mark]); /* Taille des matrices ? */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } TailleElement = NbEtats * NbEtats * sizeof(short); AlloueMemoireGenerateurs(); printf("%s\n", Messages[M_Type_minus]); /* Taper % pour "- infini" */ for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%s", s) != 1) { printf("scanf error\n"); exit(1); } if (s[0] == '%') ((Matrice)Generateurs[a])[p][q] = LONG_MIN; else ((Matrice)Generateurs[a])[p][q] = atol(s); } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /**************************************************** * * EntreeMatricesMinPlus. OK * ****************************************************/ void EntreeMatricesMinPlus(void) { short p, q; lettre a; static char s[] = " "; printf("%s ", Messages[M_Size_matrices_question_mark]); /* printf("Taille des matrices ? "); */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } TailleElement = NbEtats * NbEtats * sizeof(short); AlloueMemoireGenerateurs(); printf("%s\n", Messages[M_Type_plus]); /* Taper % pour "+ infini" */ for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%s", s) != 1) { printf("scanf error\n"); exit(1); } if (s[0] != '%') ((Matrice)Generateurs[a])[p][q] = atol(s); else ((Matrice)Generateurs[a])[p][q] = LONG_MAX; } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /**************************************************** * * EntreeMatricesMaxPlusTropicales. OK * ****************************************************/ void EntreeMatricesMaxPlusTropicales(void) { short p, q; lettre a; static char s[] = " "; EntreeSemiAnneauMaxPlusTropical(); printf("%s ", Messages[M_Size_matrices_question_mark]); /* Taille des matrices ? */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } TailleElement = NbEtats * NbEtats * sizeof(short); AlloueMemoireGenerateurs(); printf("%s\n", Messages[M_Type_minus]); /* Taper % pour "- infini" */ for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%s", s) != 1) { printf("scanf error\n"); exit(1); } if (s[0] == '%') ((Matrice)Generateurs[a])[p][q] = LONG_MIN; else ((Matrice)Generateurs[a])[p][q] = Ecrete(atol(s)); } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /**************************************************** * * EntreeMatricesMinPlusTropicales. OK * ****************************************************/ void EntreeMatricesMinPlusTropicales(void) { short p, q; lettre a; static char s[] = " "; EntreeSemiAnneauMinPlusTropical(); printf("%s ", Messages[M_Size_matrices_question_mark]); /* printf("Taille des matrices ? "); */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } TailleElement = NbEtats * NbEtats * sizeof(short); AlloueMemoireGenerateurs(); printf("%s\n", Messages[M_Type_plus]); /* Taper % pour "+ infini" */ for (a = 0; a < NbLettres; a++) { for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { printf("%c[%d,%d] = ", a + 97, p + 1, q + 1); if (scanf("%s", s) != 1) { printf("scanf error\n"); exit(1); } if (s[0] != '%') ((Matrice)Generateurs[a])[p][q] = Ecrete(atol(s)); else ((Matrice)Generateurs[a])[p][q] = LONG_MAX; } printf("\n"); } if (PartiePointee && (!FinauxDejaSpecifies)) EntreeEtatsInitiauxFinaux(); } /************************************ * * NormeMatricesMaxPlus (calcule le Max des coefficients) * ************************************/ long NormeMatricesMaxPlus(Matrice x) { register short p, q; long Max = LONG_MIN; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) if (Max < x[p][q]) Max = x[p][q]; return Max; } /************************************ * * ProduitMatricesMaxPlus * ************************************/ void ProduitMatricesMaxPlus(element x, element y, element xy) { register short p, q, r; long v; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = LONG_MIN; for (r = 0; r < NbEtats; r++) v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q])); ((Matrice)xy)[p][q] = v ; } } /************************************ * * ProduitMatricesMinPlus * ************************************/ void ProduitMatricesMinPlus(element x, element y, element xy) { register short p, q, r; long v; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = LONG_MAX; for (r = 0; r < NbEtats; r++) v = Min(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q])); ((Matrice)xy)[p][q] = v; } } /************************************ * * ProduitMatricesMaxPlusTropicales * ************************************/ void ProduitMatricesMaxPlusTropicales(element x, element y, element xy) { register short p, q, r; long v; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = LONG_MIN; for (r = 0; r < NbEtats; r++) v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q])); ((Matrice)xy)[p][q] = Ecrete(v) ; } } /************************************ * * ProduitMatricesMinPlusTropicales * ************************************/ void ProduitMatricesMinPlusTropicales(element x, element y, element xy) { register short p, q, r; long v; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = LONG_MAX; for (r = 0; r < NbEtats; r++) v = Min(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q])); ((Matrice)xy)[p][q] = Ecrete(v) ; } } /************************************ * * ProduitMatProjectivesMaxPlus * ************************************/ void ProduitMatMaxPlusProjectives(element x, element y, element xy) { register short p, q, r; long v, Norme; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) { v = LONG_MIN; for (r = 0; r < NbEtats; r++) v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q])); ((Matrice)xy)[p][q] = v; } Norme = NormeMatricesMaxPlus((Matrice)xy); for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) if (((Matrice)xy)[p][q] != LONG_MIN) ((Matrice)xy)[p][q] -= Norme; } /******************************************************** * * FaireIdentiteMatricesMaxPlus : Initialisation de l'identite * ********************************************************/ void FaireIdentiteMatricesMaxPlus(element x) { short p, q; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) ((Matrice)x)[p][q] = LONG_MIN; for (p = 0; p < NbEtats; p++) ((Matrice)x)[p][p] = 0; } /******************************************************** * * FaireIdentiteMatricesMinPlus : Initialisation de l'identite * ********************************************************/ void FaireIdentiteMatricesMinPlus(element x) { short p, q; for (p = 0; p < NbEtats; p++) for (q = 0; q < NbEtats; q++) ((Matrice)x)[p][q] = LONG_MAX; for (p = 0; p < NbEtats; p++) ((Matrice)x)[p][p] = 0; } /**************************************************** * * SortieMatricesMaxPlus : Sortie d'un element. OK * ****************************************************/ void SortieMatricesMaxPlus(element x) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MIN) printf(" -%% "); else printf("%3ld ", ((Matrice)x)[p][q]); printf("|"); } printf("\n"); } /**************************************************** * * SortieMatricesMaxPlusTropicales : Sortie d'un element. OK * ****************************************************/ void SortieMatricesMaxPlusTropicales(element x) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MIN) printf(" -%% "); else printf("%3ld ", ((Matrice)x)[p][q]); printf("|"); } printf("\n"); } /**************************************************** * * SortieMatricesMinPlus : Sortie d'un element. OK * ****************************************************/ void SortieMatricesMinPlus(element x) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MAX) printf(" +%% "); else printf("%3ld ", ((Matrice)x)[p][q]); printf("|"); } printf("\n"); } /**************************************************** * * SortieMatricesMinPlusTropicales : Sortie d'un element. OK * ****************************************************/ void SortieMatricesMinPlusTropicales(element x) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] >= Seuil) printf("%3ld ", Seuil); else printf("%3ld ", ((Matrice)x)[p][q]); printf("|"); } printf("\n"); } /**************************************************** * * SortieLaTeXMatricesMaxPlus : Sortie d'un element. OK * ****************************************************/ void SortieLaTeXMatricesMaxPlus(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MIN) fprintf(MyFile, "&$-\\infty$ "); else fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]); } fprintf(MyFile, "\n"); } /**************************************************** * * SortieLaTeXMatricesMaxPlusTropicales : Sortie d'un element. OK * ****************************************************/ void SortieLaTeXMatricesMaxPlusTropicales(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MIN) fprintf(MyFile, "&$-\\infty$ "); else fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]); } fseek(MyFile, -2, SEEK_CUR); fprintf(MyFile, "\n"); } /**************************************************** * * SortieLaTeXMatricesMinPlus : Sortie d'un element. OK * ****************************************************/ void SortieLaTeXMatricesMinPlus(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] == LONG_MAX) fprintf(MyFile, "&$+\\infty$ "); else fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]); } fseek(MyFile, -2, SEEK_CUR); fprintf(MyFile, "\n"); } /**************************************************** * * SortieLaTeXMatricesMinPlusTropicales : Sortie d'un element. OK * ****************************************************/ void SortieLaTeXMatricesMinPlusTropicales(element x, FILE *MyFile) { short p, q; for (p = 0; p < NbEtats; p++) { for (q = 0; q < NbEtats; q++) if (((Matrice)x)[p][q] >= Seuil) fprintf(MyFile, "&$+\\infty$ "); else fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]); } fseek(MyFile, -2, SEEK_CUR); fprintf(MyFile, "\n"); }