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.

New features with VLO framework part IV

Ultimando detalles del editor de objetos sobre un canvas de delphi, aquí os dejo la última modificación permitiendo así poder mover los diferentes componentes de la pantalla con total libertad. Con ésta nueva versión ya casi está listo el editor con el que podré crear diagramas mucho más complejos y con una estructura más intelijible y más bonita. Aún me queda el tema de centrar el texto dentro de Tbox, pero aún me estoy pensando si va a ser útil o no (además no es fácil hacer el cálculo y tengo que calcular el tiempo que voy a invertir).

La modificación ha sido relativamente fácil ya que dispongo de los diferentes métodos de movimiento sobre Tbox, luego solo tengo que ir a los enlaces, buscar los diferentes Tbox asociados (origen, destino) y mover los puntos de éste permitiendo así mover el diagrama completamente.

Además he añadido 2 propiedades nuevas para poder personalizar el editor, una que nos permite cambiar el color de fondo y otra el color de la grid.

Ahora podemos visualizar los diagramas de la siguiente manera:

Aquí os dejo también uno de mis famosos vídeos a los que ya me estoy empezando a aficionar, ya que de una manera fácil y rápida os puedo mostrar las diferentes modificaciones de la plataforma y podéis ver el resultado.

También os dejo la aplicación de test para probar el componente:

• Test framework v2.0.0 build 290.rar (with data)

New features with VLO framework part III

Siguiendo mi planning ya tengo casi acabada la versión básica de la plataforma con la que trabajaré posteriormente las diferentes aplicaciones que tengo en mente. En ésta última versión, me he centrado sobretodo en la edición y en pulir sobretodo el tema de los eventos de teclado y que toda la gestión de diagramas sea fácil y cómoda de utilizar. Solo me queda un punto pendiente antes de sacar el último release y poder centrarme en las aplicaciones que ya se están desarrollando en ramas diferentes pero que comparten un ancestro común en la plataforma VLO.

En dicha versión puedo destacar:

• Mejora de la creación, carga y eliminación de proyectos
• Mejora de los eventos de teclado (CTRL+C, +V, etc)
• Creación de pantalla de propiedades sobre la aplicación
• Corrección en la clonación de objetos

Aquí os dejo la versión para testearla totalmente libre de descarga:

• TestFramework v2.0.0 build 269.rar (with data)

Ahora con un poco de imaginación, podemos llegar a crear diagramas como el siguiente:

Aún tengo que acabar 2 puntos pendientes que tratan sobre el centrado del texto en función de las dimensiones de la caja y el arrastrado de los puntos de las líneas que aún estoy a medias con el desarrollo, pero que en la siguiente entrega estará resuelto.

Aquí os dejo también un vídeo sobre las últimas mejoras de la plataforma y como ha mejorado su utilización:

Espero que os guste y no dudéis en contactar conmigo sobre cualquier bug que encontréis en la aplicación así como idea que tengáis.

New features with VLO framework part II

Ya está disponible el último release estable de la aplicación con las últimas modificaciones en las que he estado trabajando éstos días. Ya se ha ahora publico poco, pero no tengo mucho tiempo libre y necesito priorizar tareas. En ésta última versión podréis ver que ya casi tengo acabado el componente con todas las opciones gráficas necesarias para el posterior desarrollo de nuevas aplicaciones utilizando un entorno gráfico para mostrar los resultados.

También os dejo un vídeo explicativo con las nuevas funcionalidades que permiten rapidez, comodidad y flexibilidad a la hora de crear nuevos diagramas pudiendo crear propiedades por defecto, propagarlas y editarlas. Si os acordáis de Thundax Box Manager, ésta aplicación utiliza por defecto la plataforma VLO v1.0, pues ahora con las mejoras introducidas, la edición se hará mucho más corta y rápida.

La estructura de las clases ha cambiado un poco, aquí podemos ver la nueva estructura UML de las clases TAbstractLine, TBox y TAbstractProperty que son las principales para el desarrollo de los componentes visuales:

Aquí os dejo el vídeo con las cosas más interesantes:

Como podéis ver, aparece un nuevo editor de propiedades por defecto. Con éste editor podemos predefinir como queremos que sean nuestras boxes en su primera instancia y sus conectores. De ésta manera podemos crear documentos más interesantes y atractivos visualmente:


