Visualizador de Estructuras de Datos

1

Visualizador de Estructuras de Datos

Proyecto de Grado

Presentado al

Departamento de Ingeniería de Sistemas y Computación

por

Diana Marcela Gutiérrez Córdoba

Profesor asesor: Mario Fernando De la Rosa Rosero, Ph.D.

Ingeniería de Sistemas y Computación

Universidad de los Andes

Bogotá,Colombia

Junio 2020

2

Contenido

Lista de figuras ....................................................................................................................... 3

Capítulo I: Introducción ......................................................................................................... 6

Capítulo II: Descripción general ............................................................................................ 8

2.1. Objetivo general ....................................................................................................... 8

2.2. Objetivos específicos ............................................................................................... 8

2.3. Antecedentes ............................................................................................................ 8

2.4. Identificación del problema ................................................................................... 13

Capítulo III: Diseño y especificaciones ............................................................................... 14

3.1. Especificaciones ..................................................................................................... 15

3.2. Restricciones .......................................................................................................... 20

Capítulo IV: Desarrollo del diseño ....................................................................................... 21

4.1. Alternativas de diseño ............................................................................................ 23

Capítulo V: Implementación ................................................................................................ 24

5.1. Interfaz visual......................................................................................................... 24

5.2. Integración con la herramienta............................................................................... 27

Capítulo VI: Resultados........................................................................................................ 28

6.1. Manejo de errores .................................................................................................. 28

6.2. Pruebas ................................................................................................................... 34

Capítulo VII: Conclusiones ................................................................................................. 57

7.1. Trabajo futuro ........................................................................................................ 57

Referencias ........................................................................................................................... 59

3

Lista de figuras

Ilustración 1. visualización de una lista .................................................................................. 9

Ilustración 2. pseudocódigo en ejecución ............................................................................... 9

Ilustración 3. visualización resultante .................................................................................. 10

Ilustración 4. visualización del grafo inicial ......................................................................... 10

Ilustración 5. visualización del algoritmo paso a paso ......................................................... 11

Ilustración 6. vista de los resultados ..................................................................................... 11

Ilustración 7. workspace y generación de la estructura ........................................................ 12

Ilustración 8. ejecución del código y visualización de la estructura .................................... 13

Ilustración 9. Diagrama de componentes ............................................................................. 14

Ilustración 10. Estructura del proyecto estudiante................................................................ 17

Ilustración 11. estructura de la entrada de datos ................................................................... 22

Ilustración 12. Estructura de la interfaz del visualizador ..................................................... 24

Ilustración 13. Panel de opciones según el tipo de estructura .............................................. 26

Ilustración 14. Aviso de advertencia para entrada errónea ................................................... 34

Ilustración 15. Aviso de advertencia para entradas vacías ................................................... 35

Ilustración 16. Aviso de advertencia para nodo inexistente ................................................. 35

Ilustración 17. Aviso de advertencia para arco inexistente .................................................. 35

Ilustración 18. Aviso de error al crear la estructura ............................................................. 36

Ilustración 19. Visualización de un grafo dirigido ............................................................... 37

Ilustración 20. Visualización de un grafo no dirigido .......................................................... 38

Ilustración 21. Visualización de una lista encadenada ......................................................... 38

Ilustración 22. Visualización de un árbol binario ordenado ................................................. 39

Ilustración 23. Estado del visualizador tras buscar nodos existentes e inexistentes ............. 40

Ilustración 24. Búsqueda de nodos realizada correctamente ................................................ 41

Ilustración 25. Estado del visualizador tras una búsqueda inconsistente ............................. 42

Ilustración 26. Estado del visualizador tras una búsqueda de adyacentes implementada

incorrectamente .................................................................................................................... 43

Ilustración 27. Búsqueda de adyacentes realizada correctamente ........................................ 44

Ilustración 28. Estado del visualizador al agregar incorrectamente un nodo ....................... 45

Ilustración 29. Estado del visualizador tras adición correcta de un nodo ............................. 46

Ilustración 30. Inserción de nodo fallida .............................................................................. 46

Ilustración 31. Estado del visualizador tras eliminación incorrecta de un nodo .................. 47

Ilustración 32. Estado del visualizador tras eliminación correcta de un nodo ..................... 48

Ilustración 33. Estado del visualizador tras la búsqueda de arcos existentes e inexistentes 49

Ilustración 34. Estado del visualizador tras una búsqueda implementada incorrectamente . 50

Ilustración 35. Estado del visualizador tras la correcta búsqueda de un arco o conexión .... 51

Ilustración 36. Aviso de advertencia al agregar un arco existente ....................................... 51

Ilustración 37. Aviso de error al presentarse inconsistencias ............................................... 52

Ilustración 38. Estado del visualizador tras la adición correcta de arcos ............................. 52

4

Ilustración 39. Aviso de advertencia para un conjunto de arcos vacío ................................. 53

Ilustración 40. Estado de la visualización tras mostrar el conjunto de arcos ....................... 53

Ilustración 41. Estado del visualizador tras mostrar un conjunto de nodos con búsqueda

incorrecta .............................................................................................................................. 54

Ilustración 42. Estado de la visualización tras mostrar el conjunto de nodos ...................... 54

Ilustración 43. Estado de la visualización tras mostrar un camino no secuencial ................ 55

Ilustración 44. Estado del visualizador tras mostrar un camino ........................................... 56

Ilustración 45. Aviso de error el reiniciar con problemas .................................................... 56

5

Resumen

El presente proyecto abarca la temática de estructuras de datos, enfocándose principalmente

en tres de ellas: grafo (dirigido y no dirigido), lista encadenada y árbol ordenado binario. Esto

con el propósito de ofrecer un visualizador para apoyar la comprensión del tema de

estructuras de datos por parte de estudiantes, mediante una herramienta computacional que

presenta un modelo visual de las estructuras de datos y retroalimentación en cuanto a las

operaciones que se realicen sobre estas. Así las cosas, se requiere de una implementación

realizada por un estudiante, o el interesado en el visualizador, con la cual podrá iniciar la

herramienta dando lugar a su representación visual y a la habilitación de las operaciones

pertinentes. Adicionalmente, dependiendo del tipo de estructura se presentarán unas

funcionalidades específicas debido a que la utilidad no es la misma para todas, y en caso de

que se requiera probar una funcionalidad no definida en el panel de operaciones, existe la

posibilidad de probar algoritmos de la autoría del estudiante al mostrar nodos, arcos o

caminos. Finalmente, este proyecto está desarrollado en lenguaje Java y se encuentra

orientado a implementaciones de las estructuras de datos en ese mismo lenguaje. Además, se

apoya en una librería externa llamada JGraphT con el complemento JGraphXAdapter para

soportar un modelo visual adecuado y los cambios generados por interacciones mediante las

operaciones realizadas.

6

Capítulo I

Introducción

Como estudiante de Ingeniería de Sistemas y Computación de la Universidad de los Andes,

cursé la asignatura de Estructuras de Datos y como la mayoría de mis compañeros, era un

tema con el cual entrábamos en contacto por primera vez. Tras varios intentos y la realización

de los proyectos, eventualmente logré comprender el funcionamiento de las estructuras

vistas, aunque esto me representó una gran dificultad debido a lo abstracto de la temática y

la escasez de algún instrumento externo a las explicaciones de la clase que pudiese ayudar a

mi comprensión. De este modo, me gustaría poder apoyar a los estudiantes que atraviesen

por mí misma situación y de algún modo les pueda facilitar el entendimiento con respecto a

alguna(s) estructura(s) de datos, además de proveerles una herramienta que les permita poner

a prueba sus conocimientos e hipótesis en cuanto a algoritmos de su autoría.

Pues bien, este proyecto se centra en la visualización de una estructura de datos provista por

el estudiante, donde es posible interactuar con la misma mediante operaciones definidas por

la herramienta e implementadas por él mismo. De este modo, se espera que el estudiante

pueda observar y verificar el funcionamiento de su código, además de aclarar su comprensión

acerca de las estructuras de datos.

Consecuentemente, se elaboró una herramienta computacional interactiva capaz de integrar

una visualización y una implementación de una estructura de datos en lenguaje Java, bien sea

grafo, lista encadenada o árbol binario ordenado; con la intención que los estudiantes puedan

validar por si mismos los métodos de su implementación de la estructura de datos. Los

resultados del funcionamiento de la estructura de datos se mostrarán en un modelo visual con

la idea que el estudiante los observe. En caso de que la herramienta detecte un resultado no

esperado (error) en algún método, esta le informa al estudiante para que pueda observar el

