Unit Disk Graph

El jueves expuse en mi seminario de tesis; creo que me fue bastante bien. Pero lo importante (además del hecho de que por ello había estado demasiado ocupado para publicar en el blog) es que en un momento tuve que hacer la gráfica de una Unit Disk Graph; una gráfica donde los nodos están en el plano euclidiano, y dos de ellos están conectados (comparten una arista) si su distancia es menor o igual a uno.

Es un modelo obvio para redes inalámbricas si consideramos que todas las antenas tienen la misma potencia y definimos “uno” como el rango de la señal.

Ahora, lo interesante de hacer un ejemplo de gráficas de disco unitario, es que ésta sea conexa; es decir, que todo nodo pueda mandarle un mensaje a cualquier otro siguiendo una ruta a través de las aristas. Si uno hace a pie un ejemplo de 5 nodos la cosa se pone ya de hueva, porque uno tiene que estar midiendo que cada nodo esté a distancia uno o menor de al menos otro nodo.

Por supuesto, entonces uno quiere automatizar el proceso (yo quería un ejemplo de 50 nodos). La bronca es que si uno no tiene cuidado, todos los nodos (o una gran parte) terminan amontonados en alguna parte del marco donde uno esté trabajando. Recuerden que yo uso PStricks para mis gráficas en , así que lo que hice fue un programita en Java que generara 50 puntos aleatorios siguiendo el siguiente algoritmo:

1. El primer punto es completamente al azar.
2. El punto i elige a un “hermano” j al azar entre los otros i-1 puntos.
3. Se toma un ángulo α entre 0 y 360 grados (o 0 y 2π radianes, como les guste verlo), y una distancia d al azar entre 0.9 y 1.0, y las coordenadas de i son las de j desplazadas la distancia d en la dirección α, a menos que el punto se salga del marco (pasa probabilísticamente pocas veces; en el peor de los casos hay un 25% de probabilidad de que el punto resultante esté en el marco)
4. El punto que se obtuvo arriba es agregado si y sólo si se encuentra a distancia 0.5 o mayor de todos los demás puntos. Por esta condición el algoritmo se tarda un poco; para cada punto i, debe comprobar que esté “lejos” de los otros i-1 puntos. Y si el punto está demasiado “cerca” de otro, se repite el paso anterior y este.

Siguiendo este algoritmo, se obtienen gráficas bastante simpáticas: esta fue la que puse en mi presentación:

Unit Disk Graph

Por supuesto la idea del programita no era sólo generar los puntos aleatorios; lo chido es que me generó básicamente todo el código para PStricks. Yo sé que Java no es la mejor elección para estas cosas, pero la entrada y salida de ML me dio demasiados dolores de cabeza y mi Python está demasiado oxidado. Pensé en hacerlo con Perl, pero lo que realmente quería era un intérprete interactivo, así que me pasé a Java porque sencillamente me siento ahí cómodo. Pero a la próxima uso un lenguaje interpretado, seguro.

Como sea estuvo chido; utilicé programitas que me generaran el código PStricks en todos los casos excepto los más sencillos. Creo que terminaré haciendo una biblioteca para ciertas cosas geométricas comunes; nada más tengo que elegir con cuidado en qué lenguaje la quiero.