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 "bitsetv.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, bitsetv matrix)
  33 {
  34   size_t i, j;
  35   size_t size = bitset_size (matrix[0]);
  36
  37   /* Title. */
  38   fprintf (stderr, "%s BEGIN\n", title);
  39
  40   /* Column numbers. */
  41   fputs ("   ", stderr);
  42   for (i = 0; i < size; ++i)
  43     putc (i / 10 ? '0' + i / 10 : ' ', stderr);
  44   putc ('\n', stderr);
  45   fputs ("   ", stderr);
  46   for (i = 0; i < size; ++i)
  47     fprintf (stderr, "%d", i % 10);
  48   putc ('\n', stderr);
  49
  50   /* Bar. */
  51   fputs ("  .", stderr);
  52   for (i = 0; i < size; ++i)
  53     putc ('-', stderr);
  54   fputs (".\n", stderr);
  55
  56   /* Contents. */
  57   for (i = 0; i < size; ++i)
  58     {
  59       fprintf (stderr, "%2d|", i);
  60       for (j = 0; j < size; ++j)
  61         fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
  62       fputs ("|\n", stderr);
  63     }
  64
  65   /* Bar. */
  66   fputs ("  `", stderr);
  67   for (i = 0; i < size; ++i)
  68     putc ('-', stderr);
  69   fputs ("'\n", stderr);
  70
  71   /* End title. */
  72   fprintf (stderr, "%s END\n\n", title);
  73 }
  74
  75 /*-------------------------------------------------------------------.
  76 | Given the MATRIX array of N bitsets of size N, modify its contents |
  77 | to be the transive closure of what was given.                      |
  78 `-------------------------------------------------------------------*/
  79
  80 static void
  81 TC (bitsetv matrix)
  82 {
  83   int i, j;
  84
  85   if (trace_flag)
  86     bitmatrix_print ("TC: Input", matrix);
  87
  88   /* R (J, I) && R (I, K) => R (J, K).
  89      I *must* be the outter loop. */
  90
  91   for (i = 0; matrix[i]; ++i)
  92     for (j = 0; matrix[j]; ++j)
  93       if (bitset_test (matrix[j], i))
  94         bitset_or (matrix[j], matrix[j], matrix[i]);
  95
  96   if (trace_flag)
  97     bitmatrix_print ("TC: Output", matrix);
  98 }
  99
 100
 101 /*---------------------------------------------------------------.
 102 | Reflexive Transitive Closure.  Same as TC and then set all the |
 103 | bits on the diagonal of MATRIX.                                |
 104 `---------------------------------------------------------------*/
 105
 106 void
 107 RTC (bitsetv matrix)
 108 {
 109   int i;
 110
 111   TC (matrix);
 112   for (i = 0; matrix[i]; ++i)
 113     bitset_set (matrix[i], i);
 114 }