resultado obtenido, lo cual se realiza con la intención de que entienda mejor estos posibles

problemas y pueda corregir su implementación.

Finalmente, se obtuvo como resultado una herramienta que despliega correctamente la

visualización de una estructura, además de permitir la interacción con operaciones básicas y

algoritmos que han sido desarrollados e implementados por el estudiante. Conjuntamente, se

ofrece un medio para retroalimentar los resultados obtenidos con respecto a los esperados tal

que se posibilita la mejora en la implementación de las funcionalidades.

El presente documento se encuentra estructurado por capítulos como sigue: el capítulo II trata

acerca de los objetivos del proyecto además de antecedentes relacionados a la temática junto

con el problema a resolver, el capítulo III presenta el diseño y componentes de la herramienta

designando las especificaciones correspondientes, así como los requerimientos funcionales

y restricciones del desarrollo. Posteriormente, en el capítulo IV se discute acerca de las etapas

llevadas a cabo para desarrollar el diseño, adicionando las alternativas consideradas

7

previamente a la implementación; seguidamente, en el capítulo V se explican los

componentes del visualizador y las diferencias pertinentes según el tipo de estructura, para

continuar con el proceso realizado para lograr la integración con un proyecto externo.

Entonces, el capítulo VI discute los resultados obtenidos, donde inicialmente se menciona el

manejo de errores ante las posibles interacciones del usuario, asimismo, se procede a

presentar las pruebas realizadas con sus respectivas respuestas en el visualizador con los

casos que podrían ser más frecuentes en el uso de este. Finalmente, el capítulo VII expone

las conclusiones obtenidas a partir de la finalización del proyecto y la discusión de un posible

trabajo futuro.

8

Capítulo II

Descripción general

2.1. Objetivo general

Este proyecto de grado se encuentra orientado inicialmente a estudiantes interesados en el

tema de Estructuras de Datos, en lenguaje Java. De esta manera, tiene como objetivo

desarrollar una herramienta visual que permita a dichos estudiantes integrar su

implementación en lenguaje Java de las operaciones básicas de una estructura de datos y

realizar una validación visual de su funcionamiento y desempeño.

2.2. Objetivos específicos

Así las cosas, se identifican los siguientes objetivos puntuales:

• Implementar el componente visual (gráfico) que despliegue un modelo visual de una

estructura de datos específica.

• Explorar la herramienta (motor gráfico) a utilizar para lograr los cambios visuales

necesarios en la estructura de datos a validar.

• Implementar la visualización de las operaciones básicas definidas en la estructura de

datos.

• Integrar una solución o implementación de una estructura de datos en lenguaje Java

con la solución del proyecto de visualización.

• Integrar la solución propuesta de visualización con la implementación de la estructura

de datos en lenguaje Java del estudiante como instancias separadas, de modo que

pueda ver su estructura y algoritmos reflejados en el visualizador sin la necesidad de

ejecutar ambas soluciones por separado.

• Implementar el funcionamiento de tres estructuras de datos básicas.

• Realizar pruebas del funcionamiento del proyecto con las estructuras de datos

definidas.

2.3. Antecedentes

Visualgo [1]

9

Desarrollado por el Dr Steven Halim en la Universidad Nacional de Singapur como una

herramienta para ayudar a sus estudiantes a entender las estructuras de datos y algoritmos.

Así pues, ésta permite observar una estructura con una pequeña y limitada cantidad de

datos, además de realizar operaciones específicas únicamente en selectas visualizaciones

acompañadas de un pseudocódigo que indica los pasos ejecutados. Algunas de las

estructuras soportadas incluyen listas enlazadas, colas, pilas, tablas de hash, árboles

binarios y grafos.

A continuación, a modo de ejemplo se muestra una lista enlazada como el ejemplo estándar

provisto por la herramienta.

Ilustración 1. visualización de una lista

Posteriormente se selecciona la opción de “búsqueda”, en la cual se elige el nodo 6 como

objetivo, dando lugar a la visualización paso a paso del algoritmo junto con el pseudocódigo

que explica los pasos en ejecución; adicionalmente, la velocidad de visualización es ajustable

permitiendo que el usuario lo adapte a su conveniencia.

Ilustración 2. pseudocódigo en ejecución

Finalmente, se muestra el resultado de la búsqueda y el estado en el que finalizó la lista.

10

Ilustración 3. visualización resultante

Data Structure Visualizations [2]

Desarrollado por David Galles en la Universidad de San Francisco. La herramienta muestra

la visualización de varias estructuras, para las cuales algunas de ellas tienen la opción de

ejecutar operaciones básicas de inserción o eliminación, y otras como en el caso de los grafos

permiten ver la ejecución únicamente de algoritmos. Además, indica con una explicación

visual y sencilla lo que realiza la función especificada en un paso a paso.

Actualmente, la herramienta soporta la visualización de múltiples estructuras y algoritmos

tales como pilas, colas, listas encadenadas, árboles binarios, árboles rojo negro, tablas de

hash abiertas y cerradas, árboles B, árboles B+, heaps, recursiones, búsquedas binarias,

ordenamientos, entre otros.

A continuación, a modo de ejemplo se muestra un grafo que se puede construir de manera

personalizada como dirigido, no dirigido, pequeño (8 nodos), grande (18 nodos). De igual

manera, es posible determinar de qué manera se desea visualizar la estructura como una lista

de adyacencia, matriz de adyacencia o representación lógica la cual fue seleccionada para

este ejemplo.

Ilustración 4. visualización del grafo inicial

11

En este caso, se selecciona el algoritmo del camino más corto de Dijkstra, utilizando como

nodo de partida el nodo “1”, iniciando la ejecución del algoritmo, el cual muestra un

pseudocódigo según el paso en el que esté y señalando en rojo el nodo en el que se encuentra.

Complementariamente, se cuenta con controles para volver o adelantar un paso, pausar y

modificar la velocidad de ejecución.

Ilustración 5. visualización del algoritmo paso a paso

Finalmente, se muestran los resultados del algoritmo.

Ilustración 6. vista de los resultados

12

DStBlocks [3]

Es una herramienta diseñada e implementada por estudiantes de la Universidad del Bosque

(Bogotá, Colombia), mediante la cual se pretende apoyar a los estudiantes en su aprendizaje

de una forma interactiva acerca de estructuras de datos lineales y sus algoritmos.

De este modo, la interacción se da a través de bloques que expresan una fracción de código,

los cuales a la vez son modificables según los parámetros que contengan y que el usuario

debe especificar. Pues bien, dichos bloques pueden integrarse entre sí a modo de completar

un algoritmo con una estructura parcialmente predefinida, posibilitando en una disminución

de errores de sintaxis en el código para el lenguaje en particular.

Adicionalmente, una vez el usuario haya completado su algoritmo, se ofrece una

visualización de la estructura creada o modificada de modo que se pueda verificar de una

manera más sencilla si la implementación fue correcta y se cumplió lo esperado en el

algoritmo.

Ilustración 7. workspace y generación de la estructura

DS PITON [4]

Es una herramienta desarrollada por la Universidad Cristiana de Marahanta en Indonesia,

creada para apoyar a los estudiantes a obtener un mejor rendimiento y completar con mayor

eficacia sus asignaciones. Pues bien, su principal función es mostrar cómo se interpretan de

manera visual las diferentes estructuras de datos en su implementación de forma sencilla e

intuitiva para el lenguaje Phyton.

Adicionalmente, la herramienta permite ver el código de la implementación de la estructura

siguiendo un paso a paso de la ejecución conforme esta se va dando, con una velocidad que

puede ser modificada por el usuario e incluyendo las opciones para pausar o adelantar

instrucciones. En este orden de ideas, DS PITON ofrece soporte para 7 estructuras de datos:

13

arreglos, listas encadenadas, pila con arreglo, pila con lista encadenada, cola con arreglo, cola

con lista encadenada y cola de prioridad con lista encadenada; estas se representan con una

estructura predefinida, de modo que se puede proceder inmediatamente a la visualización de

esta.

Ilustración 8. ejecución del código y visualización de la estructura

2.4. Identificación del problema

Los estudiantes que se enfrentan por primera vez a las Estructuras de Datos usualmente

presentan dificultades al momento de comprenderlas e implementarlas, pues bien, esto se

debe a que la abstracción de la temática se da al momento de "imaginar" cómo funcionan ya

que es un proceso que no se puede simplemente observar. De este modo, la comprensión de

una Estructura de Datos se facilita si se puede visualizar el funcionamiento de cada una de

sus operaciones.

Adicionalmente, para que un estudiante pueda probar si su planteamiento de un algoritmo es

