transitive.cpp

#include "stdafx.h"

#include <iostream>
using std::cout; using std::endl;
#include <functional>
using std::function;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <utility>
using std::pair;
#include <cmath>

#include <Eigen>
using namespace Eigen;

const int N = 20;
using Mat = Matrix<int, N, N>;

#define intersect cwiseProduct

// Get the transitive closure using warshall's algorithm
Mat warshall(Mat Mr) {
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                Mr(i, j) |= Mr(i, k) && Mr(k, j);
    return Mr;
}

Mat bool_sqr(Mat Mr) {
    Mat Mr2; Mr2.setZero();
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N; ++k)
                Mr2(i, j) |= Mr(i, k) && Mr(k, j);
    return Mr2;
}

bool is_reflexive(const Mat& Mr) {
    return Mr.diagonal().sum() == N;
}

bool is_symmetric(const Mat& Mr) {
    return Mr.transpose() == Mr;
}

bool is_antisymmetric(const Mat& Mr) {
    return Mr.transpose().intersect(Mr).sum() - Mr.diagonal().sum() == 0; // if count(a_ij == a_ji == 1, where i!=j) == 0
}

bool is_transitive(const Mat& Mr) {
    //return warshall(Mr) == Mr;
    for (int a = 0; a < N; ++a)
        for (int b = 0; b < N; ++b)
            for (int c = 0; c < N; ++c)
                if (Mr(a, b) && Mr(b, c) && !Mr(a, c)) // not for all a,b,c(aRb ^ bRc -> a^c)
                    return false;
    return true;
}

bool is_antitransitive(const Mat& Mr) {
    return bool_sqr(Mr).intersect(Mr).sum() == 0;
    for (int a = 0; a < N; ++a)
        for (int b = 0; b < N; ++b)
            for (int c = 0; c < N; ++c)
                if (Mr(a, b) && Mr(b, c) && Mr(a, c))
                    return false;
    return true;
}

void print_mat(const Mat& Mr) {
    for (int i = 0; i < Mr.rows(); ++i) {
        for (int j = 0; j < Mr.cols(); ++j) {
            if (Mr(i, j)) {
                cout << 1 << " ";
            }
            else {
                cout << "  ";
            }
        }
        cout << endl;
    }
}

// Get the matrix representation of the relation R on the set A
Mat get_rel_mat(const VectorXi& A, const function<bool(int, int)>& R) {
    Mat Mr; Mr.setZero();
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) // Loop through the cartesian product AxA
            if (R(A(i), A(j)))
                Mr(i, j) = 1;
    return Mr;
}

int main() {
    cout << std::boolalpha;
    VectorXi A(N);
    for (int i = 1; i <= N; ++i)
        A(i - 1) = i;
    cout << "Relations on the set of integers : {" << A.transpose() << " }" << endl << endl;

#define F(xx) [](int x, int y) { return (xx); }, #xx
    vector<pair<function<bool(int, int)>, string>> tasks{
        {F(x == y)},
        {F(x != y)},
        {F(x < y)},
        {F(x == y + 1)},
        {F(x == 5)},
        {F(x == y / 2 + 5)},
        {F(x < y && (y > 4 && y < N - 3 && x > 4 && x < N - 3))}, // x < y with restricted domain
        {F(y % x == 0)},
        {F((x * y) % 5 == 0)},
        {F(ceil(x / y) == 2)},
        {F(x % 2 == y % 2)},
        {F(x % 3 == y % 6)},
        {F(pow(x - 10, 2) + pow(y - 10,2) <= pow(4, 2))},
        {F(((y == 5 || y == N - 4) && (x > 4 && x < N - 3)) || ((x == 5 || x == N - 4) && (y > 4 && y < N - 3)))},
        {F(((y > 4 && y < N - 3) && (x > 4 && x < N - 3)))},
        {F(x / 19. >= .25 * sin(y / 7. * 3.14) + .5)},
        {[](int x, int y) {
            int sum = 1;
            while (x > 1 && bool(sum += x % 2)) x % 2 ? x = 3 * x + 1 : x /= 2;
            return y < sum;
        }, "is y < the sum of parity of terms in the collatz sequence of x?"}
    };
#undef F

    for (const auto & p : tasks) {
        cout << "Relation: " << p.second << endl;
        const auto x = get_rel_mat(A, p.first);
        cout << x << endl;
        cout << "Is reflexive? " << is_reflexive(x) << endl;
        cout << "Is symmetric? " << is_symmetric(x) << endl;
        cout << "Is antisymmetric? " << is_antisymmetric(x) << endl;
        cout << "Is transitive? " << is_transitive(x) << endl;
        cout << "Is antitransitive? " << is_antitransitive(x) << endl << endl;
    }

    cout << "A randomly generated relation and its transitive closure" << endl;
    Mat r; r.setRandom();
    r = r.unaryExpr([](const int x) { return int(abs(x) % 11 == 0); }); // factor of 11 is less probable
    cout << r << endl << endl;
    cout << warshall(r) << endl << endl << endl;

    cout << "Relationship" << endl;
    print_mat(get_rel_mat(A, [](int x, int y) {
        double u = abs(2 * y - 19);
        double v = 19 - 2 * x + .6;
        double t = asin(pow(u / 16., 1. / 3.));
        double vv = 13 * cos(t) - 5 * cos(2 * t) - 2 * cos(3 * t) - cos(4 * t);
        double c = .5 / fabs(v - vv);
        t += 3.1415;
        v -= 2;
        vv = 13 * cos(t) - 5 * cos(2 * t) - 2 * cos(3 * t) - cos(4 * t);
        c += .5 / fabs(v - vv);
        return c > .4;
    }));
}