algorithm - Teoría de gráficos: algoritmo de autolayout basado en la fuerza

graph-theory force-based-algorithm

Question

Solo quiero comprobar que tengo mi teoría correcta antes de comenzar a implementar.

Constantes:

• m = masa del vértice (de todos modos, probablemente establezca esto en radio del nodo)
• k = fuerza de borde constante.
• l = longitud del borde en "estado mínimo de energía".

Variables:

• d = distancia entre dos vértices.
• cl = longitud actual del borde.

Teoría: cada vértice tiene una fuerza de repulsión en cada otro vértice que es: m / (d^2) . Para cada borde presenta una fuerza que los dos vértices "arrastran" en la dirección para llevar el borde al "estado mínimo de energía"; entonces cada vértice: -k * ((l - cl) / 2) .

Pseudocódigo:

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

Comentarios: ¿Esto funcionaría? ¿A qué debería ajustar k ?

Answer 1

Estás en las líneas correctas. Su terminología / física está un poco apagada: lo que está llamando masa y "k" está algo mezclado con lo que mejor se llamaría "carga" (para la repulsión de la ley del cuadrado inverso) y "constante de primavera" para el La atracción de la Ley Hooke.

Como se señala en las respuestas a los comentarios de su pregunta, sí necesita algo de amortiguación que en realidad le quite energía al sistema, de lo contrario, oscilará convirtiendo la energía potencial en energía cinética y regresará para siempre. Peor aún, los problemas de precisión de la simulación pueden conducir fácilmente a que la energía aumente indefinidamente y la simulación se "vuelva loca" si no tiene cuidado.

Este artículo de wikipedia tiene un buen pseudocódigo que encontrarás muy similar al tuyo, pero con los puntos anteriores tratados (aunque ten en cuenta que incluso ese pseudocódigo falta una división por masa en el cálculo de aceleración, consulta la discusión de la página).

También debe pensar un poco sobre la distribución inicial desde la que comenzará la simulación, y cuánto le preocupa la posibilidad de quedar atrapado en un mínimo local si existe (quizás) un mínimo mundial mucho mejor. Estos puntos están relacionados; mucho depende de la topología de su gráfico. Si es un árbol simple, tendrás pocos problemas para obtener un diseño agradable. Si tiene muchos bucles y estructura ... buena suerte.

Answer 2

No elegiría la misma m para cada vértice. En cambio, lo haría proporcional al número de otros vértices a los que está conectado. De esta forma, las extremidades de la gráfica que vuelan hacia su posición se alejan más rápido que las altamente conectadas.

No tengo idea para k.