correcto, es necesario que desarrolle una implementación de la estructura desde cero lo cual

le toma mucho tiempo para simplemente poder verificar su solución. Por lo tanto, al integrar

un algoritmo propio con una visualización de sus resultados, el estudiante puede validarlo y

de esta forma mejorarlo hasta lograr su funcionamiento correcto.

14

Capítulo III

Diseño y especificaciones

El diseño del proyecto consta de dos componentes principales (Ilustración 9): el componente

que usa la estructura de datos en lenguaje Java (archivo estructura.jar) provista por el

estudiante, y el componente visualizador. En el primer componente, se encuentran tres

subcomponentes que interactúan del siguiente modo: StandardMethods utiliza la interface

IStandardMethods la cual define los métodos de la estructura de datos que se van a visualizar

y la implementación propia de la estructura de datos. Por otra parte, el componente

visualizador posee dos subcomponentes que interactúan así: StructureAdapter utiliza el

componente integración con la estructura de datos y una serie de scripts que generan y

despliegan el visualizador.

Así las cosas, estos dos componentes principales se relacionan mediante la exposición del

componente StandardMethods, el cual es consumido por el de integración y StructureAdapter

para poder responder a las solicitudes generadas cuando el usuario interactúa con la

herramienta. Entonces, StructureAdapter consume el API expuesto por JGraphT para poder

crear las estructuras visualmente, siendo estas presentadas en un componente de Interfaz

Gráfica dentro del propio visualizador.

Ilustración 9. Diagrama de componentes

15

3.1. Especificaciones

Inicialmente, se identificaron varios aspectos importantes para el correcto funcionamiento

del proyecto, los cuales deben ser tomados en cuenta por el estudiante. Antes de continuar,

cabe aclarar que se entiende como conexión aquellas relaciones para las estructuras tipo árbol

y lista encadenada, mientras que en el caso de los grafos estas se toman como arcos. Así pues,

los aspectos previamente mencionados se encuentran descritos a continuación:

• Clase StandardMethods

Esta clase debe extender la interface IStandardMethods, la cual se provee al

estudiante, además de implementar los métodos ahí señalados teniendo en cuenta las

siguientes especificaciones:

o Tener como atributo una instancia estática de la estructura implementada, de

modo que esta sea el punto de acceso para los métodos solicitados.

o Implementar los métodos de la interface con los siguientes aspectos a tener en

cuenta:

Método Descripción

void createStructure() Es un método de tipo void, que debe inicializar el atributo

estático de la estructura y poblarla con los datos que el

estudiante considere pertinentes para visualizar su estado

inicial y poder modificarla y consultarla.

ArrayList<K>

getNodeList()

Es un método de tipo ArrayList genérico, que debe retornar

una lista con los nodos en la estructura de datos.

ArrayList<Edge<K>>

getEdgesList()

Es un método de tipo ArrayList que contiene objetos Edge

(clase provista al estudiante) genéricos, que debe retornar

una lista con los arcos o conexiones que contenga la

estructura de datos. Cada Edge indica un arco/conexión

entre un objeto inicial y un objeto final en la estructura de

datos. Conjuntamente, cabe aclarar que en caso de tratarse

de una lista encadenada, se espera que el método retorne

null dado que se asume que al ser una estructura lineal, las

conexiones van en el orden en que se expresen los nodos

en el anterior método, tal que el visualizador se encarga de

crearlos según dicha lista.

Object findNode(String

findTag)

Es un método de tipo Object con un String como parámetro,

el cual representa la etiqueta del nodo a encontrar; se

requiere que este método retorne el nodo de la estructura de

datos que satisfaga la búsqueda realizada.

16

Edge<K> findEdge(String

startNode, String endNode)

Es un método de tipo Edge con parámetros tipo String que

representan el nodo inicial y final en el arco o conexión;

este debe retornar dicho arco o conexión como un objeto de

tipo Edge.

ArrayList<Edge<K>>

getNeighbors(String

idVertex)

Es un método de tipo ArrayList que contiene objetos Edge

genéricos, con un String como parámetro que representa el

nodo de interés. Se espera que se retorne una lista con los

arcos o conexiones adyacentes al nodo de interés mediante

objectos de clase Edge.

ArrayList<Edge<K>>

showEdgesSet()

Es un método de tipo ArrayList que contiene objectos Edge

genéricos, que se espera que retorne una lista conteniendo

los arcos o conexiones de la estructura de datos que se

quieran mostrar. Este método busca mostrar/destacar

arcos/conexiones resultantes de algún algoritmo.

ArrayList<K>

showNodeSet()

Es un método tipo ArrayList genérico, que debe retornar

una lista con los nodos de la estructura de datos. Este

método busca mostrar/destacar nodos resultantes de algún

algoritmo.

Boolean isLineal() Es un método tipo Boolean, que se espera que retorne true

para listas encadenadas y árboles binarios, y false para

estructuras tipo grafo.

Boolean addNode(String

tag)

Es un método tipo Boolean con un parámetro tipo String,

que representa la etiqueta del nuevo nodo. El método

agrega un nodo a la estructura de datos con su etiqueta

única. El método debe retornar si fue agregado o no a la

estructura de datos.

Boolean deleteNode(String

tag)

Es un método tipo Boolean, con un parámetro tipo String,

que representa la etiqueta del nodo a eliminar. El método

elimina un nodo de la estructura de datos que tenga la

etiqueta dada. El método debe retornar si dicho nodo fue

eliminado o no de la estructura de datos.

ArrayList<K> getPath() Es un método de tipo ArrayList genérico, que debe retornar

una secuencia de nodos consecutivos (camino) en la


int structureType() Es un método de tipo int, que debe retornar 0 para árbol

binario, 1 para lista encadenada, 2 para grafo dirigido y 3

para grafo no dirigido.

boolean addEdge(String

startNode, String endNode)

Es un método tipo Boolean que tiene como parámetros el

String que representa la etiqueta del nodo inicial, y otro

String con la etiqueta del nodo final del arco a agregar. Sólo

aplica a estructuras tipo Grafo. El método debe retornar si

el arco se agregó o no a la estructura de datos.

• Archivo jar de la implementación de la estructura de datos.

17

Se requiere que el estudiante cree un archivo .jar que contenga la implementación de

la estructura de datos y las clases StandardMethods y Edge. Además, este debe

llamarse “estructura.jar”.

• Estructura del proyecto del estudiante.

Es necesario que el estudiante estructure su proyecto Java para cada estructura de

datos partiendo desde un paquete principal denominado “modelo”, el cual posee 2

subpaquetes:

o complementos: comprende la clase Edge y la interface IStandardMethods (dadas previamente al estudiante), además de la implementación de dicha

interface como se explicó anteriormente en la clase StandardMethods.

o estructuras: abarca todas las clases que el estudiante precise para implementar

su estructura de datos.

A continuación se muestra la jerarquía esperada en la estructura del proyecto:

Ilustración 10. Estructura del proyecto estudiante

En adición, el desarrollo del visualizador posee varios requerimientos para lograr satisfacer

las funcionalidades deseadas, los cuales se han distinguido entre funcionales y no funcionales

del siguiente modo:

Requerimientos funcionales

Requerimiento Crear visualización

Estructuras Árbol binario, lista encadenada, grafo

Método de apoyo void createStructure()

Entradas -

Salidas Se inicia la visualización de la estructura según los datos con los

que se inicializa la estructura de datos, además de la configuración

señalada por el mismo

En el panel de información se muestran el tipo de estructura junto

con el número de nodos y arcos o conexiones presentes

Requerimiento Buscar nodo(s)


Método de apoyo Object findNode(String findTag)

18

Entradas Etiqueta (String) que corresponde al nodo a buscar, en caso de ser

varias se separan por una coma y sin espacio: ej.

nodo1,nodo2,nodo3

Salidas En la visualización se resaltan en amarillo el(los) nodo(s)

encontrado(s).

En el panel de información se muestra el(los) nodo(s) retornado(s)

por la estructura de datos.

Requerimiento Buscar adyacentes de un nodo


Método de apoyo ArrayList<Edge<K>> getNeighbors(String idVertex)

Entradas Etiqueta String) que corresponde al nodo de interés

Salidas En la visualización se resalta en rojo el nodo buscado, y en amarillo

los adyacentes junto con los arcos/conexiones correspondientes

En el panel de información se muestran los arcos o conexiones

retornados por la estructura

Requerimiento Agregar nodo


Método de apoyo Boolean addNode(String tag)

Entradas Etiqueta (String) asociada al nuevo nodo

Salidas En la visualización se resalta el nuevo nodo en amarillo

