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 "warshall.h"
  24
  25 /*-------------------------------------------------------------.
  26 | Given n by n matrix of bits R, modify its contents to be the |
  27 | transive closure of what was given.                          |
  28 `-------------------------------------------------------------*/
  29
  30 #define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize))
  31
  32 static void
  33 TC (unsigned *R, int n)
  34 {
  35   int rowsize = WORDSIZE (n) * sizeof (unsigned);
  36   int i, j, k;
  37
  38   for (i = 0; i < n; ++i)
  39     for (j = 0; j < n; ++j)
  40       if (BITISSET (R (i), j))
  41         for (k = 0; k < rowsize; ++k)
  42           if (BITISSET (R (i), k))
  43             SETBIT (R (j), k);
  44 }
  45
  46
  47 /*---------------------------------------------------------------.
  48 | Reflexive Transitive Closure.  Same as TC and then set all the |
  49 | bits on the diagonal of R.                                     |
  50 `---------------------------------------------------------------*/
  51
  52 void
  53 RTC (unsigned *R, int n)
  54 {
  55   int rowsize = WORDSIZE (n) * sizeof (unsigned);
  56   int i;
  57
  58   TC (R, n);
  59   for (i = 0; i < n; ++i)
  60     SETBIT (R (i), i);
  61 }