src/warshall.c

   1 /* Generate transitive closure of a matrix,
   2    Copyright 1984, 1989, 2000, 2001, 2002 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 "bitset.h"
  25 #include "warshall.h"
  26
  27 /*--------------------------------------------------------.
  28 | Display the MATRIX array of SIZE bitsets of size SIZE.  |
  29 `--------------------------------------------------------*/
  30
  31 static void
  32 bitmatrix_print (const char *title, bitset *matrix, size_t size)
  33 {
  34   size_t i, j;
  35
  36   /* Title. */
  37   fprintf (stderr, "%s BEGIN\n", title);
  38
  39   /* Column numbers. */
  40   fputs ("   ", stderr);
  41   for (i = 0; i < size; ++i)
  42     putc (i / 10 ? '0' + i / 10 : ' ', stderr);
  43   putc ('\n', stderr);
  44   fputs ("   ", stderr);
  45   for (i = 0; i < size; ++i)
  46     fprintf (stderr, "%d", i % 10);
  47   putc ('\n', stderr);
  48
  49   /* Bar. */
  50   fputs ("  .", stderr);
  51   for (i = 0; i < size; ++i)
  52     putc ('-', stderr);
  53   fputs (".\n", stderr);
  54
  55   /* Contents. */
  56   for (i = 0; i < size; ++i)
  57     {
  58       fprintf (stderr, "%2d|", i);
  59       for (j = 0; j < size; ++j)
  60         fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
  61       fputs ("|\n", stderr);
  62     }
  63
  64   /* Bar. */
  65   fputs ("  `", stderr);
  66   for (i = 0; i < size; ++i)
  67     putc ('-', stderr);
  68   fputs ("'\n", stderr);
  69
  70   /* End title. */
  71   fprintf (stderr, "%s END\n\n", title);
  72 }
  73
  74 /*-------------------------------------------------------------------.
  75 | Given the MATRIX array of N bitsets of size N, modify its contents |
  76 | to be the transive closure of what was given.                      |
  77 `-------------------------------------------------------------------*/
  78
  79 static void
  80 TC (bitset *matrix, int n)
  81 {
  82   int i, j;
  83
  84   if (trace_flag)
  85     bitmatrix_print ("TC: Input", matrix, 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 (bitset_test (matrix[j], i))
  93         bitset_or (matrix[j], matrix[j], matrix[i]);
  94
  95   if (trace_flag)
  96     bitmatrix_print ("TC: Output", matrix, n);
  97 }
  98
  99
 100 /*---------------------------------------------------------------.
 101 | Reflexive Transitive Closure.  Same as TC and then set all the |
 102 | bits on the diagonal of MATRIX.                                |
 103 `---------------------------------------------------------------*/
 104
 105 void
 106 RTC (bitset *matrix, int n)
 107 {
 108   int i;
 109
 110   TC (matrix, n);
 111   for (i = 0; i < n; ++i)
 112     bitset_set (matrix[i], i);
 113 }