C ++ Graph Vertex Coloring Bibliothek oder Quellcode

Gibt es eine Bibliothek in C ++ (oder einer anderen Sprache) mit einem Portfolio von Algorithmen für das Problem der Farbgebung von Grafiken ?

Es gibt natürlich naive Greedy Vertex Coloring-Algorithmen, aber ich interessiere mich für interessantere Algorithmen wie:

1. Algorithmen, die im Abschnitt "Exakte Algorithmen" des Wikis erwähnt werden
2. Approximationsalgorithmen, die spezielle Grapheigenschaften nutzen, wie der Graph planar oder ein Einheit des Festplattengraphen .
3. Algorithmen, die die fraktale Einfärbung eines Graphen finden.

Letzteres ist mir besonders wichtig.

Was ich bisher gefunden habe, ist die Liste auf dieser Seite , aber keiner davon Sie haben einen der obigen Algorithmen. Darüber hinaus ist der beste Joe Culberson Graph Coloring Code und das wurde in den späten 90er Jahren implementiert, so ist es sehr viel veraltet, weil es keine dokumentierte API gibt (nicht dass dies für das, worum es in dieser Frage geht, wichtig ist, aber ich dachte, ich würde es erwähnen).

Es gibt die Koala-Grafik-Farbbibliothek , die den Geist dessen hat, wonach ich suche , aber wenn Sie sich ihren Quellcode ansehen, hat er das Versprechen noch nicht erfüllt. Es scheint sich in sehr frühen Entwicklungsstadien zu befinden.

Andere allgemeine Diagrammbibliotheken werden in dieser Stapelüberlauffrage erwähnt. Dazu gehören:

1. Graphviz
2. Boost Graph Library
3. Zitrone
4. igra्a>ph
5. OGDF

Ich sollte beachten, dass ich die Boost Graph Library dafür nutze viele Dinge. In der Tat bietet es eine naive Vertex Coloring-Implementierung. Joe Culberson's Code (oben erwähnt) macht viel mehr.

Das Folgende ist eine Liste von Graphen-Malcodes, die ich gefunden habe (und in den meisten Fällen getestet habe), aber sie sind immer noch in Bezug auf die drei oben genannten Algorithmusklassen zu kurz.

1. GraphCol - Dokumentation ist nicht auf Englisch, seufz.
2. Planarität - enthält einen Farbalgorithmus, der eine 5-Färbung oder besser für planare Graphen garantiert.
3. Graph-Coloring - scheint eine Re-Implementierung einer kleinen Anzahl von Algorithmen zu sein, die bereits von Joe Culberson implementiert wurden ( oben).