src/warshall.c

   1 /* Generate transitive closure of a matrix,
   2    Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 #include "system.h"
  23 #include "getargs.h"
  24 #include "warshall.h"
  25
  26 /*-------------------------------------------------------------.
  27 | Given n by n matrix of bits R, modify its contents to be the |
  28 | transive closure of what was given.                          |
  29 `-------------------------------------------------------------*/
  30
  31 static void
  32 bitmatrix_print (const char *title, unsigned *matrix, size_t size)
  33 {
  34   size_t i, j;
  35   size_t rowsize = WORDSIZE (size) * sizeof (unsigned);
  36 #define ROW(Num) ((unsigned *) ((char *) matrix + ((Num) * rowsize)))
  37
  38   /* Title. */
  39   fprintf (stderr, "%s BEGIN\n", title);
  40
  41   /* Column numbers. */
  42   fputs ("   ", stderr);
  43   for (i = 0; i < size; ++i)
  44     putc (i / 10 ? '0' + i / 10 : ' ', stderr);
  45   putc ('\n', stderr);
  46   fputs ("   ", stderr);
  47   for (i = 0; i < size; ++i)
  48     fprintf (stderr, "%d", i % 10);
  49   putc ('\n', stderr);
  50
  51   /* Bar. */
  52   fputs ("  +", stderr);
  53   for (i = 0; i < size; ++i)
  54     putc ('-', stderr);
  55   fputs ("+\n", stderr);
  56
  57   /* Contents. */
  58   for (i = 0; i < size; ++i)
  59     {
  60       fprintf (stderr, "%2d|", i);
  61       for (j = 0; j < size; ++j)
  62         fputs (BITISSET (ROW (i), j) ? "1" : " ", stderr);
  63       fputs ("|\n", stderr);
  64     }
  65
  66   /* Bar. */
  67   fputs ("  +", stderr);
  68   for (i = 0; i < size; ++i)
  69     putc ('-', stderr);
  70   fputs ("+\n", stderr);
  71
  72   /* End title. */
  73   fprintf (stderr, "%s END\n\n", title);
  74 }
  75
  76 #define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize))
  77
  78 static void
  79 TC (unsigned *R, int n)
  80 {
  81   int rowsize = WORDSIZE (n) * sizeof (unsigned);
  82   int i, j, k;
  83
  84   if (trace_flag)
  85     bitmatrix_print ("TC: Input", R, n);
  86
  87   /* R (J, I) && R (I, K) => R (J, K).
  88      I *must* be the outter loop. */
  89
  90   for (i = 0; i < n; ++i)
  91     for (j = 0; j < n; ++j)
  92       if (BITISSET (R (j), i))
  93         for (k = 0; k < n; ++k)
  94           if (BITISSET (R (i), k))
  95             SETBIT (R (j), k);
  96
  97   if (trace_flag)
  98     bitmatrix_print ("TC: Output", R, n);
  99 }
 100
 101
 102 /*---------------------------------------------------------------.
 103 | Reflexive Transitive Closure.  Same as TC and then set all the |
 104 | bits on the diagonal of R.                                     |
 105 `---------------------------------------------------------------*/
 106
 107 void
 108 RTC (unsigned *R, int n)
 109 {
 110   int rowsize = WORDSIZE (n) * sizeof (unsigned);
 111   int i;
 112
 113   TC (R, n);
 114   for (i = 0; i < n; ++i)
 115     SETBIT (R (i), i);
 116 }