javascript - framework - Gráfico dirigido por la fuerza D3.js, reduce los cruces de borde haciendo que los bordes se repelan entre sí

framework d3

Question

Así que ya tengo una página que dibuja un gráfico de fuerza dirigida, como el que se muestra here .

Y eso funciona bien. Estoy usando el JS desde here , con algunos ajustes para extender los nodos ligeramente mejor.

Estas son más o menos las únicas diferencias:

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();

Donde la reducción de la fuerza del enlace parece hacer que los enlaces se parezcan más a los resortes, por lo que se vuelve similar a la técnica de Fruchterman & Reingold utilizada con frecuencia. Esto funciona razonablemente bien, pero solo para gráficos bastante pequeños. Con gráficos más grandes, el número de cruces simplemente sube, como era de esperar, pero la solución a la que aterriza normalmente no es óptima. No estoy buscando un método para obtener la solución óptima, sé que es muy difícil. Me gustaría que tenga algo de crudo que intente forzar las líneas y los nodos.

¿Hay alguna manera de agregar una repulsión en los enlaces, así como entre los nodos? No estoy familiarizado con la forma en que funciona la fuerza D3, y parece que no puedo encontrar nada que diga que esto sea posible ...

Answer 1

Algo que podría ser más fácil que tratar de repeler forzosamente los bordes es mover los nodos hasta que la cantidad de líneas de cruce en el sistema sea menor.

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

Comience con los nodos con la menor cantidad de conexiones y mueva hacia abajo.

Si intentas utilizar los bordes como nodos, sospecho que obtendrás los mismos problemas de bloqueo espacial. La solución está en descubrir dónde hay intersecciones de borde y si pueden resolverse. Es posible que no sea posible resolver muchos de los cruces de borde

Un enfoque más lateral a la visualización es animarlo de modo que solo muestre un subconjunto de nodos y conexiones a la vez. O para hacer que los bordes sean transparentes hasta que el usuario coloca el foco del mouse sobre un nodo, punto en el que los bordes asociados se vuelven más visibles.

Answer 2

He ''resuelto'' el problema con esto:

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

No es exactamente lo que queríamos, pero mejor que antes. Importend es que usted define un "nodo raíz" y lo solucionó.

nodes[0].fixed = true;

Parece más como un árbol, pero está más claro.

Answer 3

Seguí el ejemplo de Force Editor y vi que establecer los valores de charge y linkDistance resuelve el problema.

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

Captura de pantalla:

Answer 4

Lamentablemente, la respuesta a su pregunta no existe.

No hay un mecanismo integrado en D3 que repele los bordes o minimice los cruces de borde. Uno pensaría que no sería tan difícil implementar una carga en un borde, pero aquí estamos.

Además, no parece haber ningún mecanismo en ninguna parte que reduzca los cruces de borde en general. He examinado docenas de bibliotecas de visualización y algoritmos de diseño, y ninguno de ellos trata sobre la reducción de los cruces de borde en un gráfico genérico no dirigido.

Hay una serie de algoritmos que funcionan bien para gráficos planos, gráficos de 2 niveles u otras simplificaciones. dagre funciona bien en teoría para gráficos de 2 niveles, aunque la absoluta falta de documentación hace que sea casi imposible trabajar con él.

Parte de la razón para esto es que la distribución de gráficos es difícil . En particular, la minimización de los cruces de borde es NP-hard, por lo que sospecho que la mayoría de los diseñadores de diseño se topan con ese problema, golpean su cabeza contra el teclado unas cuantas veces y se dan por vencidos.

Si alguien tiene una buena biblioteca para esto, publíquelo para el resto de nosotros :)