Frutcherman's Algorithm

Este es un algoritmo que hice para una materia de mi facultad. Se intenta dibujar un grafo lo más 'lindo' posible, es decir, minimizando la cantidad de aristas que se cortan.
Funciona bajo un sistema de fuerzas. Los nodos se repelen naturalmente, pero las aristas añaden fuerza de atracción. En teoría cuando se simula este sistema el grafo tiende a un estado más ordenado, que es lo que estamos buscando.


El programa está hecho enteramente en Python, usamos pygame para mostrar en pantalla y interactuar con el mouse/teclado. Pueden ver el código acá:
http://codepad.org/pRGJsU1L


Para hacerlo nos basamos en el paper original. Pueden aprender más sobre este tipo de algoritmos acá:

Hicimos una sola modificación al estado de equilibrio de forma más rápida. A medida que el sistema se vuelve más estable, las fuerzas se reducen y se tarda más en llegar al estado de equilibrio. Por eso hicimos que las fuerzas sean modificadas por un valor creciente en el tiempo, al cual llamamos temperatura. Y por qué no empezamos con mucha temperatura directamente? En este caso el sistema se vuelve tan inestable que nunca se alcanzaría el equilibrio, en la práctica el grafo parece transformarse como en un "gas".

0 comentarios: