DOT Language

Investigando un poco por la red (haciendo trabajo de campo) he encontrado varias librerías relacionadas con el tema de grafos. Ya que estoy desarrollando una herramienta que generará grafos (dirigidos - no dirigidos) y que además implementará un algoritmo para la búsqueda de caminos, pues no está nada mal lo que ya hay por la red y que me resulta tan interesante. Ahora que ya tengo bastante avanzado el proyecto VLO (a ver si en un par de semanas lo avanzo un poco más y os muestro en lo que he estado trabajando recientemente) ahora estoy intentando reordenar los grafos aplicando algoritmos de dibujado Force-Directed. Éstos permiten posicionar los nodos de una manera más elegante asignado propiedades físicas a cada uno de éstos.

Utilizando éstos Algoritmos llamados Force-based o Force-Directed podremos generar diagramas tan espectaculares como los siguientes:

Éstos diagramas los he sacado de aiSee graph Visualization, donde podemos encontrar muchos ejemplos sobre diferentes diagramas.

Como indica el título del artículo, aquí os comentaré un poco el lenguaje DOT. Éste lenguaje es del tipo plano donde aplicando un pequeño trozo de código, podemos llegar a crear diagramas sin tener que preocuparnos de su dibujado.

Por ejemplo el siguiente script:

digraph if {
graph [rankdir=LR];
node [label="\N"];
graph [bb="0,0,218,108"];
{
graph [rank=same,
 bb=""];
b [pos="119,18", width="0.75", height="0.5"];
c [pos="119,90", width="0.75", height="0.5"];
}
a [pos="27,18", width="0.75", height="0.5"];
a -> b [pos="e,91.77,18 54.105,18 62.732,18 72.431,18 81.65,18"];
c -> b [label="long long long", pos="s,119,71.831 119,36.413 119,44.059 119,53.108 119,61.573", lp="168.5,54"];
}

crea el siguiente grafo en un servicio online utilizando el lenguaje DOT.

Es bastante interesante ya que podemos tener herramientas que generen éstos pequeños scripts y luego instalar un servicio de renderizado de grafos y ver el resultado en una imagen.

Podemos encontrar librerías para diferentes SO que utilizan éste lenguaje. Una de éstas es Graphviz (Graphic visualization Software) un paquete Open Source que contiene una serie de librerías para la visualización y generación de grafos. He encontrado varias aplicaciones por la red que utilizan ésta librería y quería indagar un poco más sobre éste tema.

En la web de Graphviz podréis encontrar la última versión estable del paquete e incluso el código fuente para ver los diferentes algoritmos que utilizan.

Si miramos en la galería de imágenes podemos encontrar grafos con una estética muy buena:

Además recomiendo la lectura de los diferentes documentos de ayuda que contienen referéncias muy buenas a diferente bibliografía relacionada con el tema de los grafos. Uno de los libros que yo recomiendo es el siguiente:

Thomas M. J. Fruchterman and Edward M. Reingold. Graph Drawing by Force- directed Placement. Software– Practice and Experience, 21(11):1129–1164, November 1991

Dentro de la propia arquitectura del Graphviz, podemos encontrar las diferentes aplicaciones que modelan los grafos y los posicionan en función del algoritmo seleccionado. En su caso, dispone de los programas NEATO, TWOPI, CIRCO, FDP, DOTTY y LEFTY. Cada uno de éstos tiene un tipo de posicionamiento diferente, ordenando los diagramas en formas circulares, de redes, etc. Todo para que el dibujo final sea mucho más inteligible.

Además desde la página principal de Graphviz, encontramos WebDot, un servicio web que nos permite generar diagramas utilizando el lenguaje DOT y que nos devuelve el resultado en HTML.

Es increíble el trabajo realizado por todas las personas involucradas en el proyecto, la verdad es que me ha gustado mucho y sobretodo por la información y documentación que hay. Podemos aprender mucho de ellos y sobretodo consultar la bibliografía recomendada para poder introducirnos un poco más sobre la teoría de grafos. También os recomiendo ver el siguiente vídeo que muestra gráficamente como funciona un algoritmo de éste tipo.

Podría hacer el artículo mucho más extenso, pero prefiero dejarlo aquí y si queréis indagar un poco más, os dejo una serie de enlaces de interés muy interesantes desde donde poder continuar con la investigación.

Espero que os hay entretenido la lectura, y espero vuestros comentarios!.

• Enlaces de interés:

OmniGraffle.
vizierfx a Flex Library for GraphViz rendering.
aiSee graph visualization.
force-directed node interface.
Webdot demo graphs.
DOT Tutorial.
Force directed layouts.
Force directed Algorithm (Spring Algorithm).
aiSee graph gallery.
Visual Complexity.
more Force Directed in google.