How to verify a Reflexive Relation?

The process of identifying/verifying if any given relation is reflexive:

Check for the existence of every aRa tuple in the relation for all a present in the set.
If every tuple exists, only then the relation is reflexive. Otherwise, not reflexive.

Follow the below illustration for a better understanding:

Illustration:

Consider set A = {a, b} and a relation R = {{a, a}, {a, b}}.

For the element a in A:
=> The pair {a, a} is present in R.
=> Hence aRa is satisfied.

For the element b in A:
=> The pair {b, b} is not present int R.
=> Hence bRb is not satisfied.

As the condition for ‘b’ is not satisfied, the relation is not reflexive.

Below is a code implementation of the approach.

C++

// C++ code to check if a set is reflexive
 
#include <bits/stdc++.h>
using namespace std;
 
class Relation {
public:
    bool checkReflexive(set<int> A, set<pair<int, int> > R)
    {
        // Property 1
        if (A.size() > 0 && R.size() == 0) {
            return false;
        }
        // Property 2
        else if (A.size() == 0) {
            return true;
        }
 
        for (auto i = A.begin(); i != A.end(); i++) {
 
            // Making a tuple of same element
            auto temp = make_pair(*i, *i);
 
            if (R.find(temp) == R.end()) {
 
                // If aRa tuple not exists in relation R
                return false;
            }
        }
 
        // All aRa tuples exists in relation R
        return true;
    }
};
 
// Driver code
int main()
{
    // Creating a set A
    set<int> A{ 1, 2, 3, 4 };
 
    // Creating relation R
    set<pair<int, int> > R;
 
    // Inserting tuples in relation R
    R.insert(make_pair(1, 1));
    R.insert(make_pair(1, 2));
    R.insert(make_pair(2, 2));
    R.insert(make_pair(2, 3));
    R.insert(make_pair(3, 2));
    R.insert(make_pair(3, 3));
 
    Relation obj;
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
        cout << "Reflexive Relation" << endl;
    }
    else {
        cout << "Not a Reflexive Relation" << endl;
    }
 
    return 0;
}

Java

// Java code implementation for the above approach
import java.io.*;
import java.util.*;
 
class pair {
  int first, second;
  pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
class GFG {
 
  static class Relation {
    boolean checkReflexive(Set<Integer> A, Set<pair> R)
    {
      // Property 1
      if (A.size() > 0 && R.size() == 0) {
        return false;
      }
 
      // Property 2
      else if (A.size() == 0) {
        return true;
      }
 
      for (var i : A) {
        if (!R.contains(new pair(i, i))) {
          // If aRa tuple not exists in relation R
          return false;
        }
      }
      // All aRa tuples exists in relation R
      return true;
    }
  }
 
  public static void main(String[] args)
  {
    // Creating a set A
    Set<Integer> A = new HashSet<>();
    A.add(1);
    A.add(2);
    A.add(3);
    A.add(4);
 
    // Creating relation R
    Set<pair> R = new HashSet<>();
 
    // Inserting tuples in relation R
    R.add(new pair(1, 1));
    R.add(new pair(1, 2));
    R.add(new pair(2, 2));
    R.add(new pair(2, 3));
    R.add(new pair(3, 2));
    R.add(new pair(3, 3));
 
    Relation obj = new Relation();
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
      System.out.println("Reflexive Relation");
    }
    else {
      System.out.println("Not a Reflexive Relation");
    }
  }
}
 
// This code is contributed by lokeshmvs21.

Python3

class Relation:
    def checkReflexive(self, A, R):
        # Property 1
        if len(A) > 0 and len(R) == 0:
            return False
        # Property 2
        elif len(A) == 0:
            return True
 
        for i in A:
            if (i, i) not in R:
 
                # If aRa tuple not exists in relation R
                return False
 
        # All aRa tuples exists in relation R
        return True
 
 
# Driver code
if __name__ == '__main__':
 
    # Creating a set A
    A = {1, 2, 3, 4}
 
    # Creating relation R
    R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 2), (3, 3)}
 
    obj = Relation()
 
    # R in not reflexive as (4, 4) tuple is not present
    if obj.checkReflexive(A, R):
        print("Reflexive Relation")
    else:
        print("Not a Reflexive Relation")

C#

// C# code implementation for the above approach
 
using System;
using System.Collections.Generic;
 
class pair {
  public int first, second;
  public pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG {
 
  class Relation {
    public bool checkReflexive(HashSet<int> A,
                               HashSet<pair> R)
    {
      // Property 1
      if (A.Count > 0 && R.Count == 0) {
        return false;
      }
 
      // Property 2
      else if (A.Count == 0) {
        return true;
      }
 
      foreach(var i in A)
      {
        if (!R.Contains(new pair(i, i))) 
        {
           
          // If aRa tuple not exists in relation R
          return false;
        }
      }
       
      // All aRa tuples exists in relation R
      return true;
    }
  }
 
  static public void Main()
  {
 
    // Creating a set A
    HashSet<int> A = new HashSet<int>();
    A.Add(1);
    A.Add(2);
    A.Add(3);
    A.Add(4);
 
    // Creating relation R
    HashSet<pair> R = new HashSet<pair>();
 
    // Inserting tuples in relation R
    R.Add(new pair(1, 1));
    R.Add(new pair(1, 2));
    R.Add(new pair(2, 2));
    R.Add(new pair(2, 3));
    R.Add(new pair(3, 2));
    R.Add(new pair(3, 3));
 
    Relation obj = new Relation();
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
      Console.WriteLine("Reflexive Relation");
    }
    else {
      Console.WriteLine("Not a Reflexive Relation");
    }
  }
}
 
// This code is contributed by lokesh

Javascript

// JS code to check if a set is reflexive
 
function checkReflexive(A, R)
{
    let cnt = 0;
    // Property 1
    if (A.size > 0 && R.size == 0) {
        return false;
    }
    // Property 2
    else if (A.size == 0) {
        return true;
    }
 
    A.forEach(i => {
         
        // Making a tuple of same element
        let temp = [i, i];
 
        if (!R.has(temp)) {
 
            // If aRa tuple not exists in relation R
            cnt++;
        }
 
    });
 
 
    // All aRa tuples exists in relation R
    if(cnt==0)
        return true;
    else
        return false;
}
 
 
// Driver code
// Creating a set A
let A = new Set([ 1, 2, 3, 4 ]);
 
// Creating relation R
let R = new Set();
 
// Inserting tuples in relation R
R.add([1,1]);
R.add([1,2]);
R.add([2,2]);
R.add([2,3]);
R.add([3,2]);
R.add([3,3]);
R.add([3,3]);
 
// R in not reflexive as (4, 4) tuple is not present
if (checkReflexive(A, R)) {
    console.log("Reflexive Relation");
}
else {
    console.log("Not a Reflexive Relation");
}
 
// This code is contributed by akashish__

Output

Not a Reflexive Relation

Time Complexity: O(N * log M) where N is the size of the set and M is the number of pairs in the relation
Auxiliary Space: O(1)

C++

Java

Python3

C#

Javascript

Reflexive Relation on Set

Similar Reads