MANUAL DE USUARIO
ProRouting es una aplicación que permite el dibujo de Grafos de Proximidad y la
utilización sobre ellos de algunos algoritmos de ruteo online. Está implementada con el
lenguaje de programación Java, y puede utilizarse en cualquier sistema que
tenga instalada la Máquina Virtual de Java ( JVM ).
ProRouting esta basada en trabajos anteriores realizados por los compañeros de facultad David Ramos, Rubén Naranjo y Damián Serrano.
La aplicación consta de los siguientes elementos:
barra de herramientas de grafos.
barra de herramientas de ruteo.
zona de
dibujo (superficie gráfica o lienzo).
Figura 1. Aplicación ProRouting
A continuación vamos a describir los distintos
elementos que componen la herramienta.
1. Barra de menús
La barra de menús consta de cinco menús desplegables: File, Edit, Execution, View y Help.
El menú File
contiene los comandos de manejo de ficheros:
New … Crea un
nuevo espacio de trabajo y elimina el anterior.
Open… Abre un archivo de grafo, con
extensión .grp.
Save… Guarda en fichero los vértices del
grafo que esta en
pantalla, así como las aristas del grafo manual.
Exit … Salir
de la aplicación.
Figura 2. Menú File
1.2. Menú Edit
El menú Edit contiene comandos para inserción de vértices.
Insert->Draw nodes… Inserción manual de puntos
Insert->Automatic… Inserción aleatoria de puntos
Select… Selección
de puntos
Remove… Eliminación de
vértices
Figura 3. Menú Edit
1.3. Menú Execution
El menú Execution el modo
de ejecución dinámico (por defecto) o el modo ejecución paso
a paso.
Dinamic… Modo de ejecución dinámico.
Step->Start… Modo de ejecución paso a paso, de la
construcción de un
grafo, o de la ejecución de un algoritmo de ruteo.
Step->Stop Detiene
la ejecución paso a paso y vuelve al modo de
ejecución dinámico.
Figura 4. Menú Execution.
1.4. Menú View
El menú View establece que grafos se dibujan en pantalla. También
cuenta con el comando Open Reference System, que carga una imagen de extensión .jpg, .gif o .png de fondo como referencia para la introducción
manual de puntos y dibujo de aristas.
Figura 5. Menú View
2. Barras de Herramientas de Grafos y
manejo de ficheros
Esta barra agrupa los botones que dibujan /
ocultan los grafos de proximidad
construidos a partir de los puntos que están actualmente en pantalla. También
contiene botones para manejo de ficheros, control de animaciones y dibujo
manual de grafos.
Figura 6. Barra de herramientas de
grafos y ficheros
Crea un nuevo espacio de trabajo y
elimina el anterior.
Abre un archivo de grafo, con extensión
.grp.
Guarda en fichero los vértices del grafo
que esta en pantalla, así como
las aristas del grafo manual.
Carga una imagen de extensión .jpg, .gif o .png de fondo como sistema de referencia para la
introducción manual de puntos y dibujo de aristas.
Dibuja / Oculta el sistema de referencia.
Abre la ventana de configuración de los
distintos grafos y algoritmos de ruteo.
Establece el modo de inserción manual de puntos.
Establece el modo de inserción manual de
aristas. Sólo pueden
introducirse aristas manualmente si hay un único grafo visible
en
pantalla. La arista introducida se añade a este grafo.
Abre
una ventana de diálogo para introducir un número n entero
positivo. Al pulsar el botón OK se dibujan en el grafo n puntos de
coordenadas aleatorias.
Elimina el punto seleccionado y las
aristas adyacentes.
Avanza un paso de la animación cuando está seleccionado del
modo de
ejecución paso a paso.
Detiene la animación actual y restaura
el modo de ejecución dinámico.
Dibuja / Oculta el grafo manual, que sólo consta de los
vértices aristas
dibujadas manualmente.
Dibuja / Oculta el Grafo del Vecino Más
Próximo.
Dibuja / Oculta el Árbol Generador
Mínimo.
Dibuja / Oculta el Grafo de Vecindad
Relativa.
Dibuja / Oculta el Grafo de Gabriel.
Dibuja / Oculta la Triangulación
Incremental.
Dibuja / Oculta la Triangulación de Delaunay.
Dibuja / Oculta la Triangulación de Delaunay Restringida.
Dibuja / Oculta la Triangulación Voraz.
Dibuja / Oculta el Diagrama de Voronoi.
Dibuja / Oculta el Grafo de Yao.
Dibuja / Oculta el Grafo Theta.
Dibuja / Oculta el Grafo de Disco
Unidad.
Dibuja / Oculta el Grafo Half-Space Proximal.
Dibuja / Oculta la familia de grafos
Theta-Lambda
Dibuja / Oculta la familia de Grafos Beta-Skeleton.
Dibuja / Oculta el par de puntos más
próximo.
Dibuja / Oculta el cierre convexo.
Dibuja
/ Oculta los vecinos de Delaunay de un punto.
3.
Barra de herramientas de ruteo y configuración.
Figura 7. Barra de herramientas de ruteo y configuración.
Dibuja / Oculta el camino
correspondiente a Ruteo Voraz.
Dibuja / Oculta el camino
correspondiente a Ruteo con Brújula.
Dibuja / Oculta el camino
correspondiente a Ruteo con Brújula
aleatorizado.
Dibuja / Oculta el camino correspondiente
al Ruteo Voraz-Brújula.
Dibuja / Oculta el camino
correspondiente al Ruteo de Voronoi.
Sólo se
encuentra seleccionable el botón si está visible la triangulación de
Delaunay.
Dibuja
/ Oculta el camino correspondiente al Ruteo por Caras
1.
Dibuja / Oculta el camino
correspondiente al Ruteo por Caras 2.
Dibuja / Oculta el camino
correspondiente al Ruteo Voraz-Caras-Voraz.
Dibuja / Oculta el camino
correspondiente al Ruteo local en el grafo
Theta-Lambda. Este botón sólo es seleccionable si está visible el grafo
Theta-Lambda.
Dibuja / Oculta el camino
correspondiente al camino mínimo (Dijkstra).
Establece el modo selección de nodo origen de ruteo.
Establece el modo selección de nodo
destino de ruteo.
Dilation(s,t): razón entre la longitud del camino de dijkstra entre s y t y la distancia euclidea s,t.
Dilation (G) :es el máximo de Dilation (s,t) , considerando todos los posibles puntos s y t dentro de G.
AD (s,t) , Alg. Distance : longitud del camino encontrado por el algoritmo en
uso.
SPD(s,t), Shortest path distance : longitud del camino mínimo entre s y t.
ED (s,t): Distancia euclidea entre s y t.
4.
Superficie gráfica
La superficie gráfica tiene como funciones
principales la introducción de puntos y aristas por parte del usuario, y el
dibujo de los grafos y caminos
encontrados por los algoritmos de ruteo con las
opciones actualmente seleccionadas. Los puntos se representan de color rojo, y
las aristas del color que este configurado el grafo en cuestión. El camino
encontrado por cada algoritmo de ruteo se dibuja del
color que esté configurado y de un grosor superior al de las aristas.
La mecánica de introducción de datos es la
siguiente:
·
Inserción de puntos: haciendo click con el botón
izquierdo del ratón, sobre el icono
de la barra de herramientas de grafos para
insertar puntos, se selecciona el modo de inserción de puntos. El cursor adopta
forma de cruz sobre la superficie gráfica, y sus coordenadas se muestran en la
barra de estado. Haciendo click con el botón derecho o izquierdo sobre la superficie
se inserta un punto sobre las coordenadas actuales.
·
Selección de puntos: estando el botón de inserción de puntos no
seleccionado y haciendo click con el botón derecho o izquierdo del ratón sobre algún punto insertado
anteriormente, podemos seleccionar el punto, que aparecerá con un borde azul.
·
Inserción de aristas: para insertar aristas de forma manual debe estar
visible sólo un grafo, y se añadirán en el las nuevas aristas. También debe
estar seleccionado el modo de inserción de aristas, haciendo click con el
botón izquierdo del ratón sobre el icono
. Para
introducir una arista es necesario seleccionar los dos puntos que va a unir la
arista.
·
Borrado de puntos: Para eliminar un punto es necesario seleccionarlo y después pulsar la
tecla Supr
o hacer click con el ratón sobre el icono
. Se eliminarán de forma automática las
aristas incidentes sobre ese punto.
·
Desplazamiento de puntos: es necesario seleccionar un punto y arrastrarlo sin
soltar el botón del ratón hasta que no se llegue al lugar deseado.
5.
Barra de estado
La parte derecha de la barra de estado muestra las
coordenadas actuales del ratón sobre la superficie gráfica. La parte izquierda
muestra información sobre las operaciones que se están realizando en cada
momento, tipo de grafo construido, si el algoritmo de ruteo ha tenido éxito o no, solicita selección de puntos para crear una arista,
información sobre el paso que se está realizando en el modo de ejecución paso a
paso, etc.
Figura 8. Barra de estado.
6.
Ventana de configuración
Se accede haciendo click con el ratón sobre el icono
de la barra de herramientas de ruteo y configuración. La ventana de configuración contiene
dos pestañas seleccionables.
La primera permite configurar los grafos de proximidad ,
y la segunda los algoritmos de ruteo.
Cada pestaña contiene un combo que permite seleccionar cada uno de los grafos (o de los
algoritmos de ruteo) y acceder a los parámetros
configurables. En el caso de los grafos podemos cambiar el color de las
aristas, si se intersecciona con el grafo de Disco
Unidad, y otros parámetros particulares de cada grafo. En el caso de los
algoritmos de ruteo sólo es configurable el color de
las aristas del camino.
Figura 9. Ventana de configuración.