javascript - JavaScript 中的分区细化算法

Question

我有一组节点 {s1,s2,s3,s4,s5} 和一些边:

• (s1,a,s2)
• (s2,a,s2)
• (s3,a,s4)
• (s4,a,s4)

• (s5,a,s5)

• (s1,b,s3)

• (s3,b,s5)
• (s5,b,s5)

我有一个分区细化过程说明

在第一张图片中，我将所有节点都放在一个Array(或Map？？)中。

在每次迭代中，我想将每个 block 减少为子 block 。在第一张图片的(唯一) block 中，我们看到 s2 和 s4 可以进行 a 转换(两个循环)但不能进行 b 转换，而其余节点 s1、s3、s5 可以进行 a 转换和b-transitions，所以我将它们分成两个 block {s1,s3,s5} 和 {s2,s4}。

在下一次迭代中， block {s2,s4} 没有区别，但在另一个 block 中，我们看到 s1 和 s3 有一个转移到 block {s2,s4} 而 s5 有一个 a -转换到它自己的 block {s1,s3,s5}，所以我将 s5 分成它自己的 block ，生成 {s1,s3}、{s5}、{s2,s4}。

最后，我看到 s3 有一个到 block {s5} 的 b 转换，而 {s1} 没有有这个，所以我将 s3 和 s1 分组到单独的 block 中，产生 {s1} , {s3}, {s5}, {s2,s4}。

我如何在 JavaScript 中实现它？

我猜可能是这样的

// all nodes
var nodes = getNodes();

// all edges
var edges = getEdges();

// always holding the current partition
var partition = [];

// first add all nodes into 1 block
partition.push(nodes)

// run until the process is terminated
while (true) {

  // loop through each block in partition
  partition.forEach(function (block) {

    // only care about blocks with more than 1 node
    if (block.length > 1) {

      // loop through each node in the block
      block.forEach(function (node) {

        // check which transitions this node have (i.e. which label and which blocks it goes into)

      });

    }

  });

Answer 1

这是尝试使用一些函数作为回调来对用节点分割数组的规则进行回调。

这三个函数在第 1 部分被命名为 'selfOnly'，在第 2 部分被命名为 'transitionOnly'，在第 3 部分被命名为 'transitionInto'的细化。

refinement 函数采用类型的优化和转换。

Inisde of refinement 是一个函数，用于将节点移动到新组和 partitions 的一些迭代，它们的 parts 和搜索边。

然后使用类型相关的回调来决定某个节点是否要从实际组中分离出来。

function refinement(type, transition) {

    function move(source, target, index, pos) {
        if (pos === undefined) {
            pos = target.push(source.splice(index, 1)) - 1;
        } else {
            target[pos].push(source.splice(index, 1)[0]);
        }
        return pos;
    }

    partitions.forEach(function (parts) {
        var pos;
        if (parts.length === 1) {
            return;
        }
        parts.reduceRight(function (_, part, i) {
            edges.forEach({
                selfOnly: function (a) {
                    if (a[0] !== part || a[1] !== transition || a[2] !== part) {
                        return;
                    }
                    if (!edges.some(function (b) { return b[0] === part && b[1] !== transition && a[2] === part; })) {
                        pos = move(parts, partitions, i, pos);
                    }
                },
                transitionOnly: function (a) {
                    if (a[0] !== part || a[1] !== transition || a[2] === part) {
                        return;
                    }
                    pos = move(parts, partitions, i, pos);
                },
                transitionInto: function (a) {
                    if (a[1] !== transition || a[2] !== part) {
                        return;
                    }
                    pos = move(parts, partitions, i, pos);
                }
            }[type]);
        }, null);
    });
}

var nodes = ['s1', 's2', 's3', 's4', 's5'],
    edges = [['s1', 'a', 's2'], ['s2', 'a', 's2'], ['s3', 'a', 's4'], ['s4', 'a', 's4'], ['s5', 'a', 's5'], ['s1', 'b', 's3'], ['s3', 'b', 's5'], ['s5', 'b', 's5']],
    partitions = [nodes];

refinement('selfOnly', 'a');
console.log(partitions);
refinement('transitionOnly', 'a');
console.log(partitions);
refinement('transitionInto', 'b');
console.log(partitions);

.as-console-wrapper { max-height: 100% !important; top: 0; }