Así, podemos crear documentos como el siguiente:

• Download test framework v2.0.0 build 185.rar (with data)

New features with VLO framework part I

Aquí os dejo varios de los últimos vídeos con las características más destacables de la plataforma. A modo de resumen comento que el componente ha mejorado en velocidad y en rendimiento. Además de que permito la creación de bucles en una misma TBox, de ésta manera como comenté en uno de mis últimos posts, ésto me servirá para poder crear una pequeña aplicación para el análisis de DFA (Deterministic Finite Automaton) y así ampliar las diferentes opciones que tenemos para utilizar VLO Framework.

De ésta manera podríamos llegar a generar diagramas como el siguiente:


Aquí os dejo el vídeo y el programa de test para que podáis hacer vuestros propios diagramas:

• Download test framework v2.0.0 build 40 (with Data).

Playing with VLO Framework

Bueno después de tantos días de intenso trabajo en los que parecía que nunca iba a acabar, por fin tengo los primeros vídeos sobre la utilización de mi plataforma (VLO Framework). En éstos vídeos muestro las últimas características de la aplicación y de ésta manera queda mejor explicado (una imagen vale más que mil palabras). En éstos 2 primeros vídeos introductorios, muestro la potencia en lo que refiere a edición de cajas (movimiento, copiar-pegar, eliminar, arrastrar, etc), y en el segundo muestro unos ejemplos sobre lo que luego vendrá (su utilización en diferentes aplicaciones que ya tengo en desarrollo).

Vídeo 1 : Playing with VLO Framework

Vídeo 2 : Making diagrams with VLO Framework

Los vídeos los he hecho con el camtasia Studio, una herramienta increíble para la edición de vídeos y para crear producciones para youtube y la web en general. Hay un vídeo de dougstech.com que me ha ayudado bastante en la generación de los vídeos.

Podéis descargar la última versión de prueba de la plataforma aquí:

• Canvas test Framework v2.rar (with data)

Plataforma de desarrollo : VLO Framework parte III

Ahora que tengo un poco más avanzada la parte del cálculo de rutas ya puedo entretenerme un poco más con el diseño del canvas para mejorar un poco el comportamiento del dibujado de los diferentes elementos que forman VLO Framework. En ésta última versión he incorporado cosas importantes como:

• una grid de fondo
• la acción snap to grid
• la edición de líneas por 3 puntos
• la múltiple selección de cajas
• el movimiento global de las cajas con la múlti selección
• el Conexionado de boxes de origen a destino y viceversa (en versiones anteriores, solo se permitía una conexión)

De ésta manera la aplicación se muestra de la siguiente forma:


Ahora, importando imágenes, podemos realizar diagramas típicos como los siguientes:

Utilizando la herramienta de selección, podemos seleccionar todos los componentes Tbox y moverlos utilizando el mouse:


Lo interesante de la plataforma es que la podemos utilizar para dibujar aquello que queramos (imágenes enlazadas) y luego utilizar éstos componentes visuales para modelar aquello que queremos programar. Por ejemplo el siguiente paso será crear un comprobador de DFA (Deterministic finite machine), y a partir de ahí cualquier cosa que se nos ocurra gráficamente. De ésta manera podemos llegar a mejorar bastante la ilustración de nuestros modelos, por ejemplo en uno de mis anteriores diagramas sobre el cálculo de rutas, ahora tendríamos ésto:

Aquí os dejo una muestra del test del framework para que comprobéis su comportamiento:

• test Framework.exe

VLO framework on SourceForge

Ya podéis encontrar la última versión de mi framework (VLO) en SourceForge. Aún estoy ultimando detalles, pero podréis encontrar el último ejecutable en descarga libre desde el siguiente enlace: vloframework.sourceforge.net.

Desde la misma web podréis descargar la aplicación, informar sobre errores y contactar conmigo sobre cualquier cosa referente a la aplicación. Aún estoy acabando de configurar el repositorio para poder subir el código fuente de la plataforma, pero en un par de días lo tendré listo. Estoy trabajando sobre la configuración básica de la plataforma mejorando el comportamiento de los diferentes objetos visuales y pensando en las diferentes posibilidades que tiene la plataforma sobre diferentes ideas que me han expuesto y algunas otras que se me han ocurrido a mi.

