Partition Refinement Algorithm in JavaScript

Question

I have a set of nodes {s1,s2,s3,s4,s5} and some 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)

I have a partition refinement process illustrated in

In the first picture, I have all nodes in an Array (or Map?).

In every iteration, I want to reduce each block into subblocks. In the (only) block in the first picture, we see that s2 and s4 can do an a-transition (the two loops) but no b-transitions, while the remaining nodes s1, s3, s5 can do both a-transitions and b-transitions, so I partition them into two blocks {s1,s3,s5} and {s2,s4}.

In the next iteration, there is no difference for the block {s2,s4}, but in the other block, we see that s1 and s3 have a-transitions into the block {s2,s4} while s5 has an a-transition into its own block {s1,s3,s5}, so I partition s5 into its own block yielding {s1,s3}, {s5}, {s2,s4}.

Finally, I see that s3 has a b-transition into the block {s5} while {s1} do not have this, so I group s3 and s1 into separate blocks, yielding {s1}, {s3}, {s5}, {s2,s4}.

How can I implement this in JavaScript?

I guess it could be something like this

// 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

This is an attempt to use some function as callbacks for the rules for splitting the array with the nodes.

The three functions are named as 'selfOnly' for part 1, 'transitionOnly' for part 2 and 'transitionInto' for part 3 of refinement.

The refinement function takes type of refinement and transition.

Inisde of refinement is a function for moving a node to a new group and some iterations for partitions, their parts and the search in edges.

Then the type related callback is used to decide if some node is to separate from the actual group.

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; }