15

dagre-d3の非常に複雑なTCP 状態図の例を見た後、同様の複雑さの図を解決できると考えました。次の図では、明らかにそうではありません。2 つのマークされたノードが交換された場合、すべての交差が解決されます。 dagre と d3.js を使用して作成された図

もう 1 つの興味深い点は、グラフがどれだけうまく解決されるかは、エッジを設定した順序に依存するように見えることです。

次のコード

g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });
g.setEdge("148570019_1100", "148570010_1100", { label: "" });

これと同じ結果は得られません:

g.setEdge("148570019_1100", "148570010_1100", { label: "" });
g.setEdge("148570019_1100", "148570020_1100", { label: "" });
g.setEdge("148570019_1100", "148570021_1100", { label: "" });

次の 2 つの例を参照してください。

示唆されたように、代わりにcola.jsを使用しようとしましたが、同じグラフは次のようになります。 cola.js と d3.js を使用して作成された図

ご覧のとおり、colajs はクロス リダクションで優れていますが、レイアウトは dagre ほど構造化されておらず、明確ではありません。colajs には次の設定を使用します。

cola.d3adaptor()
      .avoidOverlaps(true)
      .convergenceThreshold(1e-3)
      .symmetricDiffLinkLengths(20)
      .flowLayout('x', 150)
      .size([width, height])
      .nodes(nodes)
      .links(edges)
      .constraints(constraints)
      .jaccardLinkLengths(300);

dagre と同様に、より構造化されたように見えるように colajs を構成することは可能ですか? そして、dagre は単にこのような問題を解決できないのでしょうか、それともそのように構成することは可能でしょうか?

4

1 に答える 1

9

問題の解決策の 1 つを次に示します: http://jsfiddle.net/5u9mzfse/

多かれ少なかれ、最適なレンダリングを決定するという実際の問題、それをアルゴリズムで達成する方法に興味がありました。

アイデアは、レンダリングされたノードの順序が重要であるという事実を利用することです。そのため、順序をシャッフルして、最良の結果を生み出す順序を見つけることができます。これを行う最も簡単な方法は、エッジが形成する線のバウニング ボックスが衝突するかどうかをテストすることです。ここでは、エッジの開始点と終了点がバウンディング ボックスの十分な推定値であると想定しています。

エッジは最初にリストに保存する必要があります

var edgeList = [["10007154_1100","148570017_1100",{"label":""}, ...]

それで

  1. リストをシャッフルする
  2. レンダリング ノード
  3. 出力からエッジの境界ボックスを計算します
  4. 境界ボックスが重なっている数を計算する
  5. 衝突回数がゼロの場合は出力をレンダリングし、そうでない場合はmax_cnt回の反復が実行されるまで続行し、これまでで最良のものを選択します

レンダリングされた出力からのエッジの境界ボックスは、次のようなものを使用して見つけることができます。

  var nn = svg.select(".edgePaths");
  var paths = nn[0][0];
  var fc = paths.firstChild;
  var boxes = [];
  while(fc) {
     var path = fc.firstChild.getAttribute("d");
     var coords = path.split(/,|L/).map(function(c) {
         var n = c;
         if((c[0]=="M" || c[0]=="L")) n = c.substring(1);
         return parseFloat(n);
     })
     boxes.push({ left : coords[0], top : coords[1], 
            right : coords[coords.length-2], 
            bottom : coords[coords.length-1]});
     fc = fc.nextSibling;
  }

ボックスが衝突するかどうかを計算するだけで、次のようなものがほぼ正しい結果をもたらすと考えました。

  var collisionCnt = 0;
  boxes.forEach( function(a) {
         // --> test for collisions against other nodes...
         boxes.forEach(function(b) {
             if(a==b) return;
             // test if outside
             if ( (a.right  < b.left) || 
                  (a.left   > b.right) || 
                  (a.top    > b.bottom) || 
                  (a.bottom < b.top) ) {

                  // test if inside
                  if(a.left >= b.left  && a.left <=b.right 
                  || a.right >= b.left  && a.right <=b.right) {
                     if(a.top <= b.top && a.top >= b.bottom) {
                        collisionCnt++;
                     }
                     if(a.bottom <= b.top && a.bottom >= b.bottom) {
                        collisionCnt++;
                     }                 
                  }
             } else {
                collisionCnt++;
             }
         })
      })

次に、この一連のエッジと交差するエッジの数がわかります。

次に、各ラウンドの後に、これがこれまでで最高の配列であるかどうか、または衝突がない場合はすぐに終了することを確認します。

if(collisionCnt==0) {
     optimalArray = list.slice();
     console.log("Iteration cnt ", iter_cnt);
     break; 
 } 
 if(typeof(best_result) == "undefined") {
    best_result = collisionCnt;
 } else {
    if(collisionCnt < best_result) {
        optimalArray = list.slice();
        best_result = collisionCnt;
    }
 }

少なくとも単純なグラフを使用したテスト中、アルゴリズムはエッジの最適な順序を計算するために 1 ～ 5 ラウンドを必要としたため、少なくともダイアグラムが大きすぎない場合は非常にうまく機能するように見えます。

于 2016-03-20T11:32:53.410 に答える