Cálculo de rutas de transporte parte V

En éste artículo os entrego la última versión de la aplicación con mejoras adicionales sobre la selección de caminos. Continuando con la IV parte, he modificado ligeramente el algoritmo para identificar y marcar diferentes destinos en función de un parámetro situado en la propia conexión. Por ejemplo, si nos encontramos en un ítem que tiene 2 caminos a seguir, éstos deben estar numerados para indicar cual tomar.

Si éste elemento es un dispositivo físico, de alguna manera deberá posicionarse para dirigirse hacia un sitio u otro. De ésta manera si nos encontramos con la siguiente situación:

Indicamos numéricamente que si queremos ir del dispositivo 40 al 11, éste debe estar en su posición '2' y si quiere dirigirse hacia el 39, en la posición '1'. Físicamente representaría que por ejemplo una válvula debe estar posicionada en un sentido (abierta) para acceder a 11 y cerrada para 39 por ejemplo. De éstos ejemplos encontraremos muchísimos en la selección de caminos, y es interesante pararse un momento y pensar sobre éstos y buscar una solución elegante.

De momento he hecho que el nombramiento de las conexiones sea automático y sin ningún orden. Camino que selecciono, camino que marco. Ahora el cálculo es más eficiente, más rápido y con mejor disponibilidad a la hora de hacer pequeños cálculos para obtener éstos parámetros.

Si nos fijamos en el siguiente ejemplo:

Veréis que cada enlace está marcado y cuando generamos la salida para el cálculo de rutas, podemos ver como identifica cada uno de los nodos:

En verde se marcan los orígenes, en azul los elementos bloqueados y en fucsia los destinos. Además ésta versión dispone de las siguientes mejoras:

• Selección total de los nodos
• Movimiento total de los nodos mediante botones
• Enlaces de bloqueo identificados en azul (no se editarán)

Aquí os dejo la última versión:

• ThundaxBoxManager 2.5.0 build 70 (with Data)

Cálculo de rutas de transporte parte IV

En ésta entrega, hago el primer desarrollo profesional de mi framework VLO sobre un ejemplo real para el cálculo de rutas. Como ya sabéis, el VLO framework es una plataforma de desarrollo desarrollada en Delphi 2010 que pretende obtener un vínculo gráfico con un Objeto. De ésta manera esa porción de memoria que estamos utilizando se está representado en pantalla utilizando una serie de conceptos gráficos. Llevo trabajando en éste proyecto unos 2 meses y medio y como podéis ver, si se planifica bien el trabajo, se tienen las ideas claras y partimos con un buen background en orientación a objetos y diseño utilizando patrones podemos crear herramientas increíbles.

Luego vino la implementación de la plataforma sobre ejemplos reales, al principio podía crear diagramas de grafos y calcular la ruta más corta utilizando Dijkstra. Después le di una parte mucha más gráfica y implementé un sistema multi capas para poder disponer de texto, imagen y caja en el mismo componente. A partir de ahí y con otras muchas ideas (gracias a los morning pages) apareció el cálculo de rutas. Hace ya bastantes años que me dedico al sector de la automatización industrial y la mayoría de aplicaciones que desarrollo son para cumplir los requisitos que necesitan éste tipo de industria.

Por lo tanto, continuando con ésta última versión de la aplicación, veréis que hay un pequeño cambio y es que ahora ya tengo implementado el algoritmo para reconocer scada's (Vijeo Citect) utilizando la Graphics Builder Automation Interface, y aquí ya vi un filón.

¿En qué consiste ésta última versión?. Pues bien, si disponemos de un diagrama real de Scada, por ejemplo como el siguiente:

Podemos ver una configuración típica donde se transporta el producto desde unos silos de origen a unos recipientes destino. Ahora lo que hay que hacer, es escanear la librería de "Genies" (Objetos del Vijeo Citect) con Thundax Genies Scanner y volcar los datos en la ubicación de los resources de Thundax Box Manager (para que disponga de todas las imagenes de la librería y así poder representar las boxes con la imagen correcta).

