Существует ли библиотека C ++ (или любого другого языка) с набором алгоритмов для задачи раскраски графов ?
Конечно, существуют наивные жадные алгоритмы раскраски вершин, но яМеня интересуют более интересные алгоритмы, такие как:
- Алгоритмы, упомянутые в разделе «Точные алгоритмы» wiki
- Алгоритмы аппроксимации, использующие преимущества специального графатакие свойства, как граф планарный или граф единичных дисков .
- Алгоритмы, которые находят дробную раскраску графа.
Этот последний имеет для меня особое значение.
На данный момент я нашел список на этой странице , но ни один из них не имеет ни одного из вышеперечисленных алгоритмов.Более того, лучшим из них является код раскраски графиков Джо Калберсона , который был реализован в конце 90-х годов, поэтому он очень устарел с точки зрения отсутствия документированного API (не то, что это важно для того, о чем этот вопрос, но я подумал, что упомяну это).
Есть библиотека раскрасок графа Коала , которая имеет дух того, что я ищу, но если вы посмотрите на их исходный код он еще не выполнил обещание.Похоже, что он находится на очень ранних стадиях разработки.
Другие общие библиотеки графов упоминаются в этом вопросе о стекопереработке .Они включают в себя:
- Graphviz
- Boost Graph Library
- Лимон
- igraph
- OGDF
Следует отметить, что я использую Boost Graph Library длямного вещей.Фактически, это обеспечивает наивную реализацию раскраски вершин.Код Джо Калберсона (упомянутый выше) делает гораздо больше.
Ниже приведен список кода раскраски графов, который я обнаружил (и тестировал в большинстве случаев), но он все еще в основном не соответствует требованиям трех алгоритмов.классы выше.
- GraphCol - документация не на английском языке, вздох.
- Planarity - содержит алгоритм раскраски, который гарантирует 5-краска или лучше для плоских графов.
- Color-Coloring - представляется повторной реализацией небольшого числа алгоритмов, уже реализованных Джо Калберсоном (см. выше).