warshall.c File Reference

#include "defs.h"

Include dependency graph for warshall.c:

Go to the source code of this file.

Functions
	transitive_closure (unsigned *R, int n)
	reflexive_transitive_closure (unsigned *R, int n)

Function Documentation

reflexive_transitive_closure	(	unsigned *	R,
		int	n
	)

Computes the transitive closure of a relation in-place.

Let \( \mathrm{R} \) be an \( \mathrm{n} \times \mathrm{n} \) matrix of bits expressing a relation between n elements, such that \( \mathrm{R}_{i,j} \) is set if and only if the i-th elements is in relation with the j-th one.

Then this function computes the reflexive and transitive closure of such relation and stores it in-place, using Warshall's algorithm. Its complexity is \( O\left( n^3 \right) \), dominated by the complexity of transitive_closure().

Internally, this function just calls transitive_closure() and then sets all elements on the matrix diagonal to make the relation reflexive.

Definition at line 79 of file warshall.c.

References BITS_PER_WORD, R, transitive_closure(), and WORDSIZE.

Referenced by set_EFF().

{
    register int rowsize;
    register unsigned i;
    register unsigned *rp;
    register unsigned *relend;

    transitive_closure(R, n);

    rowsize = WORDSIZE(n);
    relend = R + n*rowsize;

    i = 0;
    rp = R;
    while (rp < relend)
    {
        *rp |= (1 << i);
        if (++i >= BITS_PER_WORD)
        {
            i = 0;
            rp++;
        }

        rp += rowsize;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

transitive_closure	(	unsigned *	R,
		int	n
	)

Computes the transitive closure of a relation in-place.

Let \( \mathrm{R} \) be an \( \mathrm{n} \times \mathrm{n} \) matrix of bits expressing a relation between n elements, such that \( \mathrm{R}_{i,j} \) is set if and only if the i-th elements is in relation with the j-th one.

Then this function computes the transitive closure of such relation and stores it in-place, using Warshall's algorithm. Its complexity is \( O\left( n^3 \right) \).

Definition at line 13 of file warshall.c.

References BITS_PER_WORD, R, and WORDSIZE.

Referenced by reflexive_transitive_closure().

{
    register int rowsize;
    register unsigned i;
    register unsigned *rowj;
    register unsigned *rp;
    register unsigned *rend;
    register unsigned *ccol;
    register unsigned *relend;
    register unsigned *cword;
    register unsigned *rowi;

    rowsize = WORDSIZE(n);
    relend = R + n*rowsize;

    cword = R;
    i = 0;
    rowi = R;
    while (rowi < relend)
    {
        ccol = cword;
        rowj = R;

        while (rowj < relend)
        {
            if (*ccol & (1 << i))
            {
                rp = rowi;
                rend = rowj + rowsize;
                while (rowj < rend)
                    *rowj++ |= *rp++;
            }
            else
            {
                rowj += rowsize;
            }

            ccol += rowsize;
        }

        if (++i >= BITS_PER_WORD)
        {
            i = 0;
            cword++;
        }

        rowi += rowsize;
    }
}

Here is the caller graph for this function: