PDF de programación - Grafos: herramienta informática para el aprendizaje y resolución de problemas reales de teoría de grafos

X Congreso de Ingeniería de Organización
Valencia, 7 y 8 de septiembre de 2006



Grafos: herramienta informática para el aprendizaje y resolución de

problemas reales de teoría de grafos.



Alejandro Rodríguez Villalobos1


1 Dpto. de Organización de Empresas. Escuela Politécnica Superior de Alcoy. Universidad Politécnica de
Valencia. Pza. Ferrándiz-Carbonell, 03801 Alcoy. [email protected]



Resumen



En este artículo se presenta el estado y resultados alcanzados hasta el momento de un proyecto de
investigación que tiene como principal objetivo el desarrollo de una herramienta informática que
facilite el aprendizaje y resolución de problemas reales de teoría de grafos. El proyecto comenzó
en el año 2003, y actualmente sigue en activo, en proceso de programación de nuevos algoritmos,
incorporación de nuevas funciones y generación de documentación actualizada. Este artículo
además de difundir el estado y resultados del proyecto, pretende también ser una invitación, para
que todo aquel que lo desee pueda sumarse a él y compartir el desarrollo, el conocimiento y otras
experiencias relacionadas.

Proyecto Grafos


Palabras clave: teoría de grafos, ingeniería de organización industrial, aprendizaje,
conocimiento compartido


1.

Grafos es una herramienta informática para la construcción, edición y análisis de grafos que
pretende ser de utilidad para la docencia, aprendizaje y práctica de la teoría de grafos (Graph
Theory), Dieter (2004), y otras disciplinas relacionadas como la investigación operativa,
diseño de redes, ingeniería de organización industrial, la logística y el transporte, etc. Un
grafo puede representar en forma de red un modelo de una realidad empresarial Este modelo
podrá ser analizado desde distintos puntos de vista gracias a los algoritmos y funciones
incorporados en la herramienta.
La herramienta informática, se puede usar sin restricciones para el modelado, diseño de
grafos, análisis y resolución de problemas reales, a partir de los algoritmos y funciones
descritas en este artículo. El desarrollo de Grafos se ha estructurado en base a dos grandes
objetivos:

 Desarrollo de un interfaz para la construcción y edición de grafos en modo tabular o

gráfico (Figura 1), que permita la incorporación modular de multitud de funciones.

 Desarrollo de una estructura de clases y librerías .dll con algoritmos de resolución y
análisis de problemas de teoría de grafos. Implementación y compilación de diferentes
algoritmos.

Independientemente de sus conocimientos actuales sobre la materia, la información recogida
en la página web del proyecto puede ser un buen punto de partida para el aprendizaje en
mayor profundidad de la teoría de grafos y su aplicación en la realidad empresarial e
industrial. Todo el material recopilado en el sitio web del proyecto (software, textos,
imágenes, casos, etc.), se distribuye bajo licencia Creative Commons License, por lo que se

