javascript - D3js Force-directed graph 链接交叉点避免

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>

图像看起来像这样:

第一个问题是:如何避免这个十字路口？ 我知道我无法避开所有边缘交叉点，但我想将它们最小化。这个例子是一个没有循环的 TreeMap 。我知道有一种方法可以在没有边缘交叉的情况下构建它。但是我不知道如何用这个算法来做。
但还是烦人的十字路口。

第二个问题是:不及时模拟力(我不需要动画)而只是绘制最终结果怎么样？当我使用 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));

想法是让不相关的节点相互排斥，同时保持链接距离较短。

它在我的例子中工作得很好，但我的节点图比你的简单得多。