Grafos

Ordenación orgánica

A partir de la versión 1.2.0, Grafos cuenta con una nueva e interesante funcionalidad; se trata de la posibilidad de ordenar el grafo automáticamente de manera orgánica. Siga leyendo para comprender más sobre las posibilidades y uso de esta función.

Esta función de ordenación procura representaciones claras de grafos complejos. Es especialmente útil para la representación en áreas como:

- Bioinformática
- Redes empresariales
- Representación de conocimiento
- Gestión de sistemas
- Visualización de mallas

La ordenación orgánica se realiza mediante un algoritmo adaptado del 'Force-Directed graph drawing algorithm'. Cuando se calcula la distribución, los nodos son considerados como objetos físicos expuestos a fuerzas de repulsión entre ellos (como los electrones). Los arcos también tienen una analogía física y son considerados como muelles metálicos con cierto grado de elasticidad, de manera que producen fuerzas de atracción o repulsión en función de la distancia física entre sus extremos. Los muelles intentarán mantener unidos a los nodos de sus extremos a cierta distancia más o menos constante. Además, en este caso se han añadido otras fuerzas implicadas (gravitatoria respecto del baricentro, con los bordes del tapiz y de repulsión entre arcos cruzados). El algoritmo simula las fuerzas físicas implicadas y reordena la posición de los nodos en función de la suma total de fuerzas. El grafo evolucionará convergiendo hacia el estado de menor energía del sistema, aunque en este proceso puede quedar atrapado en un mínimo local.

La representación resultante, en la mayoría de los casos, muestra la simetría inherente y la estructura agrupada del grafo, con una distribución de nodos balanceada y con menos arcos entrecruzados.

Esta representación es la recomendada para la visualización de estructuras estelares, con anillos periféricos y con regiones conectadas vertebralmente. Tras la representación gráfica con este algoritmo, se identificará fácilmente la estructura de la red.

Ejemplo: Una vez que haya construido el grafo, vaya al menú Formato, y desde allí a la función Orgánica.

A continuación observará como el programa realiza los cálculos pertinentes y el grafo se va redibujando automáticamente de una manera más ordenada a cada paso. Puede repetir este proceso convergente varias veces, e incluso ayudar al programa en el proceso de optimización heurística moviendo algunos nodos que pueden quedar atrapados en alguna solución de mínimo local. Las siguientes imágenes muestran un ejemplo de ordenación orgánica desde una etapa inicial de situación caótica hasta la solución final.

Creative Commons License Alejandro Rodríguez Villalobos