Repository files navigation

🔹 JLibGraph es una biblioteca desarrollada en el lenguaje de programaciónJava. Posee como objetivo fundamental el manejo de grafos y la realización de operaciones sobre estos. Su enfoque se basa en el tratamiento de varios problemas comunes en lateoría de grafos: rama de las matemáticas dedicada a los grafos y sus problemáticas asociadas.

🔹 Un grafo es un conjunto no vacío de vértices y aristas. Las aristas son pares ordenados de la forma (u, v), representando las líneas que conectan dichos vértices, y pueden ser clasificadas en adyacentes, paralelas, cíclicas o cruzadas; mientras que los vértices son los elementos que conforman el grafo y tienen un grado dependiente del número de aristas que inciden sobre dicho vértice. Un camino es el conjunto de vértices interconectados por aristas.

La biblioteca aspira a implementar los siguientes tipos de grafos:

• Simple
• Multígrafo
• Dirigido
• Etiquetado
• Aleatorio
• Regular
• Dual

Para dar tratamiento a algunos problemas comunes en teoría de grafos se han implementado los siguientes algoritmos:

• Árboles de expansión
  • Prim
  • Kruskal
• Caminos más cortos
  • Bellman-Ford
  • Dial
  • Dijkstra
  • Floyd-Warshall
• Centralidad:
  • Katz
• Ciclos
  • Detección de ciclos
  • Ciclo de Euler
  • Ciclo de Hamilton
• Componentes fuertemente conexos (SCC):
  • Kosaraju
• Comunidades:
  • Girvan-Newman
• NP de m-números cromáticos:
  • Colorable
  • Greedy
• Redes de flujo
  • Ford-Fulkerson

La biblioteca está programada enJava, y contiene un amplio espectro de algoritmos y utilidades generales para trabajar con grafos y árboles. El paquete principal escu.edu.cujae.graphy.core. Ahí se encuentran la mayoría de interfaces. La interfaz genéricaGraph<T> representa cualquier tipo de grafo, mientras que la interfazWeightedGraph<T> extiende a la interfazGraph<T> añadiendo operaciones para el trabajo con pesos. La instanciación de los grafos puede realizarse a través de losbuilders, pero la clase de utilidadGraphBuilders proporciona métodos estáticos para construir grafos.El paquetecu.edu.cujae.graphy.algorithms incluye los algoritmos de la biblioteca. Muchos de ellos toman como parámetro unGraphIterator<T>. Los iteradores pueden ser secuenciales o aleatorios y constituyen la vía de manipulación de los datos en la biblioteca.

No se exponen los nodos de los grafos (excepto en la biblioteca de árboles).

Actualmente se encuentran soportados los siguientes IDEs:

• NetBeans (el desarrollo principal se efectúa aquí)
• Visual Studio Code
• Eclipse (soporte parcial)

// La interfaz Graph es genérica y puede contener cualquier objeto// El boolean de makeSimpleGraph determina si el grafo construído es dirigido o noGraph<Object>graph =GraphBuilders.makeSimpleGraph(false);

// La interfaz WeightedGraph<?> extiende a Graph<?>// El boolean cumple la misma función en todos los métodos de GraphBuildersWeightedGraph<Object>weightedGraph =GraphBuilders.makeSimpleWeightedGraph(false);

Los iteradores pueden ser aleatorios, a lo ancho o en profundidad

Graph<Object>graph =GraphBuilders.makeSimpleGraph(false);GraphIterator<Object>randomIterator =graph.randomIterator();// o también un parámetro entero que representa el identificador del nodo en el graforandomIterator =graph.iterator(0);

GraphIterator<Object>depthFirstSearchIterator =graph.depthFirstSearchIterator();

GraphIterator<Object>breadthFirstSearchIterator =graph.breadthFirstSearchIterator();

Para contribuir al proyecto, debe clonar primero el repositorio. En la ramamain se encuentra el código estable, mientras que la rama activa de desarrollo esdevelopment. Todos los pull requests conmain odevelopment como destino tendrán que ser aprobados por los revisores. No olvide mirar losissues y las discusiones con frecuencia 😉. Cualquier cambio al código o sugerencia debe ser puesto comoissue, y las discusiones generales en su respectiva pestaña.

La siguiente lista se encuentra ordenada alfabéticamente. Siéntase libre de incluirse en ella si ha hecho alguna contribución al proyecto, sólo manténgala ordenada, por favor:

• J. García:mango:(@JoseCarlosGarcia)
• J. Marrero:robot:(@JavierMarrero)
• A. Méndez:watermelon:(@Amy-Mendez)
• A. Morales:snowflake:(@SnowBlackQueen)
• C. Robaina:evergreen_tree:(@cdrobaina01)

Por esta vía se realiza un agradecimiento especial al colectivo de la asignaturaEstructura de Datos de la Facultad de Ingeniería Informática, de la Universidad Tecnológica de La Habana "José Antonio Echeverría" (CUJAE), específicamente a la profesoraDr. C. Lisandra Bravo Ilisástigui (@Lisibravo), por la idea original 💛.

El proyectoJLibGraph es software libre y se encuentra licenciado bajo los términos de la GNU Lesser General Public License en su versión 2.1 u opcionalmente versiones posteriores.