Test for symmetry in relation using sets

Question

I am working with ordered pairs of type unsigned typedef pair<unsigned, unsigned> OP;, and sets of ordered pairs typedef set<OP> SOP;.

The ultimate goal of my program is to check if the set(relation) is an equivalence relation.

My problem: I have managed to check if a set is reflexive but currently I am trying to check if an ordered pair in the set (relation) is symmetric. I have currently constructed two for loops to compare the ordered pairs against each other but have struck a dead end in my comparison.

My code:

for (auto it3 = sop.begin(); it3 != sop.end(); it3++) { // loop through each pair in set
        for (auto it4 = sop.begin(); it4 != sop.end(); it4++) { // compare with other pairs
           // make sure first and second items in pair are different
            while (it3->first != it3->second) {
               //If the case is that there is not an instance of 
               //symmetric relation return false  
                if (!((it3->first == it4->second) && (it3->second == it4->first))) {
                    return false;
                }
            }
        }
    }

Answer 1

Your looping logic is completely flawed.

The inner while does not change neither it3 nor it4. So either it will return false or it will loop forever. In addition, the inner for loop doesn't take advantege of the fact that sets are ordered.

The test you are looking for is much simpler

It is sufficient to loop on sop, and check for every item if the symmetric is in the set as well. If one is not, it's not a symmetric relationship. If all succeed to find the reverse, it's fine:

bool is_symetric (SOP sop) {
    for (auto it3 = sop.begin(); it3 != sop.end(); it3++) { // loop through each pair in set
        if (it3->first != it3->second) {
            if (sop.find({it3->second,it3->first })==sop.end()) {
                return false;
            }
        }
    }
    return true; 
}

Online demo

There's even a cooler solution if you're allowed to use the algorithm library:

bool is_symetric (SOP sop) {
    return all_of(sop.cbegin(), sop.cend(),
        [&sop](auto &x){ return x.first==x.second || sop.find({x.second,x.first })!=sop.end();}) ;
}

Online demo 2

And even cooler, is if you make it a template, able to work not only with unsigned, but with any other type:

template <class T>
bool is_symetric (set<pair<T,T>> sop) {
    return all_of(sop.cbegin(), sop.cend(),
        [&sop](auto &x){ return x.first==x.second || sop.find({x.second,x.first })!=sop.end();}) ;
}

Online demo 3 (with unsigned long long)