puede decir que otro de los objetivos de este proyecto es la difusión libre de conocimiento
(http://personales.upv.es/arodrigu/grafos).


Figura 1. Pantallas de Grafos. Ejemplos de edición gráfica y tabular.



Aprendizaje



2.

La filosofía de esta herramienta es la siguiente: "dibujar, modelar, resolver y analizar". Con
esto se pretende que el usuario tenga libertad absoluta para tratar y abordar los problemas de
grafos. El usuario puede dibujar libremente el grafo sin preocuparse del análisis o algoritmo
que utilizará posteriormente. El programa le avisará en caso de no factibilidad o de cualquier
otro requerimiento para un análisis en particular. Los estudiantes que usen Grafos
experimentarán un proceso de aprendizaje basado en su libertad y en etapas de prueba-error
(aprendizaje a través del juego), Gallardo (2000). Otros programas existentes, a diferencia de
este, guían al usuario paso a paso según el tipo de grafo y problema a resolver, descartando de
entrada su libertad de elección y construcción. Esta libertad de cara al usuario ha implicado
una mayor complejidad en el desarrollo del código fuente, ya que no sólo hay que contemplar
los supuestos aplicables al tipo de análisis o problema a resolver, sino cualquier escenario que
pueda generar la interacción con el usuario (incluyendo los de no factibilidad).


3.

Grafos está desarrollado en Microsoft Visual Studio 2005 (el código fuente actualmente está
íntegramente programado en Visual Basic .net 2005, aunque podría integrar fácilmente
módulos desarrollados en otros lenguajes de programación .net). Esta plataforma de
desarrollo garantiza su funcionamiento en Microsoft Windows y facilita su adaptación a
futuras versiones de este sistema operativo (incluyendo Windows Vista, Windows 64-bit,
Windows Mobile).

Desarrollo y estructura

Su estructura es modular, flexible y escalable (Figura 2). La programación orientada a
objetos, y su estructura basada en clases y librerías (.dll), permite fácilmente incorporar
nuevas funciones y análisis, o mejorar los existentes. Las principales funciones del programa
(edición gráfica, edición tabular, dibujar grafo, gestión de la interfaz, etc.) están encapsuladas
dentro de él; mientras que los modelos de datos (importación/exportación de datos, meta-
datos) y las librerías de análisis de grafos son externas a la estructura. Esto permite poder
utilizar estas librerías por otros programas o en otros proyectos.


lp_solve.dll

MILP (.lp, .mps)

Ficheros de datos
.grf
.graphml

dibuja grafo
dibuja grafo

Análisis
Análisis
Análisis

Resultados
Resultados
Resultados

.txt
.dat
.vrp-xml

.gif
.png
.bmp
.tif
.svg
…

interfaz
interfaz
interfaz

edición gráfica
edición gráfica
edición gráfica

edición tabla
edición tabla
edición tabla

funciones
funciones

Figura 2. Esquema estructural y funcional.

Dijkstra.dll
Dijkstra.dll

Kruskal.dll
Kruskal.dll

Prim.dll
Prim.dll

FloydWarshall.dll
FloydWarshall.dll

FordFulkerson.dll
FordFulkerson.dll

BellmanFord.dll
BellmanFord.dll

…
…



Intercambio de datos



4.

En la figura anterior se puede observar un esquema de los flujos de datos de Grafos. Los datos
de un grafo se guardarán en dos posibles tipos de archivo: un fichero de texto de tipo
secuencial (.grf) y un fichero de tipo estructurado GRAPHML File Format (.graphml). Este
último tipo de fichero es un estándar que fue iniciado en el comité “Graph Drawing Steering
Committee” previo al “Graph Drawing 2000” de Williamsburg. Se acordó formar un grupo
que definiera un nuevo formato de datos para grafos basado en XML (Figura 3), de modo que
fuera estándar para la comunidad de dibujo de grafos y sus cooperadores. La propuesta de
estructura fue presentada en el siguiente simposio “Graph Drawing Symposium” de Viena
(ver http://graphml.graphdrawing.org/). El principal predecesor de GraphML es GML, que
fue el resultado de una iniciativa que comenzó en el “Graph Drawing 1995” en Passau y
finalizó en el “Graph Drawing 1996” de Berkeley. GML es todavía uno de los principales
formato de grafos soportado por muchos sistemas de dibujo, aunque no en este proyecto.


<?xml version="1.0"?>
<xs:schema targetNamespace="http://graphml.graphdrawing.org/xmlns"

xmlns="http://graphml.graphdrawing.org/xmlns/1.0rc"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
elementFormDefault="qualified"
attributeFormDefault="unqualified"

...

Figura 3. Cabecera del fichero XML utilizado en GRAPHML.


Además de estos dos formatos anteriores, el programa es capaz de intercambiar datos con
otras aplicaciones (hojas de cálculo, bases de datos, etc.) gracias a su función avanzada de

importación y exportación de datos. El usuario puede configurar fácilmente el formato y
estructura de datos que quiere intercambiar (fichero separado por comas, tabulaciones, etc.),
así como los datos a tratar (coordenadas de nodos, valor de coste del arco, demanda de los
nodos, matriz binaria, etiquetas, etc.). De este modo se incrementan las posibilidades de
análisis y sus aplicaciones reales.
Por otro lado, la aplicación permite generar diferentes ficheros de imagen con el grafo
resultante: de mapa de bits (.gif, .png, .bmp, .tif), y también de tipo vectorial (.svg). Scalable
Vector Graphics es un lenguaje de texto que describe imágenes vectoriales, formas, textos y
otros gráficos incrustados. Los ficheros SVG son compactos y proporcionan una gran calidad
gráfica en la web, en la impresión y en dispositivos de recursos limitados. Además, SVG
soporta códigos y animación, lo que lo hace ideal para la interacción, el manejo de datos, y la
personalización de los gráficos. SVG está libre de royalties y es un estándar abierto e
independiente desarrollado bajo la supervisión de W3C (World Wide Web Consortium).
También es importante citar la utilización de ficheros de datos auxiliares que son útiles para la
resolución de problemas de rutas. Actualmente se utilizan dos formatos de fichero para la
definición de modelos de programación lineal entera mixta (MILP), se trata de estándares (.lp,
.mps) que sirven de pasarela entre la aplicación y el solucionador de problemas de
optimización (Solver lp_solve).
Por último, cabe destacar los ficheros utilizados para manejar los datos que definen problemas
de rutas de vehículos VRP (Vehicle Routing Problems), Dantzig (1959). En este proyecto se
ha propuesto un nuevo formato de fichero (.vrp-xml); diseñado a partir de una estructura de
etiquetas VRP-XML que resuelve los probl