Блок-схемы в d3js с использованием dagre-d3 или colajs

Ответ 1

Вот одно из решений проблемы: http://jsfiddle.net/5u9mzfse/

Более или менее меня просто интересовала эта актуальная проблема определения оптимального рендеринга, как это сделать алгоритмически.

Идея состоит в том, чтобы использовать тот факт, что порядок обрабатываемых узлов имеет значение, поэтому вы можете перетасовать заказ и найти порядок, который создает наилучшие результаты. Самый простой способ сделать это - проверить, сталкиваются ли перегородки строк, с которыми сталкиваются края. Здесь я предполагаю, что начало и конец ребер - достаточно хорошая оценка для ограничивающей рамки.

Края должны быть сначала сохранены в списке

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

Тогда

• Перетасовать список
• Удалить узлы
• Вычислить ограничивающие поля ребер из выходных
• Рассчитать, сколько ограничивающих полей перекрывается
• Если количество столкновений равно нулю, выводите вывод, в противном случае продолжайте до тех пор, пока не будут выполнены итерации 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 раундов для расчета оптимального порядка ребер, поэтому он выглядит так, как будто он может работать довольно хорошо, если диаграмма не слишком велика.