En el panel de información se indica el nodo agregado

Requerimiento Eliminar nodo


Método de apoyo Boolean deleteNode(String tag)

Entradas Etiqueta (String) asociada al nodo a eliminar

Salidas Un aviso indica el estado de la eliminación

En el panel de información se indica el nodo eliminado

Requerimiento Buscar arcos o conexiones


Método de apoyo Edge<K> findEdge(String startNode, String endNode)

Entradas Arco o conexión por buscar (String) con la siguiente notación:

nodo inicial>nodo final. Ej: nodo1>nodo2

En caso de que se requiera buscar múltiples arcos o conexiones, se

sigue la anterior notación separándolos por comas: ej.

nodo1>nodo2,nodo3>nodo4

Salidas En la visualización se señalan en amarillo los arcos o conexiones

solicitados además de los nodos involucrados

En el panel de información se indica la búsqueda realizada

19

Requerimiento Agregar arcos

Estructuras Grafo

Método de apoyo boolean addEdge(String startNode, String endNode)

Entradas Arco por agregar (String) con la siguiente notación: nodo

inicial>nodo final. Ej: nodo1>nodo2

En caso de que se requiera agregar múltiples arcos, se sigue la

anterior notación separando los arcos por comas: ej.

nodo1>nodo2,nodo3>nodo4

Salidas En la visualización se señalan en amarillo los arcos agregados a la

estructura además de los nodos involucrados

En el panel de información se indica la operación ingresada

Requerimiento Mostrar arcos

Estructuras Grafo

Método de apoyo ArrayList<Edge<K>> showEdgesSet()

Entradas -

Salidas En la visualización se señalan en amarillo los arcos retornados por

la estructura

En el panel de información se indican los arcos retornados por la

estructura

Requerimiento Mostrar nodos


Método de apoyo ArrayList<K> showNodeSet()

Entradas -

Salidas En la visualización se señalan en amarillo los nodos retornados por

la estructura

En el panel de información se indican los nodos retornados por la

estructura

Requerimiento Mostrar camino


Método de apoyo ArrayList<K> getPath()

Entradas -

Salidas En la visualización se señala en amarillo la secuencia de nodos y

arcos/conexiones, en azul el nodo inicial y el final del camino, en

rojo los nodos que interrumpan la secuencia.

En el panel de información se indican el camino retornado por la

estructura.

Requerimiento Reiniciar estructura


Método de apoyo void createStructure()

20

Entradas -

Salidas La visualización se muestra tal como se tenía antes de realizar

alguna operación sobre la estructura.

En el panel de información se indica que la estructura se ha

reinicializado.

Requerimientos no funcionales

• Retroalimentación con avisos en caso de presentarse advertencias o errores en la

ejecución de alguna(s) de las operaciones de prueba.

• Soporte de un conjunto de datos tal que dicho tamaño sea suficiente para satisfacer

los objetivos.

• Actualización del modelo visual mediante el uso de la librería gráfica JGraphT [6]

[7].

3.2. Restricciones

• La herramienta es compatible únicamente con desarrollos en lenguaje Java.

• La clase que representa a los nodos que el estudiante implemente en sus estructuras

debe tener un método toString() el cual retorna la etiqueta única con la que se

identificará dicho nodo en la visualización.

• Las etiquetas previamente mencionadas deben ser únicas en cada estructura de datos;

esto quiere decir que no puede haber dos nodos con la misma etiqueta en una misma

estructura.

• Todos los métodos en la clase StandardMethods deben estar implementados para

poder dar paso al uso de la funcionalidad asociada.

• El modelo visual hace uso de la librería JGraphT [6] [7].

21

Capítulo IV

Desarrollo del diseño

Para dar lugar al desarrollo del proyecto, es necesario hablar de varias etapas que se

presentaron de forma iterativa y acumulativa, de modo que cada una de ellas deriva en un

producto más elaborado y completo conforme a los requerimientos esperados. De este modo,

dicho proceso se presenta a continuación:

1. Búsqueda de herramientas para la visualización: para iniciar el proyecto se realizó

la búsqueda de herramientas orientadas a desarrollos en Java que facilitaran la

visualización de un modelo gráfico para las estructuras de datos, con lo cual se

obtuvieron como resultados JGraphT [6] y GraphViz [5]. De este modo, se decidió

utilizar JGraphT dado que permite que la estructura sea dinámica e interactiva,

además de mostrar cambios conforme se realizan operaciones sobre esta. Por otra

parte, con respecto a la segunda solución, GraphViz genera la vista de la estructura

en un archivo png de modo que es necesario embeberla en el programa y volver a

ejecutar la visualización conforme se realizan cambios, lo cual condujo a descartarla

entre las alternativas.

2. Implementación de una estructura de datos de prueba: para dar comienzo al uso

de la herramienta seleccionada, primero era necesario implementar una estructura de

datos en lenguaje Java con la cual interactuar para verificar el funcionamiento de esta.

Así las cosas, se procedió a implementar una estructura tipo grafo dirigido.

3. Pruebas con JGraphT: se procedió a profundizar en JGraphT realizando

operaciones básicas como la búsqueda de un nodo o conjunto de nodos, búsqueda de

los adyacentes de un nodo específico y la búsqueda de una secuencia de nodos

(camino). Cabe aclarar que esta herramienta soporta la creación de la estructura

lógica, más es necesario para la visualización el uso de una librería adicional llamada

JGraphXAdapter [7], permitiendo realizar los cambios en las etiquetas, arcos y nodos

del grafo.

Adicionalmente, para esta etapa de pruebas de JGraphT se definió un formato

estándar para la entrada de datos correspondiente al grafo a visualizar. Así las cosas,

se utilizó un archivo en formato JSON que debía contener 3 elementos necesarios: el

nombre de la etiqueta del nodo, un objeto “contenido” con la información del nodo,

y un objeto “arcos” con un arreglo que determina las conexiones con otros nodos.

Cabe señalar que los dos últimos objetos mencionados podían contener cualquier tipo

de datos como arreglos, arraylists, Strings, etc.

22

Ilustración 11. estructura de la entrada de datos

Finalmente se interpretaba el JSON introducido, lo cual se realizó con apoyo de la

librería JSON.simple [8] para recuperar los datos de manera sencilla y así proceder a

la creación de grafo.

4. Integración del visualizador con un proyecto desde el IDE Eclipse: a partir de las

pruebas realizadas, se vio necesario sustituir el método utilizado hasta el momento de

poblar la estructura con un JSON por otro método procedimental, en el que el

estudiante crea sus propios datos y pobla su implementación por sí mismo, por lo cual

se eliminó por completo el uso de los JSON para este desarrollo. Posteriormente, se

realizó la integración del visualizador con dicho proyecto mediante la importación

del proyecto en la clase principal de la herramienta, la cual hace uso de las clases en

la carpeta complementos: StandardMethods y Edge.

5. Creación de otras estructuras de prueba: continuando el desarrollo, se vio la

necesidad de probar la herramienta con estructuras diferentes, para así poder acoplar

las funcionalidades con el comportamiento que estas requieren. De este modo, se

procedió a implementar (en lenguaje Java) y adecuar con los métodos necesarios a

dos nuevas estructuras: lista encadenada y árbol binario ordenado.

6. Adición de nuevas funcionalidades: con la inclusión del soporte para nuevas

estructuras de datos, se agregaron nuevas operaciones y se modificaron otras para que

fuesen más provechosas al momento de verificar el funcionamiento de la estructura

de datos. Así pues, se añadieron las siguientes operaciones: agregar y eliminar nodos,

y buscar y agregar arcos. Adicionalmente, se implementó el soporte para tres

opciones de algoritmos libres que obedecen las funcionalidades de mostrar un

conjunto de arcos, mostrar un conjunto de nodos y mostrar un camino (secuencia de

nodos). De esta manera, mostrar arcos y nodos se encargan de indicar en la

visualización los conjuntos respectivamente retornados, pero el de mostrar camino

obedece a la modificación de la previa funcionalidad denominada “buscar camino”

tal que pasa a verificar que el camino retornado sea una secuencia de arcos o

conexiones y a dar la correspondiente retroalimentación en caso de que no cumpla

dicha condición.

7. Creación de estructuras de prueba con funcionamiento incorrecto: una vez

probadas las estructuras de datos con el funcionamiento esperado, se procedió a crear

la contraparte de cada una de ellas cuyo funcionamiento tuviese errores a modo de

emular una implementación incorrecta por parte del estudiante. De esta manera, se

23

tenían medios para probar situaciones de error y de este modo acondicionar la

herramienta para que los manejase de forma adecuada, dando la retroalimentación

