COSC3302
Program-1
Due: Tuesday, 2/12/2013
Smallest Equivalence Relation.
(Warshall's
Algorithm)
Backgrounds:
1.
Given a binary relation R on a certain finite set S,
we can consider an equivalence
relation on the set S
that contains the relation
R.
2. Of
all equivalence relations to be obtained from this
relation R, we can think of the
minimum equivalence relation.
It must be the one that is
contained in any and every such
equivalence
relation.
Example:
1 0 0
0 1 0
0 0 0
For the above relation on a set of three
elements,
each of the following is an equivalence relation that
contains
the given binary relation:
1 0 0 1 1 1 1 1 0
0 1 0 1 1 1 1 1 0
0 0 1 1 1 1 0 0 1
The first one above is the minimum equivalence relation
containing
the given binary relation.
3.
How to get it?
Perform the following operations in succession:
a. Symmetric closure on the given binary relation R to result
in
s(R)
b. Transitive closure operation on the resulting relation,
s(R),
to result in
ts(R).
c. Finally, Reflexive closure on ts(R), to get rts(R) which
is
the wanted minimum
equivalence relation.
You can perform above three operations
in a different sequence.
But, not every different sequence will
result in what is wanted as the Symmetric
Closure must be performed always before
the Transitive Closure.
Task:
Write
a well-documented program that does:
1. Repeat
a. Input the size of an adjacency matrix
(<=20)
b. Input a matrix exactly of that size.
c. Compute the minimum equivalence relation
and hence its
adjacency matrix.
d. And, print out both the input matrix and
the resulting (Min.
Eq. Relation) matrix.
until all inputs are
done.
2. Print out the number of input cases
that have been
processed.
NOTE:
In computing the Transitive Closure of a (binary)
relation
use the
Warshall's algorithm.
The
Warshall's algorithm:
void
Closure (int Size, int Rel [][])
{
int From, To,
Via;
for (Via=0; Via < Size;
Via++)
for (From=0; From < Size;
From++)
for (To=0; To
< Size; To++)
if (Rel[From][Via]*Rel[Via][To])
Rel[From][To] =
1;
//End of Via loop, and hence end of other two
loops.
}
//End of java method Closure.
Inputs: Use the following three input cases, plus at least two more of
your making.
3
1 0 0
0 1 0
0 1 1
6
0 1 1 0 0 0
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 0 1 0
0 0 0 1 0 1
0 0 0 1 0 0
8
1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 1 0 1 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1
1 0 0 1 0 0 1 0
EXERCISE:
Find a binary relation over three elements for which perfporming the
Transitive Closure before the Symmetric Closure
will not produce a Minimum E. R.