schematy blokowe w d3js przy użyciu dagre-d3 lub colajs

Question

Po obejrzeniu dość złożonego TCP state diagram example dagre-d3, doszłam do wniosku, że będzie on w stanie rozwiązać diagramy o podobnej złożoności. Na poniższym diagramie wyraźnie tak nie jest. Jeśli oba zaznaczone węzły zostały zamienione, wszystkie skrzyżowania zostałyby rozwiązane.

Inną ciekawą rzeczą jest to, że jak dobry wykres jest rozwiązany wydaje się zależeć od kolejności ustawić krawędzie.

następujący kod

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

nie dają takie same wyniki jak to:

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

Zobacz te dwa przykłady:

• perfect graph
• messed up graph

Jak sugeruje, starałem się używać cola.js zamiast, i to właśnie ten sam wykres wygląda następująco:

Jak widać, colajs jest lepszy na skrzyżowaniu redukcja, ale układ nie jest tak uporządkowany i jasny jak dagre. Używam następujące ustawienia dla colajs:

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

Czy jest możliwe aby skonfigurować colajs w sposób, który sprawia, że ​​wyglądają bardziej zorganizowany, podobny do dagre? I czy dagre po prostu nie jest w stanie rozwiązać czegoś takiego, czy też można go skonfigurować tak, jak jest?

Answer 1

Oto jedno rozwiązanie tego problemu: http://jsfiddle.net/5u9mzfse/

Mniej lub bardziej byłem zainteresowany tylko tego rzeczywistego problemu określania optymalnego renderowania, jak to osiągnąć algorytmicznie.

Chodzi o to, aby wykorzystać fakt, że kolejność renderowanych węzłów ma znaczenie, więc można przetasować zamówienie i znaleźć zamówienie, które zapewnia najlepsze wyniki. Najłatwiej to zrobić, sprawdzając, czy bouningujące pola linii, które tworzą krawędzie, zderzają się. Zakładam tutaj, że krawędzie początku i końca są wystarczająco estymowane dla obwiedni.

krawędzi powinny być najpierw zapisana w liście

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

Następnie

1. rekonfigurację listę
2. renderowania węzłów
3. oblicza obwiednie krawędzi z wyjścia
4. Oblicz, ile ramek granicznych pokrywa się
5. Jeśli liczba kolizji wynosi zero czyni wyjście, inaczej kontynuować aż max_cnt iteracje dotarty i wybierz najlepszy dotychczas

polach obwiedni krawędzi ze świadczonych wyjścia można znaleźć za pomocą coś jak to:

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

przed chwilą obliczyć czy pudełka zderzają, pomyślałem coś takiego dać około poprawne wyniki:

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

Wtedy wiesz, ile krawędzi krzyżuje się z tym zestawem krawędzi.

Następnie po każdej rundzie sprawdź, czy jest to najlepsza dotychczasowa tablica lub, jeśli nie ma kolizji, natychmiast zamknij;

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

Podczas testów przynajmniej z prostego wykresu algorytm wymaga 1-5 rund obliczyć optymalną kolejność krawędzi więc wygląda na to, że może działać całkiem dobrze przynajmniej, jeśli schemat nie jest zbyt duża.