además de la visualización más oportunas.

8. Integración del visualizador con un proyecto sin depender de Eclipse:

posteriormente, se ideó un mecanismo para que se pudiese hacer uso de la

herramienta sin la necesidad de utilizarla desde Eclipse, lo cual derivó en la creación

de scripts ejecutables permitiendo que el visualizador se integrase con el proyecto del

estudiante dependiendo del archivo .jar de su implementación. En este orden de ideas,

el proceso de integración procede de la siguiente manera:

• Creación del archivo .jar por parte del estudiante (ver sección 3.1).

• Inclusión del jar en el directorio “jar_files”.

• Ejecución del script clean, el cual se encarga de eliminar los archivos .class

de previas ejecuciones.

• Ejecución del script build, encargado de compilar el visualizador junto con el

archivo .jar con la implementación del estudiante.

• Ejecución del script run, el cual despliega el visualizador y da paso al uso de

la herramienta.

9. Adición de soporte para grafo no dirigido: para completar el soporte para grafos,

se decidió modificar la herramienta de modo que también funcionara correctamente

para un grafo no dirigido. Pues bien, el estudiante requiere especificar en su clase

StandardMethods que su estructura corresponde a este tipo.

10. Inclusión del panel de información: así las cosas, se agregó un panel en la parte

inferior del visualizador, encargado de dar una retroalimentación más profunda

acerca de las operaciones realizadas indicando la información retornada por la

estructura. De este modo, se provee al estudiante un medio complementario a la

visualización que le permita verificar lo que obtuvo como respuesta con respecto a lo

que esperaba en el resultado.

11. Adición de la funcionalidad de reinicio: finalmente, se contempló necesario incluir

una funcionalidad que permitiese reinicializar la estructura en caso de que alguna

operación tuviese un comportamiento inesperado, o simplemente para volver al

estado inicial e interactuar desde este estado con la estructura de datos.

4.1. Alternativas de diseño

Al momento de definir la herramienta que apoyase la representación visual de las estructuras,

se llegó a JGraphT y GraphViz como alternativas. De este modo, se profundizó en sus

respectivos funcionamientos y se llegó a que JGraphT correspondía a la herramienta más apta

para el desarrollo así como se mencionó previamente en la sección 4, Desarrollo del diseño,

numeral 1.

24

Capítulo V

Implementación

El visualizador parte de un desarrollo en Java hecho en Eclipse, el cual se despliega como un

JApplet que consume el archivo .jar del estudiante para poder funcionar correctamente. Así

las cosas, a continuación se profundizará en mayor detalle en cuanto a la interfaz visual e

integración con la herramienta.

5.1. Interfaz visual

La interfaz del visualizador se encuentra hecha en Java swing, compuesta por un frame

principal que contiene a su vez los tres paneles principales organizados mediante un

BorderLayout (Ilustración 12). De este modo, se procederá a detallar más en cada uno de los

paneles señalados en la siguiente ilustración:

Ilustración 12. Estructura de la interfaz del visualizador

25

1. Panel de opciones

Este corresponde al principal medio de interacción con la estructura, ya que es el que

conecta las entradas junto con las funcionalidades implementadas por el estudiante

para proceder a visualizar los resultados de las operaciones seleccionadas. Cabe

aclarar que, las funcionalidades que requieren de entradas mediante campos de texto

tratan principalmente con las etiquetas de los nodos; pues bien, es necesario que el

estudiante maneje el tipo de etiqueta que maneja en su estructura (si es de tipo int,

double, entre otros) con respecto al String que se envía al ser ingresado. Entonces, las

funcionalidades provistas actualmente por el visualizador son las siguientes:

• Buscar nodos

• Buscar adyacentes

• Agregar nodo

• Eliminar nodo

• Buscar arcos o conexiones

• Agregar arcos

• Mostrar arcos

• Mostrar nodos

• Mostrar camino

Por otra parte, es necesario mencionar que el panel de opciones no es el mismo para

todas las estructuras dado que dependiendo de cuál de ellas sea, no todas las

funcionalidades tienen sentido y por ende, no resultan siendo útiles. Así las cosas, a

continuación se muestran las estructuras soportadas y las funcionalidades que se

encuentran asociadas a estas:

Tabla 1. Funcionalidades por estructura

26

Adicionalmente, en la ilustración 13 es posible apreciar cómo se presenta este panel

para la lista encadenada (izquierda), árbol binario ordenado (centro) y grafo

(derecha), con las funcionalidades previamente señaladas.

Ilustración 13. Panel de opciones según el tipo de estructura

2. Panel de visualización

En este panel se ofrece una representación visual de la estructura de datos provista

por el estudiante, en la cual se actualiza la vista según las operaciones que se realicen

sobre la misma. Adicionalmente, sobre este panel se muestran advertencias o errores

en caso de que algún comportamiento inesperado tome lugar en la ejecución de una

funcionalidad. Asimismo, cabe aclarar que la visualización se apoya en el uso de una

librería externa llamada JGraphT, encargada de mostrar y refrescar los cambios en la


3. Panel de información

Finalmente, este panel está a cargo de mostrar información relevante para el

estudiante, de modo que le sea posible equiparar los resultados retornados por su

implementación con la visualización. Entonces, en este se indica inicialmente el tipo

de estructura con la que se está tratando, los resultados retornados por el estudiante y

el estado de las operaciones (completo e incompleto).

27

5.2. Integración con la herramienta

En primer lugar, es necesario contar con un par de requisitos por parte del estudiante para

proceder a la correcta integración con el visualizador, los cuales abarcan la implementación

de la interface IStandardMethods en una clase denominada StandardMethods además de la

inclusión en el proyecto de la clase Edge, que es dada al estudiante. Complementariamente,

esto puede apreciarse en mayor detalle en la sección 3, Diseño y especificaciones, numeral

3.1 Especificaciones.

El proceso de integración del visualizador con el proyecto del estudiante se dio en dos etapas

para lograr la interacción esperada, como se indica en la sección 4, desarrollo del diseño,

numerales 4 y 8. Así pues, estas se dieron como se expresa a continuación:

1. Integración desde el IDE Eclipse

Esta etapa corresponde a la primera forma de integrar el visualizador con el proyecto

de la estructura de datos, el cual se realiza directamente desde Eclipse teniendo la

implementación de prueba en el mismo workspace que la herramienta; pues bien, se

debe agregar el proyecto como dependencia mediante el build path de la

implementación del visualizador, para poder importar las clases pertinentes de la

estructura de datos para la ejecución (StandardMethods y Edge).

2. Integración con archivo .jar y scripts

Posteriormente, se buscó otra alternativa para lograr que la herramienta pudiese

desplegarse por fuera del ambiente de desarrollo, de modo que el estudiante no

tuviese que importar directamente su proyecto en el IDE. Entonces, se reformó un

poco la estructura del proyecto para incluir un directorio jar_files con los archivos

.jar necesarios para ejecutar la herramienta, donde a su vez, el estudiante debería

incluir el .jar generado a partir de su implementación. A continuación, se requiere la

interacción con los scripts contenidos en el directorio bin en la secuencia clean, build

y run; lo cuales dan indicaciones acerca de los pasos a seguir conforme se vayan

ejecutando para lograr desembocar en el correcto despliegue del visualizador.

28

Capítulo VI

Resultados

Durante el desarrollo del visualizador, se tomaron en cuenta ciertas condiciones de error en

las cuales el usuario pudiese incurrir, de modo que se estas se traten y se indique qué ha

sucedido en la ejecución. Adicionalmente, se obtuvo una serie de resultados a partir de

pruebas específicas para comprobar el funcionamiento del visualizador dependiendo de

varios escenarios. En las secciones a continuación se discuten estos temas en detalle.

6.1. Manejo de errores

Funcionalidad: Crear estructura

Entrada esperada: -

Estructuras que aplican: árbol binario ordenado, lista encadenada, grafo

Casos de error contemplados Respuesta

Ocurre una excepción al iniciar (crear) la

estructura de datos. Los datos iniciales no

logran crear una estructura de datos de

prueba.

Se muestra un aviso de error indicando que se

presentó un error al crear la estructura.

Funcionalidad: Buscar nodos

Entrada esperada (única etiqueta): nodo1

Entrada esperada (múltiples etiquetas): nodo1,nodo2,nodo3



Formato de entrada incompatible con el de

las etiquetas de la estructura

Se muestra una advertencia indicando que no

hubo resultados para dicho nodo,

adicionalmente en el panel de información se

señala que hubo un error. La entrada corresponde a un nodo

inexistente (prueba en la estructura de

datos)




