Современная библиотека представления графов и манипулирования C++.

На моем старом рабочем месте у меня был смешанный опыт работы с графической библиотекой Boost ; Я не был тем человеком, который работал с этим кодом в основном, но мы столкнулись с хрупкостью, вещами, меняющимися под нашими ногами, и необходимостью неоднократно обновлять состояние по не очень хорошим причинам. Да, я знаю, это звучит немного расплывчато, но дело в том, что я хочу проверить альтернативы.

Итак, я ищу графическую библиотеку, которая:

  • Представляет неориентированные и ориентированные графы.
  • От Boost не зависит вообще или, по крайней мере, незначительно.
  • Демонстрирует хорошую производительность, когда графики являются статическими (т. е. поиск, поиск, итерация с фильтрами и без них и т. д.).
  • Демонстрирует хорошую производительность при манипулировании графами — добавлении ребер и вершин, удалении, перемещении и обновлении.
  • Хорошо масштабируется до больших, но не обязательно огромных графов, которые являются скорее разреженными, чем плотными — скажем, с десятками тысяч вершин и сотнями тысяч ребер.
  • Не препятствует очень неоднородным степеням вершин.
  • Дружелюбен к обогащению рёбер и вершин дополнительной семантикой (да, опять же, здесь расплывчато, чтобы не исключать ответы заранее).
  • Бесплатный и с открытым исходным кодом .
  • Написано на C++11 и более поздних версиях... знаете что? Хорошо, не строгое требование, но я бы очень предвзято относился к ним.

Также было бы неплохо, если бы он также:

  • Хорошо масштабируется до огромных графиков.
  • Хорошо работает как на разреженном, так и на плотном графе.
  • Позволяет настроить его базовое представление в соответствии с вашими целями производительности.
  • Это не одна из тех вещей, которые malloc() как будто завтра не наступит и оставляет вас в ловушке в лабиринте надоедливых указателей.
  • Имеет не очень вирусную лицензию.
  • Активно поддерживается.
  • Хорошо документирован.
  • Имеет широкое применение.
Также есть длиб
@Antony: я не думаю, что это соответствует всем моим требованиям...
Извините, я боялся того же, когда разместил комментарий, а не ответ. Я немного использовал библиотеку Boost Graph, поэтому чувствую вашу боль :-(

Ответы (2)

Некоторые потенциальные кандидаты или близкие к кандидатам:

Может быть актуально:

  • LEMON , или библиотека для эффективного моделирования и оптимизации в сетях — «библиотека шаблонов C++, обеспечивающая эффективную реализацию общих структур данных и алгоритмов с упором на задачи комбинаторной оптимизации, связанные в основном с графами и сетями». Вот презентация 2010 года , описывающая LEMON.
  • GGL , библиотека грамматики графов — . _ Вот инструкция .
  • Goblin — «цепочка инструментов для работы с графами», включая код алгоритмов комбинаторной оптимизации, связанных с графами; расположение графов в пространстве (например, многоуровневое, ортогональное), композиция графа (?), сериализация в/из файлов, атрибуты вершин и ребер и структуры инцидентности. Вероятно , не C++11ish и не слишком много шаблонов.
  • SNAP — Стэнфордская платформа сетевого анализа — с одной стороны, кажется, что она в значительной степени ориентирована на конкретное приложение ; с другой стороны, у него может быть довольно полное представление графа и API для манипулирования. Также есть намек на то, что он может быть основан на другой графовой библиотеке более низкого уровня.
  • NGraph — сверхпростая библиотека графов с одним 23-килобайтным файлом .hpp.
  • digraph — библиотека C++11 для орграфов, предназначенная для использования в составе компилятора обработки аудиосигналов Faust .

Не актуально/не совсем актуально:

  • LEDA — часть большой кодовой базы комбинаторных алгоритмов и одноименных структур данных. Это коммерческое программное обеспечение, и даже бесплатная версия имеет закрытый исходный код (вы можете — ахнуть — купить у них исходный код). Нет, спасибо.
  • OGDF — Open G raph Drawing Framework — кажется , больше связан с компоновкой, рисованием графиков на плоскости . Утверждает, что является заменой FOSS для LEDA.
  • igraph - библиотека графов AC (как в: не C++), созданная для использования в сетевом анализе. Утверждается, что основное внимание уделяется производительности для больших, но не огромных графов; и, кажется, претерпела значительное развитие за более чем десятилетие. Страница на гитхабе . Он имеет несколько привязок C++ к нестабильному API с именем igraphpp.
  • NoCycle — библиотека для представления DAG. Он использует компактное (?) представление карты смежности. Вероятно, слишком отличается от того, что мне нужно, и я не думаю, что «покупаюсь» на шумиху по поводу его представления.
  • libcgraph — часть проекта/инструментария компоновки графа GraphViz . Обратите внимание, что там также есть компонент с именем libgraph - не уверен, какой из них использует.
  • GCT — G raph Class T emplates — еще одна базовая библиотека с одним заголовочным файлом.

Не исключено, что некоторые из библиотек C хороши, но я не думаю, что собираюсь тратить время на их обертывание в C++, не говоря уже о нехватке абстракций, которые были бы эффективно доступны с ними.

См. также следующие вопросы о переполнении стека:

Существует очень серьезный проект по написанию шаблонной библиотеки графов с учетом диапазона в качестве предложения по дополнению к стандарту C++. Он улучшает и расширяет идеи Boost Graph, используя современные средства и механизмы C++ (включая широкое использование диапазонов).

Он не в окончательном состоянии, но его можно найти здесь: https://github.com/pratzl/graph .

И предложение P1709R2 .

Современная библиотека представления графов и манипулирования C++.
СпросиСетьПолитика конфиденциальности1y, 1v