D3js избегать пересечений силового направления графа

Question

Вот пример силового графа, который я пытался нарисовать с помощью d3.js.

У меня 3 больших вопроса. И это код (вы можете запустить фрагмент кода ниже, он может работать):

function getRandomInt(max, min = 0) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function fdSortShit(g, nodeDimensions) {
  const gNodes = [];
  const gLinks = [];
  g.children().forEach(child => {
    gNodes.push({
      id: child,
      w: nodeDimensions[child].w,
      h: nodeDimensions[child].h,
      radius:
        Math.sqrt(
          nodeDimensions[child].w * nodeDimensions[child].w + nodeDimensions[child].h * nodeDimensions[child].h
        ) / 2
    });
  });
  g.edges().forEach(edge => {
    gLinks.push({ source: edge.v, target: edge.w });
  });
  const data = {
    nodes: gNodes,
    links: gLinks
  };
  const nodes = data.nodes;
  const links = data.links;

  const linkNodeRad = 5;
  const linkNodes = [];
  links.forEach((link, idx) => {
    if (link.source != link.target) {
      linkNodes.push({
        id: `link-node-${idx}`,
        source: nodes.filter(e => {
          return e.id == link.source;
        })[0],
        target: nodes.filter(e => {
          return e.id == link.target;
        })[0],
        radius: linkNodeRad
      });
    }
  });

  const width = 800;
  const height = 600;

  var svg = d3
    .select("body")
    .append("svg")
    .attr("width", width)
    .attr("height", height)
    .attr("viewBox", "-400, -300, 800, 600");

  function forceSimulation(nodes, links) {
    return d3
      .forceSimulation(nodes)
      .force("link", d3.forceLink(links).id(d => d.id))
      .force("charge", d3.forceManyBody())
      .force("center", d3.forceCenter())
      .force(
        "collision",
        d3.forceCollide().radius(function(d) {
          return d.radius;
        })
      );
  }

  var link = svg
    .selectAll(".link")
    .attr("stroke", "#fff")
    .data(links)
    .enter()
    .append("line")
    .attr("class", "link");

  var node = svg
    .append("g")
    .selectAll("g")
    .data(nodes)
    .enter()
    .append("g");

  var circles = node
    .append("circle")
    .attr("class", "node")
    .attr("r", node => {
      return node.radius;
    });
  var text = node
    .append("text")
    .text(d => {
      return d.id;
    })
    .attr("class", "node-caption")
    .attr("x", 0)
    .attr("y", 0);

  var linkNode = svg
    .selectAll(".link-node")
    .data(linkNodes)
    .enter()
    .append("circle")
    .attr("class", "link-node")
    .attr("r", linkNodeRad);

  function ticked() {
    link
      .attr("x1", d => d.source.x)
      .attr("y1", d => d.source.y)
      .attr("x2", d => d.target.x)
      .attr("y2", d => d.target.y);

    node.attr("transform", function(d) {
      return "translate(" + d.x + "," + d.y + ")";
    });

    linkNode
      .attr("cx", function(d) {
        return (d.x = (d.source.x + d.target.x) * 0.5);
      })
      .attr("cy", function(d) {
        return (d.y = (d.source.y + d.target.y) * 0.5);
      });
  }

  forceSimulation(nodes.concat(linkNodes), links)
    .on("tick", ticked)
    .on("end", () => {
      console.warn("END");
    });
}
  
const coords = {};
const size = { min: 10, max: 30 };
const dotStr = "graph g { a--a;a--b;a--b;a--c;a--d;a--e;b--b1;c--c1;c--c2;d--d1;d--d2;d--d3;d--d4;e--e1;v--w;v--x;v--y;w--z;w--w1;x--x1;x--x2;y--y1;y--y2;y--y3;y--y4;z--z1;v--a; }";
const g = graphlibDot.read(dotStr);
g.children().forEach(child => {
  const x = getRandomInt(1024 - 10, 10);
  const y = getRandomInt(768 - 10, 10);
  coords[child] = {
    x: x,
    y: y,
    w: getRandomInt(size.max, size.min),
    h: getRandomInt(size.max, size.min)
  };
});

fdSortShit(g, coords);

svg {
  background-color: lightgray;
}
circle.node {
  fill: lightcoral;
}
circle.link-node {
  fill: rgba(0, 0, 255, 0.2);
  /* fill: transparent; */
}
line.link {
  stroke: lightseagreen;
}
text.node-caption {
  font: normal 10px courier new;
}

<script src="https://cdn.jsdelivr.net/npm/graphlib-dot@0.6.2/dist/graphlib-dot.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.7.0/d3.min.js"></script>

Изображение выглядит так:

Первый вопрос: что делать, чтобы избежать этих пересечений? Я знаю, что не могу увернуться от всех пересечений ребер, но хочу минимизировать их. Этот пример представляет собой древовидный граф без циклов. Я знаю, что есть способ построить его без пересечения краев. Но я не знаю, как это сделать с помощью этого алгоритма.
Но все равно раздражает пересечение.

Второй вопрос: как насчет НЕ для симуляции сил во времени (мне не нужна анимация), а только для того, чтобы получить окончательный результат? Когда я использую forceSimulation.on("end", cb) это здорово, но задержка между стартом и остановкой велика... но это только небольшой пример графика. Я не могу так долго ждать большего.

И третий вопрос.. как применить принудительно настроенные настройки? Сила энергии, жесткость, отталкивание, демпфирование и т. Д.? Не могу найти их на d3@5

Окончательный результат, которого хочет мой руководитель проекта:

• нет перекрытия узлов;
• минимизировать пересечения ребро-кромка;
• минимизировать пересечения ребер-узлов.

Я готов к диалогу.

Answer 1

Я решил эту проблему, поиграв с параметрами расстояния forceCollide и forceLink:

var simulation = d3.forceSimulation()                   
      .force('link', d3.forceLink().id(d => d.id).distance(100).strength(1))
      .force('charge', d3.forceManyBody())               // ^ change this value
      .force('collide', d3.forceCollide(110)) // change this value
      .force('center', d3.forceCenter(width / 2, height / 2));

Идея состоит в том, чтобы не связанные друг с другом узлы отталкивали друг друга, сохраняя при этом короткое расстояние между ними.

В моем случае это работает очень хорошо, но мой граф узлов намного проще, чем ваш.

Answer 2

Вы применяете настройки силы в части инициализации. Вот пример -

var simulation = d3.forceSimulation()                              //Modify link distance/strength here
    .force("link", d3.forceLink().id(function (d) { return d.id; }).distance(80).strength(1))
    .force("charge", d3.forceManyBody().strength(-15)) //Charge strength is here
    .force("center", d3.forceCenter(width / 2, height / 2));

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

Побочным эффектом сильно отрицательного заряда является то, что график устанавливается довольно быстро, и, поскольку вы не хотите моделировать силы в реальном времени после начального отображения, вы можете вызвать simulation.stop() заморозить или остановить симуляцию.