Una vez escaneada una librería como la presentada en la imagen, ya podemos iniciar Thundax Box Manager y escanear la pantalla del Scada con la aplicación utilizando la librería de automatización. Sobretodo antes, visualizar en las opciones de la aplicación Thundax Genies Scanner la ubicación de los resources:


Ahora, iniciamos Thundax Box Manager, y con la pantalla seleccionada del Scada, nos dirigimos al menú Citect -> Load Page Diagram, y en pocos segundos, tendremos cargada la misma estructura en mi aplicación (solo las genies, los símbolos no, porque no representan ninguna estructura de control, es decir, no tienen ninguna lógica dentro del proceso):

Ahora solo tenemos que perder 15 segundos en realizar las conexiones lógicas entre elementos o ítems y luego calcularemos las rutas:

Tenemos que acordarnos de marcar cuales son los orígenes y cuales los destinos:

Ahora entenderéis el concepto de "Bloqueo o Interlock" con la siguiente imagen:

Si os fijáis el producto pasa por la cinta superior, y hay 2 válvulas que sacan el producto. Pero tenemos que tener en cuenta que solo se puede abrir 1 a la vez, ya que sinó enviariamos producto a un destino diferente al requerido. Por lo tanto debe estar bloqueada la otra válvula y no abrirse durante la ejecución de la ruta seleccionada. De ahí que exista el objeto "interlock", y que se gestione en el cálculo de la ruta de transporte.

Ahora solo tenemos que ejecutar "Citect -> Calc Transport Routes" et voilà!, ya tenemos generadas las 100 rutas disponibles que hay en menos de 100 ms.


Además podemos ver la ruta seleccionada haciendo click en la ruta:

Aún quede mucho trabajo por delante, pero me lo tomo con mucha ilusión al ver que por fin el programa tiene una meta asequible: Crear rutas de transporte para que otro programa pueda trabajar con éstas y ejecutarlas. Lo interesante de todo ésto es que podemos ahorrar un montón de tiempo intentando averiguar la cantidad de rutas que tenemos y sobretodo intentar el poderlas implementar gráficamente manteniendo como expliqué hace 2 meses un mapa lógico sobre una estructura que carece de inteligencia.

Aquí os dejo las últimas versiones de mi aplicación:

• Thundax Box manager 2.5.0 build 9 (With data and Thundax Genies Scanner v1.0.0 build 31).

He cambiado la privacidad de la aplicación y de momento la he hecho "trial de 30 días" esperando crear un paquete más completo con sus diferentes opciones. Espero que la lectura haya sido entretenida!.

Cálculo de rutas de transporte parte III

Continuando con los artículos sobre el tema del cálculo de rutas, aquí os dejo la última versión estable y mejorada sobre un ejemplo un poco más complejo y más real para diferentes destinos y con bloqueos entre elementos. El término bloqueo significa que no puede existir una ruta sin antes bloquear una serie de elementos. Éstos se tienen que vigilar, entre sí, ya sea por un equipo inteligente u otro tipo de algoritmo o aplicación. En éste ejemplo veréis como puede llegar a complicarse un sistema de rutas:

Si nos fijamos bien, existen muchos destinos y además existen bloqueos entre caminos (representados por un nuevo concepto de símbolo):


¿Ésto que indica?. Nos indica que los 4 elementos están bloqueados entre sí, y para no dibujar (n-1) flechas entre los diferentes objetos, creamos uno diferente que creará automáticamente el enlace con las demás cajas. De ésta manera cuando se cree el camino que pase por el elemento 4, éste llamará a la caja superior y recogerá los 3 elementos que tiene para introducirlos en la descripción de la ruta.

De ésta manera obtenemos lo siguiente:


Aquí os dejo la última versión de la aplicación más los ejemplos hasta ahora hechos. Éste último ejemplo lo he hecho en menos de 3 minutos, y el cálculo total de rutas en un total de 16ms.

• ThundaxBoxManager v2.4.0 build 29.rar (With data).

PD: Ésta última versión está protegida con mxProtector y solo permitirá 10 ejecuciones. De momento tengo que poner ésto ya que no es una versión definitiva y no quiero que corra por la red sin antes tener montada una buena base. Además, ahora ya empieza a hacer cosas importantes.

Cálculo de rutas de transporte parte II

