ProRouting

PROROUTING (PROximity Graphs and ROUTING) es una herramienta diseñada para el estudio de grafos geométricos, en particular de los grafos de proximidad, las estrategias de ruteo en ellos y sus propiedades.

La herramienta se empezó a desarrollar en 2004 y desde entonces se le han añadido numerosas mejoras y aumento de funciones. En este momento está disponible la versión 2. A continuación se describen algunas de las características de la aplicación.

Grafos de proximidad y estructuras geométricas en PROROUTING

• Grafo del vecino más cercano. Grafo de los k-vecinos más próximos. Par más próximo.
• Cierre convexo.
• Árbol generador de peso mínimo. Árbol generador de peso mínimo k-local.
• Grafo del disco unidad.
• Grafo de Vecindad Relativa.
• Grafo de Gabriel.
• Triangulación incremental. Triangulación voraz.
• Triangulación de Delaunay. Diagrama de Voronoi.
• Beta-esqueletos.
• Grafo de proximidad por semiplanos.
• Familia de grafos theta-lambda.
• Theta grafo. Theta grafo dirigido. Theta grafo ordenado. "Sink spanner".
• Grafo de Yao. Grafo de Yao dirigido. Grafo Yao-Yao. Grafo de Yao simétrico.

Estrategias de ruteo en PROROUTING

• Ruteo voraz.
• Ruteo por brújula. Ruteo aleatorizado por brújula.
• Ruteo híbrido voraz-brújula.
• Ruteo Voronoi.
• Ruteo por caras (variantes 1 y 2). Ruteo voraz-cara-voraz.
• Ruteo ad-hoc para grafos theta-lambda.
• Estudio de la calidad de todas las estrategias de ruteo.

Construcción de caminos y spanners en PROROUTING

• Caminos de longitud mínima en un grafo (algoritmo de Dijkstra).
• Algoritmo PathGreedy.
• Algoritmo Sparse Spanner.
• Cálculo de la dilación de todos los grafos construidos.

Los autores de la herramienta, desarrollada de forma acumulativa en la Facultad de Informática de la Universidad Politécnica de Madrid, son:

• David Ramos (versión preliminar, julio 2004)
• José María Gil (versión 1.0, julio 2007)
• Víctor Chavero (versión 2.0, mayo 2009)
• Edgar Méndez (versión 2.1, febrero 2014)