是否有 C++(或任何其他语言)库,其中包含针对 graph coloring 问题的算法组合?
当然有朴素的贪心顶点着色算法,但我对更有趣的算法感兴趣,例如:
- wiki 的“精确算法”部分提到的算法
- 利用特殊图属性的近似算法,例如图 planar或 unit disk graph .
- 找到 fractional coloring 的算法的图表。
最后一个对我来说特别重要。
到目前为止我找到的是 this page 上的列表但他们都没有上述任何算法。而且,最好的是Joe Culberson's Graph Coloring code它是在 90 年代后期实现的,因此在没有记录的 API 方面已经非常过时了(并不是说这对于这个问题的内容很重要,但我想我会提到它)。
有 Koala graph coloring library这具有我正在寻找的精神,但如果你看看他们的 source code它尚未兑现 promise 。它似乎处于非常早期的开发阶段。
this stackoverflow question中提到了其他通用图形库.它们包括:
我应该注意到我使用了 Boost Graph Library对于很多事情。事实上,它提供了一个朴素的顶点着色实现。 Joe Culberson 的代码(上面提到的)做得更多。
以下是我发现(并在大多数情况下进行了测试)的图形着色代码列表,但它们在上述三个算法类方面仍然大部分不足。
- GraphCol - 文件不是英文的,唉。
- Planarity - 包含一个着色算法,保证平面图的 5 着色或更好。
- Graph-Coloring - 似乎是对 Joe Culberson(上文)已经实现的少量算法的重新实现。
最佳答案
http://rhydlewis.eu/gcol/ 有一些不错的.这些对应于我书中审查和测试的算法组合:
Lewis, R.(2021 年)图形着色指南:算法和应用(第二版)。施普林格。国际标准书号:978-3-030-81053-5。 https://link.springer.com/book/10.1007/978-3-030-81054-2
这些包括贪婪、回溯和元启发式方法。我在上面的链接中包含了编译说明等。
关于C++ 图顶点着色库或源代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5459347/