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。