señala que la búsqueda retornó sin resultados.

29

Algunos de los nodos no existen en la

estructura (prueba en el visualizador al

buscar cada nodo en la estructura de datos)


hubo resultados para algunos de los nodos,

señalando expresamente cuales de ellos son.

Además, en el panel de información se

presenta la búsqueda realizada junto con la

información retornada por el estudiante

(nodos encontrados).

El nodo buscado se encuentra en el

visualizador pero no en la estructura de

datos, o viceversa

Se muestra un aviso de error indicando que

hubo un error en la búsqueda de dicho nodo,

señalando en el panel de información los

resultados obtenidos desde la estructura de

datos.

La entrada está vacía Se muestra una advertencia indicando que la

entrada especificada está vacía, además en el

panel de información se señala que la

operación no fue completada.

Funcionalidad: Buscar adyacentes






Se muestra una advertencia indicando que el

nodo ingresado no está en la estructura,

además en el panel de información se señala

que la operación no se completó.

La entrada corresponde a un nodo

inexistente (prueba en la estructura de

datos)


nodo ingresado no está en la estructura,


que la operación no se completó. El estudiante retorna un arco o nodo que

no existe en la estructura

Aviso de error indicando que se generó un

error en la búsqueda, adicionalmente en el

panel de información se señala que se retornó

un error.





Funcionalidad: Agregar nodo




30




nodo no se ha agregado a la estructura,


que la operación no se completó. El nodo no es agregado a la estructura de

datos desde su implementación


se agregó el nodo especificado, además en el


operación no se completó.

El nodo se reporta como agregado pero no

se encuentra en la estructura, o viceversa


hubo errores al agregar el nodo especificado,


que la operación se completó con errores.





Funcionalidad: Eliminar nodo







nodo ingresado no se encuentra en la

estructura, además en el panel de información

se señala que la operación no se completó. El nodo no existe en la estructura (prueba

en la estructura de datos)


nodo ingresado no se encuentra en la

estructura, además en el panel de información

se señala que la operación no se completó.

El nodo no es eliminado de la estructura

de datos desde su implementación


nodo no se pudo eliminar, además en el panel

de información se señala que la operación no

se completó.

El nodo se reporta como eliminado pero

sigue en la estructura, o viceversa


hubo errores al eliminar el nodo especificado,


que la operación se completó con errores.





Funcionalidad: Buscar arcos o conexiones

31

Entrada esperada (único arco/conexión): nodo1>nodo2

Entrada esperada (múltiples arcos/conexiones): nodo1>nodo2,nodo3>nodo4



Formato de entrada incompatible con el

esperado


hubo resultados para el arco o conexión

ingresado, además en el panel de información

se señala que la búsqueda retornó vacía. El arco o conexión ingresado no existe en

la estructura


hubo resultados para el arco o conexión

ingresado, además en el panel de información

se señala que la búsqueda retornó vacía.

Alguno de los arcos o conexiones

ingresados no existe en la estructura

(prueba en el visualizador al buscar cada

arco en la estructura de datos)


hubo resultados para algunos de los arcos o

conexiones, señalando expresamente cuales

de ellos son. Además, en el panel de

información se presenta la búsqueda realizada

junto con la información retornada por el

estudiante (arcos o conexiones encontrados).

El arco o conexión se encuentra en el

visualizador pero no en la estructura de

datos o viceversa

Se muestra un aviso de error en el cual se

indica que hubo errores al buscar los

arcos/conexiones señalando expresamente

cuales son. Adicionalmente, en el panel de

información se disponen los resultados

obtenidos desde la estructura de datos.





Funcionalidad: Agregar arcos

Entrada esperada (único arco/conexión): nodo1>nodo2

Entrada esperada (múltiples arcos/conexiones): nodo1>nodo2,nodo3>nodo4

Estructuras que aplican: grafo


Formato de entrada incompatible con el

esperado


arco ingresado no se agregó a la estructura,


que la operación no se completó. Alguno de los arcos ingresados no se

agregó a la estructura (prueba en el

visualizador al intentar agregar cada arco

en la estructura de datos)


se agregaron algunos de los arcos, señalando

expresamente cuales de ellos son. Además, en

el panel de información se presenta la

operación realizada como completa.

32

La estructura de datos reporta que el arco

fue agregado pero realmente no lo hizo o

viceversa

Se muestra una advertencia indicando que

hubo errores al agregar ciertos arcos,



presenta la operación como completada con

errores.





Funcionalidad: Mostrar arcos

Entrada esperada: -

Estructuras que aplican: grafo


El conjunto retornado está vacío o es nulo Se muestra una advertencia indicando que no

hay un conjunto de arcos especificado,


que el conjunto de arcos retornó vacío. Formato en los arcos retornados

incompatible con el esperado


hubo resultados para el arco, además en el


búsqueda del arco retornó vacío, el cual al

aceptar el aviso de advertencia muestra el

conjunto retornado por el estudiante.

El arco retornado no existe en la estructura

(prueba en el visualizador)


hubo resultados para el arco, además en el


búsqueda del arco retornó vacío, el cual al

aceptar el aviso de advertencia muestra el

conjunto retornado por el estudiante.

Alguno(s) de los arcos retornados no

existe(n) en la estructura (prueba en el

visualizador)


hubo resultados para algunos de los arcos,




información retornada por el estudiante (arcos

encontrados), de modo que una vez que se

acepte el aviso de advertencia, éste muestre el

conjunto de arcos retornado por el estudiante.

Funcionalidad: Mostrar nodos

Entrada esperada: -

33



El conjunto retornado está vacío o es nulo Se muestra una advertencia indicando que no

hay un conjunto de nodos especificado,


que el conjunto de nodos retornó vacío. Formato de los nodos retornados

incompatible con el de las etiquetas de la

estructura




señala que hubo un error, el cual al aceptar el

aviso de advertencia muestra el conjunto

retornado por el estudiante.

El nodo retornado no existe en la

estructura (prueba en el visualizador)




señala que hubo un error, el cual al aceptar el

aviso de advertencia muestra el conjunto

retornado por el estudiante.

Algunos de los nodos retornados no

existen en la estructura (prueba en el

visualizador)


hubo resultados para algunos de los nodos,




información retornada por el estudiante

(nodos encontrados), de modo que una vez

que se acepte el aviso de advertencia, éste

muestre el conjunto de nodos retornado por el

estudiante.

Funcionalidad: Mostrar camino

Entrada esperada: -



El camino retornado está vacío o es nulo Se muestra una advertencia indicando que no

hay un camino especificado, además en el

panel de información se señala que el camino

retornado está vacío. Algunos de los arcos o conexiones no

satisfacen una secuencia (prueba en el

visualizador)

Se muestra una advertencia indicando que

algunos de los arcos o conexiones no

completan el camino, señalando

expresamente cuales de ellos son y a su vez

resaltándolos con rojo en la visualización.


34

presenta el camino retornado por el

estudiante.

El estudiante retorna un arco o conexión

que no existe en la estructura (prueba en el

visualizador)

Aviso de error indicando que se generó un

error en el camino, adicionalmente en el panel

de información se señala que se retornó un

error.

Funcionalidad: Reiniciar estructura

Entrada esperada: -



Ocurre una excepción al reiniciar la

estructura

Se muestra un aviso de error indicando que se

presentó un error al reiniciar la estructura,


que la operación no se completó.

6.2. Pruebas

Como se expresó previamente, el proyecto cuenta con tres estructuras de prueba, para las

cuales se tiene una implementación correcta y otra incorrecta. A continuación se indica por

cada funcionalidad, las pruebas realizadas además de los resultados obtenidos para cada tipo

de estructura en caso de que el comportamiento no sea generalizado.

• Casos generales

Entrada con un formato distinto al de las etiquetas

Inicialmente, al momento de ingresar la etiqueta en el campo de texto, esta es

interpretada como un String que debe ser manejado por el estudiante directamente en

su implementación, tal que es necesario que realice las conversiones necesarias al tipo

de dato que está manejando en su estructura para poder completar la búsqueda. Ahora

bien, en caso de que dicho evento no se maneje adecuadamente, la herramienta

responde con un aviso de advertencia expresando que no hubo resultados para el nodo

ingresado, adicionalmente se expresa en el panel de información que la operación

retornó error.

Ilustración 14. Aviso de advertencia para entrada errónea

35

Entrada vacía

En caso de no se ingrese nada en el campo de texto, la herramienta responde con un

aviso de advertencia en el cual indica que no la entrada está vacía. Adicionalmente,

en el panel de información de expresa que la operación de búsqueda no se completó.

