Algorithm for checking transitivity of relation?

Question

I need to check if relation is transitive or not?

Would you please suggest some algorithm to check the transitivity of relations?

I am storing relation as a boolean matrix there is 1 if elements are related other wise 0 like in graphs.

Thanks.

Solution 1

Much simpler algorithm as my Map/Set version (deleted), now with boolean matrix. Maybe this is easier to understand, even if you don't know Java?

public class Trans
{

  final static int SIZE = 4;

  static boolean isTransitive(boolean[][] function)
  {
    for (int i = 0; i < SIZE; i++)
    {
      for (int j = 0; j < SIZE; j++)
      {
        if (function[i][j])
        {
          for (int k = 0; k < SIZE; k++)
          {
            if (function[j][k] && !function[i][k])
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  public static void main(String[] args)
  {
    boolean[][] function = new boolean[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
      function[i] = new boolean[SIZE];
    }
    function[0][1] = true;
    function[1][2] = true;
    function[0][2] = true;
    function[0][3] = true;
    function[1][3] = true;   
    System.out.println(isTransitive(function));
  }
}

Solution 2

Despite this totally sounds like homework...

You'd need to store your relations so that you can look them up by the antecedent very quickly. Then you can discover transitive relations of the type A->B->C, add them to the same storage, and keep going to look up A->B->C->D, etc etc...

Solution 3

Topological sorting may be the right direction. The relationship is transitive if there are no loops in its directed graph representation. If you care about speed, graph algorithms are probably the way to go.

Comments

[Pratik Deoghare]

I don't go to school, so no homework :D

[Santropedro]

"The relationship is transitive if there are no loops in its directed graph representation" That's false, for example the relation {(1,2),(2,3)} doesn't have any loops, but it's not transitive, it would if one adds (1,3) to it.