How to verify a Partial Order Relation?
The process of identifying/verifying if any given relation is a partial order relation is:
- Check if the relation is Reflexive.
- Check if the relation is Anti-Symmetric.
- Check if the relation is Transitive.
Follow the below illustration for a better understanding
Illustration:
Consider set R = {(1, 1), (1, 3), (1, 4), (2, 2), (2, 1), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4), (4, 3)}
Pairs (1, 1), (2, 2), (3, 3), (4, 4) exist:
⇒ This satisfies the reflexive condition.The transitive condition is also satisfied.
For the pairs (4, 3):
⇒ The relation (3, 4) exists
⇒ This does not satisfy the anti-symmetric condition.
So the relation is not anti-symmetric.Hence it is not a partial order relation.
Below is the code for checking if a given relation is partial order relation or not:
C++
// C++ code to check if a relation is partial order #include <bits/stdc++.h> using namespace std; // Class to define a relation class Relation { public : bool checkPartialOrder(set< int > A, set<pair< int , int > > R) { bool transitive = checkTransitive(R); bool antisymmetric = checkAntiSymmetric(R); bool reflexive = checkReflexive(A, R); return (transitive && antisymmetric && reflexive); } // Function to check transitive relation bool checkTransitive(set<pair< int , int > > R) { // Empty relation is always transitive if (R.size() == 0) { return true ; } // Create a dictionary to store tuple // as key value pair map< int , set< int > > tup; // Creating dictionary of relation // where (a) is key and (b) is value for ( auto i = R.begin(); i != R.end(); i++) { if (tup.find(i->first) == tup.end()) { set< int > temp; temp.insert(i->second); tup.insert( pair< int , set< int > >(i->first, temp)); } else { tup.at(i->first).insert(i->second); } } for ( auto a = tup.begin(); a != tup.end(); a++) { // Set of all b's related with a set< int > all_b_in_aRb = tup.at(a->first); // Taking all c's from each b one by one for ( int b : all_b_in_aRb) { if (tup.find(b) != tup.end() && a->first != b) { // Set of all c's related with b set< int > all_c_in_bRc = tup.at(b); // All c's related with each b must be // subset of all b's related with a for ( int c : all_c_in_bRc) { if (all_b_in_aRb.find(c) == all_b_in_aRb.end()) { return false ; } } } } } // For all aRb and bRc there exist aRc // in relation R return true ; } // Function to check antisymmetric relation bool checkAntiSymmetric(set<pair< int , int > > R) { // Empty relation is always anti-symmetric if (R.size() == 0) { return true ; } for ( auto i = R.begin(); i != R.end(); i++) { if (i->second != i->first) { // Not a aRa tuple // making a mirror tuple auto temp = make_pair(i->second, i->first); if (R.find(temp) != R.end()) { // If bRa tuple exists // in relation R return false ; } } } // bRa tuples does not exist // for all aRb in relation R return true ; } // Function to check reflexive relation bool checkReflexive(set< int > A, set<pair< int , int > > R) { // Empty relation on a non-empty relation set // is never reflexive. if (A.size() > 0 && R.size() == 0) { return false ; } // Relation defined on an empty set // is always reflexive. 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 ; } }; int main() { // Creating a set A set< int > A{ 1, 2, 3, 4 }; set<pair< int , int > > R; // Inserting tuples in relation R R.insert(make_pair(1, 1)); R.insert(make_pair(1, 3)); R.insert(make_pair(1, 4)); R.insert(make_pair(2, 2)); R.insert(make_pair(2, 1)); R.insert(make_pair(2, 3)); R.insert(make_pair(2, 4)); R.insert(make_pair(3, 3)); R.insert(make_pair(3, 4)); R.insert(make_pair(4, 4)); R.insert(make_pair(4, 3)); Relation obj; // R is not Partial Order as for (3, 4) tuple -> (4, 3) // tuple is present if (obj.checkPartialOrder(A, R)) { cout << "Partial Order Relation" << endl; } else { cout << "Not a Partial Order Relation" << endl; } return 0; } |
Java
// Java code to check if a relation is partial order import java.io.*; import java.util.*; class pair { int first, second; pair( int first, int second) { this .first = first; this .second = second; } } class GFG { // Class to define a relation static class Relation { boolean checkPartialOrder(Set<Integer> A, Set<pair> R) { boolean transitive = checkTransitive(R); boolean antisymmetric = checkAntiSymmetric(R); boolean reflexive = checkReflexive(A, R); return (transitive && antisymmetric && reflexive); } } static boolean checkTransitive(Set<pair> R) { // Property 1 if (R.size() == 0 ) { return true ; } // Create a hashmap to store tuple as key value // pair HashMap<Integer, Set<Integer> > tup = new HashMap<>(); // Creating hashmap of relation where (a) is key // and (b) is value for (pair i : R) { if (!tup.containsKey(i.first)) { Set<Integer> temp = new HashSet<>(); temp.add(i.second); tup.put(i.first, temp); } else { Set<Integer> temp = new HashSet<>(); temp = tup.get(i.first); temp.add(i.second); tup.put(i.first, temp); } } for (Integer a : tup.keySet()) { // Set of all b's related with a Set<Integer> all_b_in_aRb = tup.get(a); // Taking all c's from each b one by one for ( int b : all_b_in_aRb) { if (tup.containsKey(b) && a != b) { // Set of all c's related with b Set<Integer> all_c_in_bRc = tup.get(b); // All c's related with each b must // be subset of all b's related with // a for (Integer c : all_c_in_bRc) { if (all_b_in_aRb.contains(c)) { return false ; } } } } } // For all aRb and bRc there exist aRc in // relation R return true ; } static boolean checkAntiSymmetric(Set<pair> R) { // Property 1 if (R.size() == 0 ) { return true ; } for (var i : R) { int one = i.first; int two = i.second; if (one != two) { // Not a aRa tuple if (R.contains( new pair(two, one))) { // If bRa tuple does exists in // relation R return false ; } } } // bRa tuples does not exists for all aRb in // relation R return true ; } static 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 , 3 )); R.add( new pair( 1 , 4 )); R.add( new pair( 2 , 2 )); R.add( new pair( 2 , 1 )); R.add( new pair( 2 , 3 )); R.add( new pair( 2 , 4 )); R.add( new pair( 3 , 3 )); R.add( new pair( 3 , 4 )); R.add( new pair( 4 , 4 )); R.add( new pair( 4 , 3 )); Relation obj = new Relation(); // R is not Partial Order as for (3, 4) tuple -> (4, // 3) tuple is present if (obj.checkPartialOrder(A, R)) { System.out.println( "Partial Order Relation" ); } else { System.out.println( "Not a Partial Order Relation" ); } } } // This code is contributed by lokeshmvs21. |
Python3
# Python code to check if a relation is partial order # Class to define relation class Relation: def checkPartialOrder( self , A, R): transitive = self .checkTransitive(R) antisymmetric = self .checkAntiSymmetric(R) reflexive = self .checkReflexive(A, R) return transitive and antisymmetric and reflexive # Function to check transitive relation def checkTransitive( self , R): # Empty relation is always transitive if len (R) = = 0 : return True # Create a dictionary to store tuple # as key value pair tup = dict () # Creating dictionary of relation # where (a) is key and (b) is value for i in R: if tup.get(i[ 0 ]) is None : tup[i[ 0 ]] = {i[ 1 ]} else : tup[i[ 0 ]].add(i[ 1 ]) for a in tup.keys(): # Set of all b's related with a all_b_in_aRb = tup.get(a) if all_b_in_aRb is not None : # Taking all c's from each b one by one for b in all_b_in_aRb: # Set of all c's related with b all_c_in_bRc = tup.get(b) if a ! = b and all_c_in_bRc is not None : if not all_c_in_bRc.issubset(all_b_in_aRb): # All c's related with each b must be # subset of all b's related with a return False # For all aRb and bRc there exist aRc # in relation R return True # Function to check antisymmetric relation def checkAntiSymmetric( self , R): # Empty relation is always antisymmetric if len (R) = = 0 : return True for i in R: if i[ 0 ] ! = i[ 1 ]: # Not a aRa tuple if (i[ 1 ], i[ 0 ]) in R: # If bRa tuple does exist in relation R return False # bRa tuples does not exist # for all aRb in relation R return True # Function to check reflexive relation def checkReflexive( self , A, R): # Empty relation on a non-empty relation set # is never reflexive. if len (A) > 0 and len (R) = = 0 : return False # Relation defined on an empty set # is always reflexive. 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 , 3 ), ( 1 , 4 ), ( 2 , 2 ), ( 2 , 1 ), ( 2 , 3 ), ( 2 , 4 ), ( 3 , 3 ), ( 3 , 4 ), ( 4 , 4 ), ( 4 , 3 )} obj = Relation() # R is not Partial Order as for (3, 4) # tuple -> (4, 3) tuple is present if obj.checkPartialOrder(A, R): print ( "Partial Order Relation" ) else : print ( "Not a Partial Order Relation" ) |
C#
// C# code to check if a relation is partial order 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 to define a relation class Relation { public bool checkPartialOrder(HashSet< int > A, HashSet<pair> R) { bool transitive = checkTransitive(R); bool antisymmetric = checkAntiSymmetric(R); bool reflexive = checkReflexive(A, R); return (transitive && antisymmetric && reflexive); } } static bool checkTransitive(HashSet<pair> R) { // Property 1 if (R.Count == 0) { return true ; } // Create a hashmap to store tuple as key value // pair Dictionary< int , HashSet< int > > tup = new Dictionary< int , HashSet< int > >(); // Creating hashmap of relation where (a) is key // and (b) is value foreach (pair i in R) { if (!tup.ContainsKey(i.first)) { HashSet< int > temp = new HashSet< int >(); temp.Add(i.second); tup[i.first] = temp; } else { HashSet< int > temp = new HashSet< int >(); temp = tup[i.first]; temp.Add(i.second); tup[i.first] = temp; } } foreach ( var a in tup) { // Set of all b's related with a HashSet< int > all_b_in_aRb = tup[a.Key]; // Taking all c's from each b one by one foreach ( int b in all_b_in_aRb) { if (tup.ContainsKey(b) && a.Key != b) { // Set of all c's related with b HashSet< int > all_c_in_bRc = tup[b]; // All c's related with each b must // be subset of all b's related with // a foreach ( int c in all_c_in_bRc) { if (all_b_in_aRb.Contains(c)) { return false ; } } } } } // For all aRb and bRc there exist aRc in // relation R return true ; } static bool checkAntiSymmetric(HashSet<pair> R) { // Property 1 if (R.Count == 0) { return true ; } foreach ( var i in R) { int one = i.first; int two = i.second; if (one != two) { // Not a aRa tuple if (R.Contains( new pair(two, one))) { // If bRa tuple does exists in // relation R return false ; } } } // bRa tuples does not exists for all aRb in // relation R return true ; } static 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() { // Code 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, 3)); R.Add( new pair(1, 4)); R.Add( new pair(2, 2)); R.Add( new pair(2, 1)); R.Add( new pair(2, 3)); R.Add( new pair(2, 4)); R.Add( new pair(3, 3)); R.Add( new pair(3, 4)); R.Add( new pair(4, 4)); R.Add( new pair(4, 3)); Relation obj = new Relation(); // R is not Partial Order as for (3, 4) tuple -> (4, // 3) tuple is present if (obj.checkPartialOrder(A, R)) { Console.WriteLine( "Partial Order Relation" ); } else { Console.WriteLine( "Not a Partial Order Relation" ); } } } // This code is contributed by lokesh. |
Javascript
// JavaScript Code to check if a relation is partial order const checkPartialOrder = (A, R) => { let transitive = checkTransitive(R); let antisymmetric = checkAntiSymmetric(R); let reflexive = checkReflexive(A, R); return (transitive && antisymmetric && reflexive); }; // Function to check transitive relation const checkTransitive = (R) => { // Empty relation is always transitive if (R.size === 0) { return true ; } // Create a dictionary to store tuple // as key value pair let tup = {}; // Creating dictionary of relation // where (a) is key and (b) is value for (let i of R) { if (!(i.first in tup)) { let temp = new Set(); temp.add(i.second); tup[i.first] = temp; } else { tup[i.first].add(i.second); } } for (let a in tup) { // Set of all b's related with a let all_b_in_aRb = tup[a]; // Taking all c's from each b one by one for (let b of all_b_in_aRb) { if (b in tup && a !== b) { // Set of all c's related with b let all_c_in_bRc = tup[b]; // All c's related with each b must be // subset of all b's related with a for (let c of all_c_in_bRc) { if (!all_b_in_aRb.has(c)) { return false ; } } } } } // For all aRb and bRc there exist aRc // in relation R return true ; }; // Function to check antisymmetric relation const checkAntiSymmetric = (R) => { // Empty relation is always anti-symmetric if (R.size === 0) { return true ; } for (let i of R) { if (i.second !== i.first) { // Not a aRa tuple // making a mirror tuple let temp = [i.second, i.first]; if (R.has(temp)) { // If bRa tuple exists // in relation R return false ; } } } // bRa tuples does not exist // for all aRb in relation R return true ; }; // Function to check reflexive relation const checkReflexive = (A, R) => { // Empty relation on a non-empty relation set // is never reflexive. if (A.size > 0 && R.size === 0) { return false ; } // Relation defined on an empty set // is always reflexive. else if (A.size === 0) { return true ; } for (let i of A) { // Making a tuple of same element let temp = [i, i]; if (!R.has(temp)) { // If aRa tuple not exists in relation R return false ; } } // All aRa tuples exists in relation R return true ; }; // Creating a set A let A = new Set([1, 2, 3, 4]); let R = new Set(); // Inserting tuples in relation R R.add([1, 1]); R.add([1, 3]); R.add([1, 4]); R.add([2, 2]); R.add([2, 1]); R.add([2, 3]); R.add([2, 4]); R.add([3, 3]); R.add([3, 4]); R.add([4, 4]); R.add([4, 3]); // R is not Partial Order as for (3, 4) tuple -> (4, 3) // tuple is present if (checkPartialOrder(A, R)) { console.log( "Partial Order Relation" ); } else { console.log( "Not a Partial Order Relation" ); } |
Not a Partial Order Relation
Time Complexity: O(N * K * log N) where N is the number of tuples in relation and K is the maximum number of tuples (a, b) for which a is the same.
Auxiliary Space: O(N)
Partial Order Relation on a Set
A relation is a subset of the cartesian product of a set with another set. A relation contains ordered pairs of elements of the set it is defined on.