diagrammi di flusso in d3js utilizzando dagre-d3 o colajs

Question

Dopo aver visto il complesso TCP state diagram example di dagre-d3, ho pensato che sarebbe stato in grado di risolvere diagrammi di complessità simile. Nello schema seguente, questo chiaramente non è il caso. Se i due nodi contrassegnati sono stati scambiati, tutti gli incroci sarebbero stati risolti.

Un'altra cosa interessante è che come buono il grafico viene risolto sembra dipendere dall'ordine regolano i bordi in.

il seguente codice

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

non dà gli stessi risultati come questo:

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

vedere questi due esempi:

• perfect graph
• messed up graph

Come suggerito, ho cercato di usare cola.js invece, e questo è ciò che nello stesso grafico si presenta come:

Come si vede, colajs è meglio a incrocio riduzione, ma il layout non è così strutturato e chiaro come quello di Dagre. Io uso le seguenti impostazioni per colajs:

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

E 'possibile configurare colajs in un modo che lo fa apparire più strutturato, simile a Dagre? E Dagre semplicemente non è in grado di risolvere qualcosa del genere, o è possibile configurarlo in un modo che è?

Answer 1

Qui è una soluzione al problema: http://jsfiddle.net/5u9mzfse/

Più o meno ero solo interessata di questo vero e proprio problema di determinare la resa ottimale, come il raggiungimento di tale algoritmicamente.

L'idea è di utilizzare il fatto che l'ordine dei nodi renderizzati è importante, quindi è possibile mischiare l'ordine e trovare l'ordine che crea i migliori risultati. Il modo più semplice per farlo è quello di verificare se le scatole di bouning delle linee che formano i bordi si scontrano. Qui presumo che i bordi inizio e fine siano una stima abbastanza buona per il riquadro di delimitazione.

I bordi occorre innanzitutto salvate nella lista

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

Poi

1. Mescola lista
2. rendono nodi
3. Calcolare i riquadri di delimitazione dei bordi dall'uscita
4. Calcola quante caselle di delimitazione si sovrappongono
5. Se il conteggio di collisione è zero rendere l'uscita, altrimenti continuano fino max_cnt iterazioni sono stati eseguiti e selezionare il migliore finora

I riquadri di delimitazione dei bordi del output di rendering può essere trovato con qualcosa di simile questo:

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

La basta calcolare se le caselle si scontrano, ho pensato una cosa del genere danno risultati circa corretti:

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

Quindi sai quanti bordi si incrociano con questo set di bordi.

Quindi, dopo ogni giro, verificare che questo sia l'array migliore che abbiamo finora, o se non ci sono collisioni uscite immediatamente;

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

Durante il test almeno con un semplice grafico l'algoritmo richiesto 1-5 giri per calcolare l'ordine ottimale dei bordi in modo che sembra che potrebbe funzionare abbastanza bene almeno se il diagramma non è troppo grande.