C++ Graph Vertex Coloring Library o código fuente

Question

¿Existe una biblioteca C++ (o cualquier otro idioma) con una cartera de algoritmos para el problema de graph coloring?

Por supuesto, hay ingenuos que colorean los algoritmos codiciosos vértice, pero estoy interesado en algoritmos más interesantes como:

1. algoritmos mencionados en la sección "algoritmos exactos" de los wiki
2. algoritmos de aproximación que tienen ventaja de las propiedades especiales del gráfico como el gráfico que es planar o unit disk graph.
3. Algoritmos que encuentran el fractional coloring de un gráfico.

Este último es de particular importancia para mí.

Lo que encontré hasta ahora es la lista en this page pero ninguno de ellos tiene ninguno de los algoritmos anteriores. Además, el mejor es Joe Culberson's Graph Coloring code y que se implementó a finales de los 90, por lo que está muy desactualizado en términos de no tener una API documentada (aunque no es importante para lo que se trata esta pregunta, pero pensé que lo mencionaría) .

Ahí está el Koala graph coloring library que tiene el espíritu de lo que estoy buscando, pero si nos fijamos en su source code aún no ha cumplido la promesa. Parece estar en etapas muy tempranas de desarrollo.

Otras bibliotecas de gráficos generales se mencionan en this stackoverflow question. Ellos incluyen:

1. Graphviz
2. Boost Graph Library
3. Lemon
4. igraph
5. OGDF

Debo señalar que utilizo el Boost Graph Library para un montón de cosas. De hecho, proporciona una implementación ingenua de coloreo de vértices. El código de Joe Culberson (mencionado anteriormente) hace mucho más.

La siguiente es una lista de códigos para colorear gráficos, que encontré (y probé en la mayoría de los casos), pero todavía son insuficientes en términos de las tres clases de algoritmo anteriores.

1. GraphCol - la documentación no está en inglés, suspiro.
2. Planarity - contiene un algoritmo de coloración que garantiza un 5-color o mejor para gráficos planos.
3. Graph-Coloring - parece ser una reimplementación de un pequeño número de algoritmos ya implementados por Joe Culberson (arriba).

Answer 1

Quizás pueda ayudarse a sí mismo con el Boost Graph Library.