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