LEDA graph v/s Boost Graph библиотека
Я хочу эффективности, и я готов писать код самостоятельно, если эффективность (=0,9* скорость + 0,1* другие) высока. Если бы мне пришлось выбирать между графиком LEDA или графиком Boost, какой выбрать?
Мои алгоритмы отнимают много времени (некоторые даже не являются полиномиальными по времени) и работают на больших графах.
3 ответа
Boost, как правило, хорошая библиотека, но я бы не стал предлагать график Boost по ряду причин.
Документация BGL является выполнимой, без простого руководства пользователя. Я обнаружил, что попытаться определить графики со свойствами, которые имеют отношение к моим собственным проблемам, очень сложно.
Вы часто сталкиваетесь с огромными ошибками компилятора, которые показывают шаблоны в шаблонах внутри шаблонов... почти невозможно увидеть, что происходит.
Единственное решение, которое я нашел, было начать с тривиального примера, который идет с Boost Graph, и адаптировать его, пока он не сделает то, что я хочу.
Я знаю многих ярких и способных людей, которые отказались от Boost Graph по этим причинам. Печально, потому что под всем этим есть очень эффективные алгоритмы. Для меня BGL - пример использования шаблона в учебниках. Boost Graph - отличная идея, которая терпит неудачу из-за полного упущения: код бесполезен, если его невозможно прочитать, поддерживать, расширять или отлаживать.
Существуют альтернативы реализации LEDA/Boost. Вы могли бы сделать хуже, чем исследовать эту похожую публикацию: https://stackru.com/questions/510758/can-you-suggest-a-good-book-on-graphs-and-graph-algorithms (ссылка больше не действительна)
Повышение постоянно подвергается рефакторингу, поэтому его части переводятся в стандарт, после чего поставщики продолжают оптимизировать его для целевых систем, которые они поддерживают. В редких сценариях использования, используя наследование, разработчик может настроить некоторую часть для конкретного случая.
Если работа ограничена C++, то, поскольку части Boost стремятся интегрироваться в стандарт, у него есть эти преимущества. Там может быть конкретная причина использовать проприетарную LEDA, например, гарантированно без ошибок при тестировании, тогда, как лицо, принимающее решение, только вы должны соблюдать такие критерии.
Алгоритмы повышения графов могут быть созданы для работы с LEDA и даже графами Стэнфорда, но не наоборот. http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/leda_conversion.html
Я бы предложил использовать буст-график, это современный уровень техники.
Майк