home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / BYACC.ZIP / WARSHALL.C < prev   
C/C++ Source or Header  |  1992-03-16  |  1KB  |  87 lines
  1. #include <stdlib.h>
  2. #include "byacc.h"
  3.  
  4. void
  5. transitive_closure(unsigned *R, int n)
  6. {
  7.   register int rowsize;
  8.   register unsigned mask;
  9.   register unsigned *rowj;
  10.   register unsigned *rp;
  11.   register unsigned *rend;
  12.   register unsigned *ccol;
  13.  
  14.   unsigned *relend;
  15.   unsigned *cword;
  16.   unsigned *rowi;
  17.  
  18.   rowsize = ROWSIZE(n);
  19.   relend = (unsigned *) ((char *) R + n*rowsize);
  20.  
  21.   cword = R;
  22.   mask = 1;
  23.   rowi = R;
  24.   while (rowi < relend)
  25.     {
  26.       ccol = cword;
  27.       rowj = R;
  28.  
  29.       while (rowj < relend)
  30.     {
  31.       if (*ccol & mask)
  32.         {
  33.           rp = rowi;
  34.           rend = (unsigned *) ((char*) rowj + rowsize);
  35.  
  36.           while (rowj < rend)
  37.         *rowj++ |= *rp++;
  38.         }
  39.       else
  40.         {
  41.           rowj = (unsigned *) ((char*) rowj + rowsize);
  42.         }
  43.  
  44.       ccol = (unsigned *) ((char*) ccol + rowsize);
  45.     }
  46.  
  47.       mask <<= 1;
  48.       if (mask == 0)
  49.     {
  50.       mask = 1;
  51.       cword++;
  52.     }
  53.  
  54.       rowi = (unsigned *) ((char*) rowi + rowsize);
  55.     }
  56. }
  57.  
  58. void
  59. reflexive_transitive_closure(unsigned * R, int n)
  60. {
  61.   register int rowsize;
  62.   register unsigned mask;
  63.   register unsigned *rp;
  64.   register unsigned *relend;
  65.  
  66.   transitive_closure(R, n);
  67.  
  68.   rowsize = ROWSIZE(n);
  69.   relend = (unsigned *) ((char*) R + n*rowsize);
  70.  
  71.   mask = 1;
  72.   rp = R;
  73.   while (rp < relend)
  74.     {
  75.       *rp |= mask;
  76.  
  77.       mask <<= 1;
  78.       if (mask == 0)
  79.     {
  80.       mask = 1;
  81.       rp++;
  82.     }
  83.  
  84.       rp = (unsigned *) ((char*) rp + rowsize);
  85.     }
  86. }
  87.