パーティション洗練アルゴリズムのJavaScript

Question

にIノード{S1、S2、S3、S4、S5}、一部のエッジのセットを有する：

• を（S1、S2）
• （S2、 S2）
• （S3、S4）
• （S4、S4）
（S5、S5）

• （S1、B、S3）

• （S3、B、S5）
• （S5、B、S5）

Iは最初の画像で

に示すパーティション精緻化プロセスを持っている、私はすべて持っていますノードはArray（またはMap？）です。

各繰り返しで、各ブロックをサブブロックに分割したいと思います。最初のピクチャの（only）ブロックでは、s2とs4はaトランジション（2つのループ）を実行できますが、bトランジションは実行できませんが、残りのノードs1、s3、s5はaトランジションとb遷移になるので、それらを{s1、s3、s5}と{s2、s4}の2つのブロックに分割します。

ブロック{s2、s4}には違いはありませんが、もう一方のブロックでは、s1とs3はブロック{s2、s4}にa-遷移し、s5は自分のブロック{s1、s3、s5}に遷移するので、s5を{s1、s3}、{s5}、{s2、s4}を生成する独自のブロックに分割します。

最後に、S3は、ブロック{S5}にB-遷移を有していることがわかり、一方、{S1}行うない別々のブロックにこのため、I群S3及びS1、降伏を有する{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関数は、洗練とトランジションのタイプを取ります。 refinementの

Inisdeは、新しいグループにノードを移動するための機能とpartitions、そのpartsのためのいくつかの反復とedgesで検索です。

次に、タイプ関連のコールバックを使用して、ノードが実際のグループから分離するかどうかを判断します。

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