Una biblioteca moderna (más o menos) de representación gráfica y manipulación de C++

En mi antiguo lugar de trabajo tenía experiencia mixta con la biblioteca de gráficos de Boost ; Yo no era la persona que trabajaba con ese código principalmente, pero experimentamos fragilidad, cosas que cambiaban bajo nuestros pies y la necesidad de actualizar el estado repetidamente por razones no suficientemente buenas. Sí, sé que esto suena un poco vago, pero el punto es que quiero ver las alternativas.

Entonces, estoy buscando una biblioteca de gráficos que:

  • Representa gráficos dirigidos y no dirigidos.
  • No depende de Boost en absoluto, o al menos no de forma significativa.
  • Muestra un buen rendimiento tanto cuando los gráficos son estáticos (es decir, buscando, buscando, iterando con y sin filtros, etc.).
  • Muestra un buen rendimiento cuando se manipulan gráficos: adiciones, eliminaciones, movimientos y actualizaciones de bordes y vértices.
  • Escala bien a gráficos grandes, pero no necesariamente enormes , que son sobrios en lugar de densos , digamos, decenas de miles de vértices y cientos de miles de bordes.
  • No se resiste a grados de vértice muy no uniformes.
  • Amigable hacia el enriquecimiento de bordes y vértices con semántica adicional (sí, nuevamente, siendo vago aquí para no descartar respuestas de antemano).
  • Gratis y de código abierto .
  • Está escrito en C++ 11 y versiones posteriores... ¿sabes qué? OK, no es un requisito estricto, pero estaría muy sesgado hacia eso.

También sería bueno si también:

  • Escala bien a gráficos enormes.
  • Funciona bien en gráficos dispersos y densos.
  • Le permite configurar su representación subyacente a sus objetivos de rendimiento.
  • No es una de esas cosas que malloc() es como si no hubiera un mañana y te deja atrapado en un laberinto de punteros molestos.
  • Tiene una licencia no tan viral.
  • Se mantiene activamente.
  • Está bien documentado.
  • Es de amplio uso.
También hay dlib
@Antony: No creo que eso cumpla con todos mis criterios...
Lo siento, temía tanto cuando publiqué un comentario en lugar de una respuesta. He usado un poco la biblioteca de gráficos de Boost, así que siento tu dolor :-(

Respuestas (2)

Algunos candidatos potenciales, o próximos a ser candidatos:

Podría ser relevante:

  • LEMON , o L ibrary for Efficient M odeling and O ptimization in R etworks : una "biblioteca de plantillas de C++ que proporciona implementaciones eficientes de estructuras de datos y algoritmos comunes con un enfoque en tareas de optimización combinatoria relacionadas principalmente con gráficos y redes". Aquí hay una presentación de 2010 que describe a LEMON.
  • GGL , la biblioteca de gramática gráfica - . Aquí está el manual .
  • Goblin : "Una cadena de herramientas para manejar gráficos", que incluye código para algoritmos de optimización combinatoria relacionados con gráficos; disposición de gráficos en el espacio (por ejemplo, en capas, ortogonales), composición de gráficos (?), serialización hacia/desde archivos, atributos de vértice y borde y estructuras de incidencia. Probablemente no sea C ++ 11ish ni involucre demasiado plantillas.
  • SNAP - La plataforma de análisis de redes de S tanford - por un lado, parece estar bastante enfocada en una aplicación específica; por otro lado, podría tener una API de manipulación y representación gráfica bastante completa. También hay una pista de que podría estar basado en otra biblioteca de gráficos de nivel inferior.
  • NGraph : una biblioteca gráfica de archivos .hpp de 23 KiB súper simple y única.
  • digraph : una biblioteca de C++ 11 para dígrafos, diseñada para su uso como parte del compilador de procesamiento de señales de audio Faust .

No relevante / no muy relevante:

  • LEDA : una parte de una base de código más grande de algoritmos combinatorios y estructuras de datos del mismo nombre. Este es un software comercial, e incluso la edición gratuita es de código cerrado (puedes, jadear, comprarles la fuente). No gracias.
  • OGDF - Marco de dibujo de gráfico abierto - Parece estar más relacionado con el diseño, el dibujo de gráficos en un plano. Afirma ser un sustituto de FOSS para LEDA.
  • igraph : biblioteca de gráficos AC (como en: no C++) creada para su uso en el análisis de redes. Afirma centrarse en el rendimiento de gráficos grandes pero no enormes; y parece haber experimentado un desarrollo significativo durante más de una década. Página de GitHub . Tiene algunos enlaces de API C++ inestables llamados igraphpp.
  • NoCycle : una biblioteca para la representación de DAG. Utiliza una representación compacta (?) de un mapa de adyacencia. Probablemente demasiado diferente de lo que necesito, y no creo que "compre" la exageración sobre su representación.
  • libcgraph - Parte del proyecto/juego de herramientas de diseño de gráficos GraphViz . Tenga en cuenta que también hay un componente llamado libgraph allí, no estoy seguro de cuál usa cuál.
  • GCT - Plantillas de clase de gráfico : otra biblioteca básica de un archivo de encabezado.

No es imposible que algunas de las bibliotecas de C sean buenas, pero no creo que vaya a perder tiempo envolviéndolas en C++, sin mencionar la escasez de abstracciones que estarían efectivamente disponibles con ellas.

Consulte también las siguientes preguntas de desbordamiento de pila:

Existe un proyecto muy serio de escribir una biblioteca de gráficos basada en plantillas, con reconocimiento de rango, como una propuesta para agregar al estándar C++. Mejora y amplía las ideas de Boost Graph, utilizando instalaciones y mecanismos modernos de C++ (incluido el uso extensivo de rangos).

No está en un estado finalizado, pero se puede encontrar aquí: https://github.com/pratzl/graph

Y la propuesta es P1709R2 .

Una biblioteca moderna (más o menos) de representación gráfica y manipulación de C++
RespuestasAquíPolítica de privacidad1y, 0v