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!.
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.