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.