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

Question

是否有一个C++（或任何其他语言）库与算法的投资组合graph coloring的问题？

当然也有天真的贪婪顶点着色算法，但我很感兴趣，喜欢更有趣的算法：那拿wiki

逼近算法的“精确算法”一节中提到

1. 算法优点的像图形是planar或unit disk graph特殊图形属性。
2. 算法，找到一个图的fractional coloring。

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

我到目前为止发现的是this page的列表，但他们都没有任何上述算法。此外，最好的一个是Joe Culberson's Graph Coloring code，并且在90年代后期实现的，所以在没有文档化的API而言非常过时的（不，这是对这个问题是什么重要的，但我想我会提到它） 。

有Koala graph coloring library有我正在寻找的精神，但如果你看看他们的source code它还没有兑现承诺。它似乎处于发展的非常早期阶段。

其他通用图库在this stackoverflow question中提及。它们包括：

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

我要指出，我用的是Boost Graph Library了很多东西。事实上，它提供了一个天真的顶点着色实现。乔Culberson的代码（上面提到）做了更多。

以下是图表着色代码的列表，我已经发现（并在大多数情况下进行了测试），但它们在上述三种算法类别中仍然大部分不足。

1. GraphCol - 文档不是英文，叹气。
2. Planarity - 包含保证了5着色或更好地为平面图着色算法。
3. Graph-Coloring - 似乎是由Joe Culberson（以上）实施的少数算法的重新实现。

Answer 1

也许你可以帮助自己Boost Graph Library。