Continuando con mi anterior artículo, he mejorado el algoritmo de búsqueda de caminos, de tal manera que ahora permite la búsqueda de un sinfín de posibilidades con tiempos extremadamente pequeños. En la versión anterior me di cuenta de que había un problema con el diseño del algoritmo y era referente a que a la hora de buscar los nodos adyacentes, éstos tienen que estar ordenados por el número de conexiones entrantes que tienen. De ésta manera podemos calcular cosas tan complejas como éstas:

A simple vista parece ser bastante difícil el obtener el número de caminos disponibles pero al final acaba siendo un simple recorrido de nodos:

Como podéis ver en la última imagen, hay 31 rutas disponibles. Además, en ésta última versión, ya está resuelto el problema de multi-orígenes y multi-destinos de tal manera que el algoritmo ya es capaz de recorrerlos todos con un coste cuadrático. Hay que mejorar un poco el coste pero estamos hablando de hacer el cálculo de unas 30 rutas en unos 16 mili segundos.

Si nos fijamos en la siguiente imagen, podréis ver la resolución con múltiples orígenes y múltiples destinos:

Si os fijáis en la imagen también queda marcado el camino seleccionado en la grid, de ésta manera visualmente podemos reconocer la ruta seleccionada y comprobar que los cálculos estén correctamente realizados.

El cálculo ahora es bastante diferente de como se hacía en el artículo anterior. Se me ocurrió la idea de realizar la búsqueda a través de la tabla de adyacentes sin tener que hacer antes un barrido. De ésta manera realizando una serie de operaciones que ahora detallaré, tenemos resuelto el problema del cálculo de rutas de transporte.

Con el siguiente código realizamos el recorrido total de la lista de adyacentes:

fila := 1;
filas := 0;
columna := 1;
for i := 0 to length(AdjacentList) - 1 do
begin
   if AdjacentList[i].isSource then
   begin
       grid[columna, fila] := Inttostr(AdjacentList[i].source);
       grid[columna + 1, fila] := Inttostr(AdjacentList[i].destiny);
       AdjacentList[i].visited := true;
       filas := filas + 1;
       fila := fila + 1;
   end;
end;

bVisited := false;
while not bVisited do
begin
   sum := 0;
   for i := 1 to filas do
   begin
       columna := getLastColumn(i);
       SetLength(Connector, 0);
       GetList(Connector, AdjacentList, StrToInt(grid[columna - 1, i]));
       if Length(Connector) <> 0 then
           grid[columna, i] := IntToStr(Connector[0].destiny);
           if Length(Connector) > 1 then
           begin
               newRows := CloneRow(i, Connector);
               sum := sum + newRows;
           end;
   end;
   filas := filas + sum;
   bVisited := AllRowsFinished(filas, DestinoList);
end;

• ¿Como funciona?

Primero buscamos los orígenes de la lista de adyacentes y los situamos en la grid, por ejemplo:

1 2
1 3

Luego recorremos ésta lista buscando los adyacentes de los últimos nodos, 2 y 3. Por lo tanto encontraremos que el 2 estará conectado con el 4 y el 5 y el 3 solo con el 6. En el momento que tenemos que añadir el valor 4 detrás del 2, si vemos que hay más conexiones, realizamos un clonado de la línea que estamos tratando y insertamos el siguiente valor en la línea clonada:

1 2 4
1 3
1 2 5 (clonado)

Continuamos con la siguiente fila:

1 2 4
1 3 6
1 2 5

Ahora, tenemos que volver a empezar y volver a añadir las conexiones de los nodos posteriores e ir clonando las diferentes filas hasta llegar al final:

1 2 4 8
1 3 6 7 8
1 2 5 8
1 3 6 8

De ésta manera tan fácil conseguimos construir la lista de rutas de transporte, siempre teniendo en cuenta los diferentes orígenes y destinos que nos podemos encontrar.

Podéis descargar la última versión de la aplicación con los ejemplos aquí:

• ThundaxBoxManager v2.4.0 build 10.rar (With Data).

PD : Para la ejecución del algoritmo correcto, hay que ir al menú Citect -> Calc Routes 2 una vez el diagrama está abierto.

Cálculo de rutas de transporte parte I

