Título: "Layout Automático de Grafos con Inteligencia Artificial para la Visualización de Modelos Conceptuales

Tesista: Giuliano Marinelli

Directores: Dra. Laura Cecchi - Dr. Germán Braun

Carrera: Licenciatura en Ciencias de la Computación

Día: 29 de abril de 2020

 

Resumen
Los algoritmos de layout automático son una herramienta de gran utilidad para el diseño de modelos conceptuales, diagramas o grafos, en cualquier lenguaje de modelado como UML, ER, ORM, entre otros. En este sentido, para lograr un algoritmo de layout es necesario estudiar varias características que conforman un layout correctamente visualizado. Hemos considerado de mayor importancia, entre estas características, que el grafo (diagrama) resultante posea una mínima cantidad de cruzamientos entre sus arcos. Este problema se conoce como Crossing Number, y es NP-Completo.
En este trabajo se introduce el diseño y la implementación de ArcGen, un nuevo algoritmo genético, que minimiza la cantidad de cruces de un grafo. ArcGen involucra un reprocesamiento del grafo original, transformando su representación gráfica a un Diagrama de Arcos. Se describen todos los detalles del diseño y de la implementación con la que se validó el algoritmo.
Finalmente, dada la motivación del desarrollo de ArcGen y la complejidad temporal del problema Crossing Number, se realizaron experimentos circunscritos a grafos de tamaño proporcional al de los diagramas que se generan en la práctica real de modelado conceptual.
Se presentan los resultados de estos experimentos, mostrando que el algoritmo reduce el número de cruces sobre el grafo original en hasta cuatro veces. Se muestra también la integración de tal algoritmo con otros de layout, como el algoritmo Dirigido por Fuerzas de Tunkelang que permite dar una visualización diferente sobre el grafo. Finalmente, se evalúan y comparan los resultados en conjunto e individualmente.

Foto del día de la defensa con sus tutores, el tribunal integrado por las docentes Dra. Gabriela Aranda y Mg. Gerardo Parra y Lic.Christian Giménez, y representantes de la Secretaría Academica FAI

Foto del dia de la defensa de tesis  

Ver otras tesis FaI ]

 

 

Logo Grupo Euclides 

Trámites online (COVID-19)

Últimas noticias


Logo Grupo Euclides

Logo Fidebian  Logo Tutorias FAI  Logo CEFAI

 

Logo TAP