home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / language / bison / Old_Bison / C / Warshall < prev   
Encoding:
Text File  |  1990-04-01  |  2.4 KB  |  114 lines
  1. /* Generate transitive closure of a matrix,
  2.    Copyright (C) 1984, 1989 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 1, 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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include <stdio.h>
  22. #include "system.h"
  23. #include "machine.h"
  24.  
  25.  
  26. /* given n by n matrix of bits R, modify its contents
  27.    to be the transive closure of what was given.  */
  28.  
  29. void TC(unsigned *R, int n)
  30. {
  31.   register int rowsize;
  32.   register unsigned mask;
  33.   register unsigned *rowj;
  34.   register unsigned *rp;
  35.   register unsigned *rend;
  36.   register unsigned *ccol;
  37.  
  38.   unsigned *relend;
  39.   unsigned *cword;
  40.   unsigned *rowi;
  41.  
  42.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  43.   relend = (unsigned *) ((char *) R + (n * rowsize));
  44.  
  45.   cword = R;
  46.   mask = 1;
  47.   rowi = R;
  48.   while (rowi < relend)
  49.     {
  50.       ccol = cword;
  51.       rowj = R;
  52.  
  53.       while (rowj < relend)
  54.     {
  55.       if (*ccol & mask)
  56.         {
  57.           rp = rowi;
  58.           rend = (unsigned *) ((char *) rowj + rowsize);
  59.  
  60.           while (rowj < rend)
  61.         *rowj++ |= *rp++;
  62.         }
  63.       else
  64.         {
  65.           rowj = (unsigned *) ((char *) rowj + rowsize);
  66.         }
  67.  
  68.       ccol = (unsigned *) ((char *) ccol + rowsize);
  69.     }
  70.  
  71.       mask <<= 1;
  72.       if (mask == 0)
  73.     {
  74.       mask = 1;
  75.       cword++;
  76.     }
  77.  
  78.       rowi = (unsigned *) ((char *) rowi + rowsize);
  79.     }
  80. }
  81.  
  82.  
  83. /* Reflexive Transitive Closure.  Same as TC
  84.    and then set all the bits on the diagonal of R.  */
  85.  
  86. void RTC(unsigned *R, int n)
  87. {
  88.   register int rowsize;
  89.   register unsigned mask;
  90.   register unsigned *rp;
  91.   register unsigned *relend;
  92.  
  93.   TC(R, n);
  94.  
  95.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  96.   relend = (unsigned *) ((char *) R + n*rowsize);
  97.  
  98.   mask = 1;
  99.   rp = R;
  100.   while (rp < relend)
  101.     {
  102.       *rp |= mask;
  103.  
  104.       mask <<= 1;
  105.       if (mask == 0)
  106.     {
  107.       mask = 1;
  108.       rp++;
  109.     }
  110.  
  111.       rp = (unsigned *) ((char *) rp + rowsize);
  112.     }
  113. }
  114.