C++图形顶点着色库或源代码

Question

是否有一个C++(或任何其他语言)库,其中包含用于图着色问题的算法组合？

当然有天真贪婪的顶点着色算法,但我对更有趣的算法感兴趣,如:

1. 维基的"精确算法"部分中提到的算法
2. 利用特殊图形属性的近似算法,如平面图或单位磁盘图.
3. 找到图的分数着色的算法.

最后一个对我来说特别重要.

到目前为止我发现的是此页面上的列表,但没有一个具有上述任何算法.此外,最好的一个是Joe Culberson的图形着色代码并且是在90年代后期实现的,所以在没有文档化API的情况下已经过时了(不是这对于这个问题的重要性,但我认为我'提到它).

还有的考拉图着色库有什么我要找的精神,但如果你看看他们的源代码,它并没有在承诺交付,只是还没有.它似乎处于发展的早期阶段.

此stackoverflow问题中提到了其他常规图库.他们包括:

1. 的Graphviz
2. 提升图库
3. 柠檬
4. IGRAPH
5. OGDF

我应该注意到我使用Boost Graph Library做了很多事情.实际上,它提供了一个天真的顶点着色实现.Joe Culberson的代码(如上所述)做得更多.

以下是图形着色代码的列表,我发现(并在大多数情况下进行了测试),但它们在上述三种算法类别方面仍然大部分都不足.

1. GraphCol - 文档不是英文,叹气.
2. 平面性 - 包含着色算法,可确保平面图的5色或更好.
3. 图形着色 - 似乎是Joe Culberson已经实现的少量算法的重新实现(上图).

Answer 1

也许您可以使用Boost Graph Library来帮助自己。