grafoLib es una librería de grafos programada desde cero en Kotlin que implementa numerosos algoritmos sobre grafos dirigidos y no dirigidos.

Realizada con fines académicos para el curso de CI-2693 de la Universidad Simón Bolívar (Sartenejas, Venezuela), dictado por el profesor Guillermo Palma ([email protected]) en el periodo Septiembre-Diciembre 2021.

La carpeta de Especificaciones contiene las especificaciones seguidas a para la implementación cada clase de la librería, donde se indican qué métodos y algoritmo debían ser implementado, junto a indicaciones adicionales del profesor del curso.

La librería fue construida siguiendo las especificaciones contenidas en los archivos de la carpeta, a lo largo de nueve laboratorios y dos proyectos.

La carpeta incluye dos estudios sobre algoritmos:

• AlgoritmosMTS: Estudio sobre la eficiencia y los resultados de los algoritmos implementados en la librería para hallar componentes conexas y árboles mínimos cobertores en grafos no dirigidos. En específico, compara:

  • Para hallar componentes conexas:
    • Un algoritmo basado en Búsqueda en Profundidad (DFS), implementado de forma recursiva e iterativa.
    • Un algoritmo basado en la estructura de datos de conjuntos disjuntos, implementada usando las heurísticas de compresión de camino y de compresión por rango.
  • Para hallar árboles mínimos cobertores:
    • El algoritmo de Kruskal, que usa la estructura de conjuntos disjuntos.
    • El algoritmo de Prim, usando una cola de prioridad basada en binary heap, implementada como clase interna.

• Solución RPP: Estudio sobre la implementación realizada en la clase HeuristicaRPP de un algorito heurístico propuesto por Pearn y Wu para resolver el problema del cartero rural, o RPP (Rural Postman Problem). Se explica la solución y los detalles de implementación pertinentes, y se incluye un análisis comparativo de los resultados, comparando la eficacia y eficiencia del algoritmo usando dos algoritmos heurísticos para hallar apareamientos perfectos de costo mínimo aproximado:

  • Un algoritmo ávido descrito en el archivo correspondiente al Proyecto 2 en la carpeta de especificaciones.
  • El algoritmo Vertex-Scan propuesto por David Avis.

Se incluye un Makefile que compila la librería entera con el comando

> make

La librería entera es construida usando como base la interfaz Grafo y la clase abstracta Lado. Las clases que implementan Grafo son GrafoNoDirigido y GrafoDirigido, y las implementaciones de Lado se encuentran en Arista y Arco, como los lados de GrafoNoDirigido y GrafoDirigifo, respectivamente.

Este proyecto está bajo la Licencia GNU GPL v3.0 - mira el archivo LICENSE.md para detalles

Hecho con ❤️ por chrischriscris y fungikami 😊