Un gráfico es una estructura de datos que representa un
conjunto de entidades, denominadas nodos, conectados mediante un
conjunto de enlaces. A los nodos también se les denomina vértices. A
los enlaces también se le denomina aristas o conexiones. En las
aplicaciones prácticas, frecuentemente se utilizan gráficos para
modelar un gran número de cosas: redes informáticas, estructuras de
programas de software, diagramas de gestión de proyectos, etc. Los
gráficos son modelos muy eficaces porque permiten que las
aplicaciones se beneficien de los resultados de la investigación en
el campo de la teoría de grafos. Por ejemplo, existen métodos muy
eficientes para buscar el camino más corto entre dos nodos, el camino
de coste mínimo, etcétera.
Diseño de un gráfico
Se utiliza en las interfaces de usuario gráficas de
aplicaciones que necesitan mostrar modelos de gráficos. Diseñar un
gráfico significa dibujar el gráfico de modo que se genere una
representación adecuada y legible. Básicamente, esto implica
determinar la ubicación de los nodos y la forma de los enlaces. Para
algunas aplicaciones, la ubicación de los nodos ya se conoce (por
ejemplo, a partir de posiciones geográficas de los nodos). Para otras
aplicaciones, la ubicación no se conoce (un gráfico “lógico” puro) o
sí se conoce, pero si se utiliza, generaría un dibujo del gráfico
ilegible. En estos casos, debe calcularse la ubicación de los nodos.
¿Qué se entiende por representación “adecuada” de un
gráfico? En las aplicaciones prácticas, para la representación del
gráfico a menudo es necesario observar determinados criterios de
calidad. Estos criterios pueden variar en función del campo de
aplicación o de un estándar determinado de representación. Suele ser
difícil decir qué en que consiste un buen diseño. Cada usuario puede
tener distintos criterios, subjetivos, de lo que considera que es un
“buen” diseño. Sin embargo, existe un objetivo común tras todos los
criterios y estándares: la representación debe ser fácil de entender
y permitir una navegación sencilla a través de la estructura compleja
del gráfico.
¿Qué es un buen diseño?
Para hacer frente a las necesidades de distintas
aplicaciones, se han desarrollado muchas clases de algoritmos de
diseño de gráficos. Un algoritmo de diseño aborda uno o más criterios
de calidad, según el tipo de gráfico y las características del
algoritmo, al diseñar un gráfico.
Los criterios más comunes son estos:
- Minimizar el número de link crossings
- Minimizar el área total del dibujo
- Minimizar el número de curvas (en dibujos ortogonales)
- Maximizar el ángulo más pequeño formado por enlaces incidentes consecutivos
- Maximizar la visualización de simetrías
¿Cómo puede satisfacer un algoritmo de diseño los
criterios de calidad y los estándares de representación? Si examina
cada uno de los criterios, algunos se pueden satisfacer con
facilidad, al menos para algunas clases de gráficos. Para otras
clases, puede ser difícil generar un dibujo que cumpla los criterios. Por ejemplo, minimizar el número de intersecciones de
enlaces es relativamente simple para los árboles (es decir, gráficos
sin ciclos). Para gráficos generales, minimizar el número de
intersecciones de enlaces es un problema matemático
NP-complete
(es decir, con todos los algoritmos conocidos, el tiempo necesario
para ejecutar el diseño aumenta rápidamente conforme lo hace el
tamaño del gráfico).
Si desea satisfacer varios criterios al mismo tiempo,
puede que no exista una solución óptima para todos ellos, ya que
muchos de los criterios se contradicen mutuamente. Hay que llegar a
un compromiso sobre el tiempo que se puede dedicar a buscar la
solución. Además,
asignar pesos a cada criterio no es una tarea trivial. La
optimización de varios criterios a la vez es, la mayoría de las
veces, una tarea demasiado compleja y que lleva demasiado tiempo. Por
ello, los algoritmos de diseño suelen estar basados en métodos
heurísticos y puede que ofrezcan soluciones menos óptimas con
respecto a uno o varios criterios. Afortunadamente, en la práctica,
los algoritmos de diseño a menudo proporcionan representaciones
razonablemente legibles.
Métodos para utilizar algoritmos de diseño
Los algoritmos de diseño pueden utilizarse de varias
formas en las distintas aplicaciones en que se utilizan. Las formas
más habituales de utilizar un algoritmo son:
-
El algoritmo de diseño lo hace todo sin la intervención del usuario, excepto quizás la elección del algoritmo de diseño que se va a utilizar. A veces, puede programarse un conjunto de reglas para elegir automáticamente (y dinámicamente) el algoritmo de diseño más adecuado para el tipo concreto de gráfico que se va a diseñar.
-
El usuario de la aplicación puede mejorar libremente el resultado del procedimiento de diseño automático a mano. En algunos casos, el usuario puede mover y “fijar” nodos en las posiciones que desee y volver a ejecutar el diseño. En otros casos, una parte del gráfico se establece automáticamente como “de sólo lectura” y el usuario puede modificar el resto del diseño.
- Diseño desde ceroEl algoritmo de diseño se rehace del todo (“desde cero”) cada vez que el gráfico se modifica.
- Diseño incrementalCuando el algoritmo de diseño se ejecuta por segunda vez en un gráfico modificado, intenta conservar la estabilidad del diseño en la medida de lo posible. El diseño no se vuelve a ejecutar desde cero. El algoritmo de diseño también intenta ahorrar tiempo de CPU utilizando el diseño anterior como solución inicial. Algunos algoritmos y estilos de diseño son incrementales por naturaleza. En otros casos, el diseño incremental puede ser imposible.