💻

Logical Operator/transitive closure

2024/03/11に公開

推移閉包のコードを書いてみた。

var logical_operator = {
    dot_tuple: function(tuple_p, tuple_q) {
        let tail = tuple_p[tuple_p.length - 1];
        let head = tuple_q[0];
        if (tail == head) {
            let a = tuple_p.slice(0, tuple_p.length-1);
            let b = tuple_q.slice(1);
            return [...a.concat(b)];
        } else {
            return null;
        }
    },
    dot: function(tuples_p, tuples_q) {
        let r = [];
        for(let i=0; i < tuples_p.length; i++) {
            let tuple_p = tuples_p[i];
            for(let j=0; j < tuples_q.length; j++) {
                let tuple_q = tuples_q[j];
                let t = logical_operator.dot_tuple(tuple_p, tuple_q);
                if (t != null) {
                    r.push(t);
                }
            }
        }
        return r;
    },
    transitive_closure(tuples) {
        let r0 = tuples.slice();
        let r = tuples.slice(); // r1
        while(true) {
            let q = logical_operator.dot(r, r0);
            if (q.length == 0) {
                break;
            }
            r = [...r.concat(q)];
            if (q.length == 1) {
                break;
            }
        }
        return r;
    }
};

var r = [
    ["A", "B"],
    ["A", "C"],
    ["A", "D"],
    ["B", "C"],
];

console.log(logical_operator.transitive_closure(r));

実行結果

[
  [ 'A', 'B' ],
  [ 'A', 'C' ],
  [ 'A', 'D' ],
  [ 'B', 'C' ],
  [ 'A', 'C' ]
]

Discussion