Después de unos días muy ajetreados y con mucho trabajo (y que no falte) he podido medio acabar la primera aplicación profesional sobre mi framework. Ésta se trata sobre el cálculo de rutas. He utilizado diversos tipos de algoritmos para su recorrido y búsqueda de diferentes caminos para obtener la ruta de un origen a un destino pasando por una serie de nodos. Luego vincularé la búsqueda de éstas rutas con mi anterior aplicación Thundax Genies Scanner y así poder crear mapas mentales de aplicaciones Scada para la búsqueda de caminos automáticos. En que consiste ésta idea?

Como podéis ver en la siguiente imagen:

Disponemos de un origen marcado en verde y un destino marcado en fucsia. Con mi framework he generado el diagrama y aplicado diversas propiedades a las diferentes cajas y conectores. El problema que se presenta, es el de calcular las diferentes rutas que hay de un punto a otro y guardarlas en algún sitio para poder utilizar éstos datos y evitar sobretodo el cálculo manualmente. Poco a poco, os iré explicando la utilizad de ésto y el propósito de su cálculo.

Por lo tanto, si nos fijamos en la imagen existen 2 rutas para ir del origen (1) al destino (19):

Así, calcularíamos:

RUTA1: 1-4-8-11-19 RUTA2: 1-5-9-11-19

• ¿Dónde está la complicación aquí?

Parece fácil, no?. Pues no lo es. Es un problema bastante complicado a la que empiezan a haber cruzamientos entre nodos. Si aparecen diversas conexiones entre sí, el numero de combinaciones empieza a crecer exponencialmente.

Si observamos mi aplicación, veremos como se calculan las rutas automáticamente:

Ahora un ejemplo más real:

Como podéis comprobar, son los mismos nodos, pero ahora tenemos 7 rutas disponibles!.

El cálculo de sus rutas es el siguiente:

Aún estoy acabando de perfilar el algoritmo y calculando sus diferentes costes para una mejora en su rendimiento. Dentro de poco tendré disponible la versión para búsqueda de rutas con múltiples orígenes y múltiples destinos. Y poder realizar la búsqueda de rutas de diagramas como el siguiente:

Si os fijáis, incluso he creado un tipo de enlace nuevo con la imagen de una cadena. Éste enlace consiste en un enlace de bloqueo donde los nodos están fuertemente vinculados y también se tienen que tener en cuenta a la hora de escribir la ruta de transporte. Ésto significa que si queremos pasar por un nodo de éstos, el otro debe aparecer bloqueado (en términos de fluidos seria cerrar uno de los caminos).

• ¿Cómo funciona el algoritmo?

El algoritmo que he creado es del tipo backtracking recorriendo los diferentes nodos y marcando las rutas visitadas. Lo que hago es crear una lista de adyacentes marcando la cantidad de conexiones que tiene cada nodo.

Primero calculo los orígenes y destinos en función del color de la caja:

for i := 0 to boxlist.count - 1 do
begin
if boxlist.items[i].properties.fillColor = clLime then
    SetArrayValue(OrigenList, StrToInt(boxlist.items[i].properties.getText));
if boxlist.items[i].properties.fillColor = clFuchsia then
    SetArrayValue(DestinoList, StrToInt(boxlist.items[i].properties.getText));
end;

Luego, nos centramos en calcular la lista de adyacentes en función del tipo de conexión. Además existe una lista de bloqueos en función del tipo de conector utilizado:

for i := 0 to connectorList.count - 1 do
begin
  conn := connectorList.items[i];
  pos1 := StrToInt(conn.SourceBox.properties.getText);
  pos2 := StrToInt(conn.TargetBox.properties.getText);
  if not conn.Line.ClassNameIs('TAbstractDottedDoubleLinkedArrowLine') and
      not conn.Line.ClassNameIs('TAbstractSimpleDoubleLinkedArrowLine') then
      SetAdjacentValue(AdjacentList, pos1, pos2)
  else
  begin
      SetAdjacentValue(InterlockList, pos1, pos2);
      SetAdjacentValue(InterlockList, pos2, pos1);
  end;
end;

El siguiente paso es marcar los diferentes nodos con su peso marcado por la cantidad de nodos conectados a un nodo.

for i := 0 to length(AdjacentList)-1 do
begin
  AdjacentList[i].weight := getWeight(AdjacentList, AdjacentList[i].source);
  if AdjacentList[i].weight = 1 then
      AdjacentList[i].unique := true;
