IDELabRoute: Librería para la gestión de grafos escalables.

Sistema de gestión de grafos dinámico que pueda manejar grandes modelos de redes de forma escalable, de forma que pueda utilizarse en entornos con pocos recursos o con un ciclo de trabajo bajo.

TSPEn experiencias previas con grandes sistemas de cálculos de rutas para servidores hemos encontrado que hay algunas carecias importantes en las librerías disponibles como OpenSource cuando se trata de manejar grandes redes con millones de nodos. Las librerías que conocemos usan un modelo de gestión de los grafos que generan una estructura mallada de objetos en memoria. Este modelo precisa grandes cantidades de memoria y unos tiempos de puesta en marcha elevados.

Este proyecto pretende desarrollar un sistema de gestión de grafos dinámico que pueda manejar grandes modelos de redes de forma escalable, de forma que pueda utilizarse en entornos con pocos recursos o con un ciclo de trabajo bajo.

El proyecto está en las primeras fases y aún ofrece limitadas prestaciones, aunque ya es funcional en muchas de sus características básicas.

Objetivos

IDELabRoute persigue los siguientes objetivos:

  • Librería Java basada en Geotools 2 y OpenSource.
  • Desacoplo de objetos en memoria para permitir el reciclado de memoria.
  • Desacoplo de los almacenes físicos donde se aloja el grafo para permitir diversas estrategias de almacenamiento.
  • Flexibilidad en el modelo de los fenómenos físicos asociados al grafo.
  • Servicios estándar de acceso a las operaciones con el grafo mediante estándares Web y OGC (Open Geospatial Consortium).
  • Integración en aplicaciones de escritorio.
  • Grafos no dirigidos con impedancias bidireccionales y nodos con impedancias en los giros.
  • Operaciones principales sobre los grafos:
    • Camino más corto mediante heurísticas A*.
    • Zona de cobertura o WithinCost.
    • Problema del viajante.
  • Posibilidad de incluir excepciones en la ejecución de un algoritmo de forma segura para entornos multihilo. Por ejemplo: tramos prohibidos o enlaces entre elementos.
  • Interrelación de subredes para el cálculo de rutas intermodales.
  • Muchas otras funciones en el futuro.

Tipos básicos de Grafos

Los grafos pueden poseer una serie de propiedades que los caracterizan, los diferencian entre ellos y en base a las cuales se les puede clasificar. A continuación se hace una breve descripción de algunos de los tipos básicos de grafos existentes según tengan o no algunas de estas propiedades.

Se dice que un grafo es simple cuando no posee bucles, ni existen varias aristas que unan los mismos vértices, es decir, aristas múltiples. Los grafos que poseen aristas múltiples reciben el nombre de multigrafos.

Otra diferenciación fundamental que hay que considerar es la existente entre grafo dirigido y no dirigido. Un grafo dirigido o digrafo, es aquel en el que sus aristas tienen una orientación (son dirigidas), mientras que en el no dirigido no existe tal condición. Las aristas dirigidas de un digrafo reciben el nombre de arcos, y al ser definidas mediante los vértices que unen es relevante el orden de éstos. Los extremos de estos arcos suelen recibir el nombre el cabeza y cola, estando el arco dirigido desde su cola hasta su cabeza. Todo grafo dirigido posee un grafo no dirigido asociado, que consiste en el mismo grafo con idéntico número de vértices pero sin establecer una orientación en sus aristas. Los grafos que poseen tanto arcos como aristas suelen ser conocidos como mixtos. En un dígrafo, el orden de sus vértices se calcula sumando sus grados de entrada y salida. El grado de entrada es el número de arcos entrantes en ese vértice, aquellos que le tienen como cabeza. El grado de salida es el número de arcos salientes del vértices, los que le tienen como cola.

Hay muchas otras características que se definen para los grafos y que se tienen en cuenta en las implementaciones de los algoritmos de IDELabRoute.