Category : C Source Code
Archive   : TBISON0.ZIP
Filename : WARSHALL.C

/* Generate transitive closure of a matrix,
copyright (C) 1984 Bob Corbett and Richard Stallman

Permission is granted to anyone to make or distribute verbatim
copies of this program provided that the copyright notice and
this permission notice are preserved; and provided that the
recipient is not asked to waive or limit his right to
redistribute copies as permitted by this permission notice;
and provided that anyone possessing an executable copy
is granted access to copy the source code, in machine-readable form,
in some reasonable manner.

Permission is granted to distribute derived works or enhanced
versions of this program under the above conditions with the
additional condition that the entire derivative or enhanced work
must be covered by a permission notice identical to this one.

Anything distributed as part of a package containing portions
derived from this program, which cannot in current practice
perform its function usefully in the absense of what was derived
directly from this program, is to be considered as forming,
together with the latter, a single work derived from this program,
which must be entirely covered by a permission notice identical to
this one in order for distribution of the package to be permitted.

In other words, you are welcome to use, share and improve this
program. You are forbidden to forbid anyone else to use, share
and improve what you give them. Help stamp out software-hoarding! */

#include
#include "machine.h"


/* given n by n matrix of bits R, modify its contents
to be the transive closure of what was given. */

TC(R, n)
unsigned *R;
int n;
{
register int rowsize;
register unsigned mask;
register unsigned *rowj;
register unsigned *rp;
register unsigned *rend;
register unsigned *ccol;

unsigned *relend;
unsigned *cword;
unsigned *rowi;

rowsize = WORDSIZE(n) * sizeof(unsigned);
relend = (unsigned *) ((char *) R + n*rowsize);

cword = R;
mask = 1;
rowi = R;
while (rowi < relend)
{
ccol = cword;
rowj = R;

while (rowj < relend)
{
if (*ccol & mask)
{
rp = rowi;
rend = (unsigned *) ((char *) rowj + rowsize);

while (rowj < rend)
*rowj++ |= *rp++;
}
else
{
rowj = (unsigned *) ((char *) rowj + rowsize);
}

ccol = (unsigned *) ((char *) ccol + rowsize);
}

mask <<= 1;
if (mask == 0)
{
mask = 1;
cword++;
}

rowi = (unsigned *) ((char *) rowi + rowsize);
}
}


/* Reflexive Transitive Closure. Same as TC
and then set all the bits on the diagonal of R. */

RTC(R, n)
unsigned *R;
int n;
{
register int rowsize;
register unsigned mask;
register unsigned *rp;
register unsigned *relend;

TC(R, n);

rowsize = WORDSIZE(n) * sizeof(unsigned);
relend = (unsigned *) ((char *) R + n*rowsize);

mask = 1;
rp = R;
while (rp < relend)
{
*rp |= mask;

mask <<= 1;
if (mask == 0)
{
mask = 1;
rp++;
}

rp = (unsigned *) ((char *) rp + rowsize);
}
}