Frage D3.js force directed graph, reduziere Kantenübergänge, indem sich Kanten gegenseitig abstoßen


Ich habe also schon eine Seite, die einen kraftgerichteten Graphen wie den gezeigten zeichnet Hier.

Und das funktioniert gut. Ich benutze den JS von Hier, mit ein paar Verbesserungen, um die Knoten etwas angenehmer zu verteilen.

Dies sind mehr oder weniger die einzigen Unterschiede:

d3.json("force.json", function(json) {
  var force = d3.layout.force()
      .gravity(0.1)
      .charge(-2000)
      .linkDistance(1)
      .linkStrength(0.1)
      .nodes(json.nodes)
      .links(json.links)
      .size([w, h])
      .start();

Wo die Linkstärke abnimmt, scheint die Verbindung eher wie eine Feder zu wirken Fruchterman & Reingold Technik oft verwendet. Dies funktioniert einigermaßen gut, aber nur für relativ kleine Graphen. Bei größeren Graphen steigt die Anzahl der Kreuzungen - wie zu erwarten, aber die Lösung, auf der sie landet, ist normalerweise nicht optimal. Ich bin nicht auf der Suche nach einer Methode, um die optimale Lösung zu finden, ich weiß, das ist sehr schwierig. Ich möchte nur eine grobe Addition, die versucht, die Linien sowie die Knoten zu erzwingen.

Gibt es eine Möglichkeit, eine Abstoßung zwischen den Links und zwischen den Knoten hinzuzufügen? Ich bin nicht vertraut mit der Art, wie D3 Kraft funktioniert, und ich kann nichts finden, das sagt, dass das möglich ist ...


47
2017-08-17 13:50


Ursprung


Antworten:


Leider existiert die Antwort auf Ihre Frage nicht.

In D3 gibt es keinen eingebauten Mechanismus, der Kanten abstößt oder Kantenübergänge minimiert. Sie würden denken, dass es nicht so schwer wäre, eine Ladung an einer Kante zu implementieren, aber hier sind wir.

Außerdem scheint es keinen Mechanismus zu geben irgendwo das reduziert Kantenübergänge im Allgemeinen. Ich habe Dutzende von Visualisierungsbibliotheken und Layoutalgorithmen durchgesehen, und keiner von ihnen beschäftigt sich mit der Reduzierung von Kantenübergängen in einem generischen ungerichteten Graphen.

Es gibt eine Reihe von Algorithmen, die gut für planare Graphen oder 2-Level-Graphen oder andere Vereinfachungen funktionieren. Dagre funktioniert in der Theorie gut für 2-Level-Graphen, obwohl der völlige Mangel an Dokumentation es fast unmöglich macht, damit zu arbeiten.

Ein Teil des Grundes dafür ist, dass das Auslegen von Graphen ist hart. Insbesondere ist das Minimieren von Kantenübergängen NP-schwer, daher vermute ich, dass die meisten Layout-Designer dieses Problem lösen, ihren Kopf ein paar Mal gegen die Tastatur schlagen und aufgeben.

Wenn jemand eine gute Bibliothek dafür entwickelt, bitte veröffentlichen Sie es für den Rest von uns :)


9
2018-06-30 23:08



Etwas, das einfacher sein könnte, als zu versuchen, die Kanten abzustoßen, besteht darin, die Knoten herumzuwinden, bis die Anzahl der sich kreuzenden Linien im System geringer ist.

http://en.wikipedia.org/wiki/Simulated_annealing

Beginne mit den Knoten mit der geringsten Anzahl an Verbindungen und winkle runter.

Wenn Sie versuchen, die Kanten als Knoten zu verwenden, vermute ich, dass Sie nur die gleichen Probleme mit räumlicher Blockierung bekommen. Die Lösung besteht darin, herauszufinden, wo Kantenüberschneidungen vorhanden sind und ob sie aufgelöst werden können. Sie können feststellen, dass das Auflösen vieler Kantenübergänge nicht möglich ist

Ein lateralerer Ansatz für die Visualisierung besteht darin, sie so zu animieren, dass sie nur eine Teilmenge der Knoten und Verbindungen gleichzeitig zeigt. Oder um die Kanten transparent zu machen, bis der Benutzer den Mausfokus über einen Knoten legt, wodurch die zugehörigen Kanten besser sichtbar werden.


5
2017-11-29 19:27



Ich folgte dem Force Editor Beispiel und ich sah diese Einstellung charge und linkDistance Werte lösen das Problem.

  ...
  .charge(-200)
  .linkDistance(50)
  ...

Bildschirmfoto:

enter image description here


1
2017-08-08 07:16



Ich habe das Problem damit "gelöst":

nodes[0].x = width / 2;
nodes[0].y = 100;
nodes[0].fixed = true;
force.on("tick", function(e) {

    var kx = .4 * e.alpha, ky = 1.4 * e.alpha;
    links.forEach(function(d, i) {
      d.target.x += (d.source.x - d.target.x) * kx;
      d.target.y += (d.source.y + 80 - d.target.y) * ky;
    });
    [...]
 }

http://mbostock.github.io/d3/talk/20110921/parent-foci.html

Es ist nicht genau das, was wir wollten, aber besser als vorher. Wichtig ist, dass Sie einen "root" -Node definieren und reparieren.

nodes[0].fixed = true;

Es sieht eher wie ein Baum aus, aber so ist es klarer.


-1
2017-09-13 09:00