end;

Esto nos permite crear un diagrama con la siguiente información:

function TfrmMain.ExamineNodes(firstNode: integer; lastNode: integer; AdjacentList: TAdjacentArray): string;
var
nodeVisited: integer;
res: TArrayInteger;
i: integer;
father: integer;
begin
nodeVisited := firstNode;
father := nodeVisited;
while (nodeVisited <> lastNode) do
begin
    res := GetConnections(AdjacentList, nodeVisited);
    if length(res) = 0 then exit;
    for i := 0 to length(res) - 1 do
    begin
        nodeVisited := res[i];
        if isVisited(AdjacentList, father, nodeVisited) then
        begin
            visit(AdjacentList, father, nodeVisited);
            setRoute(nodeVisited, father);
            ExamineNodes(nodeVisited, lastNode, AdjacentList);
        end;
    end;
end;
end;

Cómo podéis ver el algoritmo es bastante simple pero se puede mejorar bastante. El coste de calculo es O(n2) para visitar todos los nodos. Aquí os dejo la última versión de la aplicación ThundaxBoxManager v2.3.0 build 57 con los diagramas de ejemplo. Para si resolución hay que ir al menú Citect y allí ejecutar la opción Backtracking2.

• ThundaxBoxManager v2.3.0 build 57.rar (with Data).

Instalando VLO Framework

Aun estoy ultimando detalles del framework y he integrado éste en el IDE de Delphi. La plataforma consiste en un conjunto de librerías las cuales el usuario final no necesita como funcionan internamente. Simplemente se instala la plataforma de desarrollo en el IDE y se empiezan a utilizar las clases necesarias para el dibujado de los objetos sobre un canvas. Ahora cuando iniciamos el Delphi, podemos ver:

Aun tengo que mejorar el Icono, pero de momento es provisional y meramente informativo para indicar que existe el framework dentro del IDE. El aspecto interno es el siguiente:

Luego una duda que nos puede aparecer es, ¿Cómo puedo hacer para que aparezca el logotipo del package en el Splash screen del Delphi?. Muy fácil, aquí os lo explico:

Una vez tenemos creado nuestro package, tenemos que crear un fichero de recursos que contendrá el logo que queremos que se visualize en el splash del delphi. En mi caso lo he llamado ThundaxVLO.res y he utilizado el XN Resource Editor para crearlo:


Utilizando ésta herramienta gratuita y open source, podemos crear nuestros ficheros de recursos e insertar las imágenes que queramos. Para la conversión de ficheros BMP a ICO he utilizado una aplicación freeware llamada ImageIcon 3.0. Una vez tenemos todos los ficheros necesarios, creamos una nueva unidad en nuestro package que incluirá el procedimiento de registro de los recursos y forzará el incrustado de la imagen en el splash inicial:

unit ThundaxFramework;

interface

{$I JEDI.INC}

procedure Register;

implementation

uses DesignIntf, DesignEditors, Graphics, ToolsAPI;

{$R ThundaxVLO.res}

procedure Register;
{$IFDEF DELPHI10_UP}
var
  lBitmap: TBitmap;
  Service: IOTAAboutBoxServices;
{$ENDIF}
begin
{$IFDEF DELPHI10_UP}
  ForceDemandLoadState(dlDisable);
  lBitmap := TBitmap.Create;
  try
      lBitmap.LoadFromResourceName(hInstance, 'LOGO');
      if Assigned(SplashScreenServices) then
          SplashScreenServices.AddPluginBitmap('VLO Framework v1.0 ', lBitmap.Handle);
      BorlandIDEServices.GetService(IOTAAboutBoxServices, Service);
      if Assigned(Service) then
          Service.AddPluginInfo('Thundax Software',
              'VLO Framework v1.0 ' + sLineBreak + 'Thundax Software', lBitmap.Handle);
  finally
      lBitmap.Free;
  end;
{$ENDIF}
end;

end.

El fichero {$I JEDI.INC} nos interesa para obtener la directiva DELPHI10_UP y saber si estamos ejecutando una versión superior o no, de esta manera se muestra o no el logo en el inicio.

De ésta manera podemos ver también el framework instalado en el About del Delphi:


Espero que os sirva de ayuda!.