Ilustración 15. Aviso de advertencia para entradas vacías

El nodo ingresado no existe en la estructura

En este caso, se muestra un aviso de advertencia en el cual se indica que el nodo no

hace parte de la estructura expresamente con su etiqueta, la cual ha sido ingresada

como entrada. Adicionalmente, en el panel de información se muestra que la


Ilustración 16. Aviso de advertencia para nodo inexistente

Búsqueda de arco conexión inexistente

En este caso, se muestra un aviso de advertencia indicando que no hubo resultados

para el arco/conexión ingresado, además en el panel de información se señala que la

búsqueda retornó vacía.

Ilustración 17. Aviso de advertencia para arco inexistente

Entrada con un formato distinto al de los arcos o conexiones

La entrada esperada para un arco o conexión corresponde a un par de nodos unidos

por el símbolo “>” a modo de indicar una flecha que los relaciona, mas en caso de

que este formato no se cumpla, se muestra la misma advertencia que se genera para

la búsqueda de un arco o conexión inexiste, así como la notificación en el panel de

información.

36

• Crear estructura

Tamaño de la estructura

Inicialmente, se probó la creación de una estructura que tuviese el comportamiento

esperado, y por ende, no implicara la generación de algún error en el despliegue. Así

las cosas, se dieron cantidades iniciales de nodos para poblar la estructura de modo

que se enfrentara dicha cantidad con respecto al tiempo que tomaba a la herramienta

generar la visualización.

Tabla 2. Tiempo para el despliegue de la visualización según la estructura y el número de nodos

De esta manera, es posible observar en la tabla 1 que la herramienta posee un buen

desempeño cuando se trata de conjuntos moderadamente grandes de nodos, siendo

que algunas estructuras se despliegan más rápido que otras con el factor adicional de

la eficiencia asociada a estas desde su implementación. Cabe aclarar que, conforme

crece el número de nodos, la visualización se hace cada vez más complicada ya que

las conexiones y vértices no pueden verse con claridad según el tamaño de la ventana.

Entonces, se determina que un tamaño promedio adecuado para lograr un buen

desempeño en la herramienta, teniendo en cuenta que las otras funcionalidades en

algunas ocasiones toman incluso el doble de tiempo con respecto al indicado en la

tabla, es de 500 nodos el cual se considera como apto para satisfacer los objetivos

del proyecto y responder peticiones en un tiempo razonable.

Estructura creada con errores

Al momento de crear la estructura, si el visualizador recibe alguna excepción en el

proceso por parte del estudiante, muestra un aviso de error informando que hubo un

error en la creación.

Ilustración 18. Aviso de error al crear la estructura

37

Estructura creada correctamente

La visualización de despliega correctamente, dando lugar a la representación de la

estructura provista por el estudiante, poblada con su información correspondiente.

Adicionalmente, en el panel de información se indica el tipo de estructura que se

encuentra representada junto con el número de nodos y arcos o conexiones presentes.

Ilustración 19. Visualización de un grafo dirigido

38

Ilustración 20. Visualización de un grafo no dirigido

Ilustración 21. Visualización de una lista encadenada

39

Ilustración 22. Visualización de un árbol binario ordenado

• Buscar nodos

Búsqueda de varios nodos (existentes e inexistentes)

Dado que la herramienta soporta la búsqueda de varios nodos en simultáneo, en caso

de que algunos de ellos no se encuentren en la estructura o que tengan un formato

incorrecto, se procede a indicar en un aviso de advertencia dichos nodos con su

etiqueta ingresada. Adicionalmente, en el panel de información se indica la búsqueda

realizada junto con los resultados retornados por el proyecto asociado, tal que la

visualización destaque los nodos que si se encontraron satisfactoriamente.

40

Ilustración 23. Estado del visualizador tras buscar nodos existentes e inexistentes

Búsqueda realizada correctamente

El visualizador resalta los nodos encontrados que se han especificado en la entrada,

además de indicar en el panel de información la búsqueda realizada junto con los

resultados retornados por la implementación de la estructura.

41

Ilustración 24. Búsqueda de nodos realizada correctamente

Búsqueda inconsistente entre el visualizador y la estructura

El visualizador resalta los nodos aunque el resultado retornado por el proyecto no

corresponda con el de la búsqueda en la visualización, y adicionalmente muestra un

aviso de error indicando que hubo un problema señalando en el panel de información

los resultados obtenidos desde la estructura de datos.

42

Ilustración 25. Estado del visualizador tras una búsqueda inconsistente

• Buscar adyacentes

Implementación con errores

Al momento de presentarse errores en esta funcionalidad, el visualizador destaca el

nodo buscado en rojo y los demás valores retornados en amarillo aunque no sean

correctos. Adicionalmente, en el panel de información se indica la búsqueda realizada

junto con los resultados retornados por el proyecto asociado.

43

Ilustración 26. Estado del visualizador tras una búsqueda de adyacentes implementada incorrectamente


El visualizador destaca en rojo el nodo buscado y en amarillo los nodos y arcos que

los conectan, adicionalmente se indica en el panel de información la búsqueda

realizada junto con el resultado retornado por la estructura.

44

Ilustración 27. Búsqueda de adyacentes realizada correctamente

• Agregar nodos


En la implementación errónea realizada, el nodo no se agrega como se debe a la

estructura de modo que en el visualizador se muestra igualmente la modificación

retornada desde el proyecto asociado, destacando el nuevo nodo e indicando en el

panel de información que la operación se ha completado, el número de nodos y

arcos/conexiones después de la ejecución.

45

Ilustración 28. Estado del visualizador al agregar incorrectamente un nodo

Inconsistencia en el resultado de la operación

El nodo no es agregado a la estructura pero se reporta como operación exitosa. En

este caso se muestra un aviso de error indicando el problema al agregar, además de la

notificación del estado de la operación en el panel de información.

46

Nodo agregado correctamente

El nodo se muestra en la visualización según lo retornado por la estructura, donde se

resalta la nueva adición e indicando en el panel de información que la operación se

ha completado. Además, se indica el número de nodo y arcos o conexiones después

de completar la funcionalidad.

Ilustración 29. Estado del visualizador tras adición correcta de un nodo

Nodo no agregado

El nodo no se agrega a la estructura, lo cual genera una advertencia en la visualización

indicando que no se agregó, además en el panel de información se muestra que la


Ilustración 30. Inserción de nodo fallida

• Eliminar nodos

Resultado de eliminación inconsistente

En caso de tratar con una implementación incorrecta en la que el nodo se reporta

como eliminado pero sigue en la estructura, la visualización muestra el estado de la

estructura retornado por el proyecto asociado, además de un aviso de error notificando

47

el problema al eliminar. Adicionalmente, en el panel de información se señala que la

operación de eliminación se completó con errores junto con el número de nodos y

arcos/conexiones posteriores a la ejecución.

Ilustración 31. Estado del visualizador tras eliminación incorrecta de un nodo

Nodo eliminado correctamente

La visualización muestra la estructura modificada además de un aviso de advertencia

en el cual notifica la eliminación del nodo expresamente con su etiqueta asociada.

Adicionalmente, en el panel de información se indica que la operación de eliminación

se ha completado junto con el número de nodos y arcos/conexiones posteriores a la

ejecución.

48

Ilustración 32. Estado del visualizador tras eliminación correcta de un nodo

• Buscar arcos o conexiones

Búsqueda de varios arcos o conexiones (existentes e inexistentes)

Cuando se ingresan varios arcos o conexiones para realizar la búsqueda y algunos de

ellos no existen en la estructura, se muestra un aviso de advertencia en el cual se

indica expresamente aquellos que no se han encontrado, adicionalmente, en el panel

de información se muestra la búsqueda realizada junto con el resultado retornado por

el proyecto asociado.

49

Ilustración 33. Estado del visualizador tras la búsqueda de arcos existentes e inexistentes


En caso de tratar con una implementación incorrecta, la visualización muestra el

estado de la estructura retornado por el proyecto asociado, destacando los nodos y

arcos/conexiones que se reciben como respuesta. Adicionalmente, en el panel de

información se señala la búsqueda realizada junto con la respuesta obtenida por parte

de la estructura.

50

Ilustración 34. Estado del visualizador tras una búsqueda implementada incorrectamente


Para una implementación correcta de la funcionalidad, el visualizador destaca el arco

o conexión retornado junto con los nodos correspondientes tras la búsqueda, además

en el panel de información se indica la operación y el resultado obtenido por parte de

la estructura.

51

Ilustración 35. Estado del visualizador tras la correcta búsqueda de un arco o conexión

• Agregar arcos

