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

Question

是否有 C++(或任何其他语言)库，其中包含针对 graph coloring 问题的算法组合？

当然有朴素的贪心顶点着色算法，但我对更有趣的算法感兴趣，例如:

1. wiki 的“精确算法”部分提到的算法
2. 利用特殊图属性的近似算法，例如图 planar或 unit disk graph .
3. 找到 fractional coloring 的算法的图表。

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

到目前为止我找到的是 this page 上的列表但他们都没有上述任何算法。而且，最好的是Joe Culberson's Graph Coloring code它是在 90 年代后期实现的，因此在没有记录的 API 方面已经非常过时了(并不是说这对于这个问题的内容很重要，但我想我会提到它)。

有 Koala graph coloring library这具有我正在寻找的精神，但如果你看看他们的 source code它尚未兑现 promise 。它似乎处于非常早期的开发阶段。

this stackoverflow question中提到了其他通用图形库.它们包括:

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

我应该注意到我使用了 Boost Graph Library对于很多事情。事实上，它提供了一个朴素的顶点着色实现。 Joe Culberson 的代码(上面提到的)做得更多。

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

1. GraphCol - 文件不是英文的，唉。
2. Planarity - 包含一个着色算法，保证平面图的 5 着色或更好。
3. Graph-Coloring - 似乎是对 Joe Culberson(上文)已经实现的少量算法的重新实现。

Answer 1

http://rhydlewis.eu/gcol/ 有一些不错的.这些对应于我书中审查和测试的算法组合:

Lewis, R.(2021 年)图形着色指南:算法和应用(第二版)。施普林格。国际标准书号:978-3-030-81053-5。 https://link.springer.com/book/10.1007/978-3-030-81054-2

这些包括贪婪、回溯和元启发式方法。我在上面的链接中包含了编译说明等。