El arco ingresado ya existe en la estructura

En este caso, se muestra una advertencia indicando que el arco no se agregó a la

estructura, expresamente con su identificador. Además, en el panel de información se

muestra que la operación no se completó.

Ilustración 36. Aviso de advertencia al agregar un arco existente

Implementación con resultados inconsistentes

Para una implementación en la que los arcos no se agreguen a la estructura y se

reporten como agregados, se muestra un aviso de error indicando el problema al

agregar, además de señalar en el panel de notificación que la operación se completó

con errores.

52

Ilustración 37. Aviso de error al presentarse inconsistencias

Adición de arcos correcta

En la visualización de la estructura se destacan los nuevos arcos junto con los nodos

implicados, además en el panel de información se indica que la operación de adición

se completó. Adicionalmente, se muestra el número de nodos y arcos/conexiones

posteriores a la ejecución.

Ilustración 38. Estado del visualizador tras la adición correcta de arcos

• Mostrar arcos

Conjunto de arcos vacío

En caso de que no se retorne un conjunto vacío, el visualizador muestra un aviso de

advertencia en el cual se indica que no hay un conjunto de arcos especificado, además

en el panel de información se muestra que dicho conjunto retornó vacío.

53

Ilustración 39. Aviso de advertencia para un conjunto de arcos vacío

Conjunto de arcos lleno

En la visualización se muestra la estructura destacando los arcos retornados en el

conjunto además de los nodos involucrados. Adicionalmente, en el panel de

información se indica cuáles son los arcos que se recibieron por parte del proyecto

asociado.

Ilustración 40. Estado de la visualización tras mostrar el conjunto de arcos

• Mostrar nodos

Implementación incorrecta

En este caso, la implementación retorna un conjunto de nodos que se visualizan

incorrectamente, así que en la estructura se señalan los resultados retornados por la ejecución, además de que en el panel de información se indica el conjunto obtenido a

partir del proyecto asociado.

54

Ilustración 41. Estado del visualizador tras mostrar un conjunto de nodos con búsqueda incorrecta

Conjunto de nodos lleno

Al igual que en el caso anterior, se destacan los nodos y se indican en el panel de

información los resultados retornados por la estructura.

Ilustración 42. Estado de la visualización tras mostrar el conjunto de nodos

55

• Mostrar camino

Implementación incorrecta

El camino retornado por la estructura no cumple la condición de ser secuencial, por

lo que en la visualización se indican los nodos secuenciales en amarillo junto con los

arcos que los conectan, en rojo aquellos que rompen la secuencia y en cian los nodos

inicial y final. Adicionalmente, en el panel de información se indica el camino

retornado por el proyecto asociado.

Ilustración 43. Estado de la visualización tras mostrar un camino no secuencial

Camino realizado correctamente

En la visualización se muestra el camino retornado destacando en amarillo los arcos

y los nodos involucrados, así mismo, los nodos inicial y final se muestran color cian

para distinguirlos más fácilmente. Además, en el panel de información se presenta el

camino retornado por la estructura como ayuda complementaria a la visualización.

56

Ilustración 44. Estado del visualizador tras mostrar un camino

• Reiniciar estructura

Reinicio completado

La estructura se muestra en el panel de visualización en su estado original,

descartando todas las operaciones y cambios que se realizaron sobre esta.

Adicionalmente, en el panel de información se indica que la estructura ha sido

reinicializada.

Reinicio con errores

En este caso se muestra un aviso de error en el cual se indica que hubo un error al

realizar la operación, de modo que no se despliega la herramienta.

Ilustración 45. Aviso de error el reiniciar con problemas

57

Capítulo VII

Conclusiones

Al completar el desarrollo del presente proyecto de grado, se evidenció que durante su

transcurso se dio una serie de avances y mejoras para lograr una herramienta completa que

satisfaga los objetivos propuestos. Aun así, también tomaron lugar algunos retos a superar

para poder completar los planteamientos respectivos al visualizador, los cuales se exponen a

continuación.

Inicialmente, hubo una dificultad con respecto a la integración de la herramienta con un

proyecto externo debido al desconocimiento en cuanto al método a utilizar, el cual fue

superado en colaboración con el asesor del proyecto de grado permitiendo que el uso del

visualizador fuera del ambiente de desarrollo fuese exitoso. Adicionalmente, en cuanto se

llegó a la etapa de pruebas, se encontró la dificultad de elaborar estructuras que tuviesen tanto

un funcionamiento correcto como incorrecto. Esto debido a que se presentaban

complicaciones en el momento de replicar un funcionamiento incorrecto, dado que se debían

cubrir varios casos a modo de emular los posibles errores que un estudiante podría cometer

al implementar sus estructuras.

Asimismo, una de las dificultades más esenciales se dio al momento de interactuar con la

librería JGraphT dado que se requería que la visualización provista fuese lo más útil y

acertada posible. Entonces, fue algo un poco empírico y a base de intentos el poder encontrar

las configuraciones adecuadas en cuanto a los formatos visuales (layouts) empleados según

el tipo de estructura así como la manipulación de la estructura lógica, los cuales terminaron

siendo satisfactorios y permitieron lograr una visualización apta para efectos del proyecto.

A modo de conclusión, tras haber superado los inconvenientes presentados, el visualizador

implementado contempla como completados los objetivos planteados ya que constituye una

herramienta que provee soporte para las estructuras de datos grafo (dirigido y no dirigido),

árbol binario ordenado y lista encadenada, dando lugar a la validación visual del

funcionamiento de un proyecto externo. Además, aunado a esto se encuentra un módulo de

retroalimentación y reporte de errores posibilitando al estudiante tanto mejorar su

implementación como probar algoritmos que sean de su interés.

7.1. Trabajo futuro

Finalmente, hay aspectos de la herramienta que se encuentran prestos a mejoras para lograr

un funcionamiento con un mejor desempeño e incluso con nuevos aspectos para expandir las

funcionalidades actuales.

58

De esta manera, el proyecto queda abierto a nuevos desarrollos que potencien la utilidad del

mismo, los cuales pueden tratarse acerca de la optimización del desempeño y posiblemente

mayor rapidez en el despliegue de resultados, así como la inclusión de nuevas operaciones

que pueden ser relevantes para el público objetivo. Además, podría entrar en consideración

el soporte para otros tipos de estructuras que puedan ser de interés para su análisis visual y

funcional.

59

Referencias

[1] Halim, S. VisuAlgo - visualising data structures and algorithms through animation.

Recuperado el 10 de febrero de 2020, de https://visualgo.net/es

[2] Galles. D. Data Structure Visualization. Recuperado el 10 de febrero de 2020, de

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

[3] Almanza-Cortés, D., Del Toro-Salazar, M., Urrego-Arias, R., Feijóo-García, P., & De la

Rosa-Rosero, F. (2019). Scaffolded Block-based Instructional Tool for Linear Data

Structures: A Constructivist Design to Ease Data Structures’ Understanding. International

Journal of Emerging Technologies in Learning (iJET). Recuperado el 1 de marzo de 2020,

de https://online-journals.org/index.php/i-jet/article/view/10051

[4] Nathasya, R., Karnalim, O., & Ayub, M. (2019). Integrating program and algorithm

visualisation for learning data structure implementation. Egyptian Informatics

Journal, 20(3), 193-204. Recuperado el 4 de marzo de 2020, de

https://www.sciencedirect.com/science/article/pii/S1110866518302603?via%3Dihub

[5] AT&T Labs (2016). Graphviz - Graph Visualization Software. Recuperado el 7 de marzo

de 2020, de http://graphviz.org

[6] Michail, D., Kinable, J., Naveh, B., & Sichi, J (2020). JGraphT -- A Java library for

graph data structures and algorithms. . ACM Transactions on Mathematical Software, Vol.

46, No. 2, Article 16, pp. 1 – 29, Junio 2020. Recuperado el 7 de marzo de 2020, arXiv

preprint arXiv:1904.08355, 2019 - arxiv.org

[7] Tinevez, J. (2020). JGraphXAdapter (JGraphT : a free Java graph library). Recuperado

el 7 de marzo de 2020, de https://jgrapht.org/javadoc/org/jgrapht/ext/JGraphXAdapter.html

[8] Fang, Y. (2014). Recuperado el 7 de marzo de 2020, de

https://code.google.com/archive/p/json-simple/

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

https://online-journals.org/index.php/i-jet/article/view/10051

https://www.sciencedirect.com/science/article/pii/S1110866518302603?via%3Dihub

http://graphviz.org/

Visualizador de Estructuras de Datos

Documents

Transcript of Visualizador de Estructuras de Datos