Как подогнать пользовательский график к шаблону библиотеки графов повышения?

Я ржавый на шаблонах С++ и использую библиотеку графов повышения (фатальная комбинация). Я искал в Интернете и не могу найти никаких прямых инструкций о том, как взять пользовательскую структуру графа и подогнать ее под BGL (библиотека графов повышения), чтобы я мог использовать алгоритмы обхода графов повышения. Кто-нибудь достаточно знаком с библиотекой, чтобы помочь мне?

РЕДАКТИРОВАТЬ: Итак, основная проблема, с которой я столкнулся, заключается в том, где найти источник, в котором указаны общие требования для сопоставления произвольного графа с графом BGL. Я действительно новичок в шаблонах, поэтому мне трудно читать спецификацию/примеры BGL. Может стоит поискать общий источник по шаблонам?


c++ templates graph data-structures boost-graph
person Michael    schedule 14.06.2010    source источник
comment
Было бы полезно, если бы мы могли увидеть пример того, как выглядит ваша пользовательская структура графика.   -  person deft_code    schedule 14.06.2010

Ответы (2)


arrow_upward
6
arrow_downward

Я бы предложил полностью отказаться от использования BGL, если только у вас уже нет значительного объема кода, написанного поверх него. Недавно я тестировал его для будущего использования в большом проекте анализа графов и обнаружил, что его почти невозможно использовать из-за слишком сложного и плохо спроектированного API.

В BGL нет простых задач, есть только сложные, и я постоянно боролся с компилятором из-за чрезмерно сложной иерархии шаблонов, которая есть в BGL. Практически полное отсутствие полезной документации (по крайней мере, там, где она действительно необходима) и недостаточное количество примеров только усугубляют ситуацию. Это не способ написать код.

Я бы рекомендовал перейти на LEMON. Он стабилен, написан на C++, прост для понимания и написания кода, предлагает несколько специализированных форм графиков для поддержки различных потребностей использования и поддерживает функции поиска/посетителя BFS и DFS. У него также есть собственный эквивалент карт свойств для узлов/ребер, так что вы должны быть в состоянии вписать в него свою собственную структуру графа и другие данные.

Попробуйте ЛИМОН; на вкус намного лучше и вызовет меньше язв. ;-)

person Joel Hoff    schedule 15.06.2010
comment
Я только что закончил тестирование LEMON на графе с 1 миллионом узлов и 100 миллионами ребер; хорошо масштабируется без проблем с производительностью и т. д. - person Joel Hoff; 16.06.2010
comment
Спасибо за идею! К сожалению, я работаю с БОЛЬШОЙ кодовой базой, и я не думаю, что мои боссы хотят еще одну зависимость: S - person Michael; 16.06.2010
comment
О, и приятно слышать, что я не единственный, кто думает, что BGL чрезвычайно сложен и слишком универсален, и что примеры не особенно показательны! - person Michael; 16.06.2010
comment
Рад слышать, что я не единственный, кто считает, что BGL может быть чрезмерно сложным - посмотрю на LEMON-ty! - person kfmfe04; 27.01.2013

arrow_upward
5
arrow_downward

Подход, насколько я понимаю, состоит в том, чтобы специализировать структуру boost::graph_traits для вашего типа графика. Это настраивает BGL с различными важными свойствами, которые необходимо знать о вашем графике. Затем вы специфицируете глобальные шаблонные функции для специализированного типа вашего графа graph_traits, чтобы реализовать любые интерфейсы повышающего графа, которые могут применяться к вашему конкретному типу графа.

Пример есть прямо в документации BGL:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/leda_conversion.html

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

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html

person Owen S.    schedule 14.06.2010
comment
Я прочитал большую часть документации BGL, которая есть на сайте, в отношении того, как заставить работать шаблоны. Однако, если вы не знакомы с LEDA, показанный вами пример нетривиален и плохо объяснен. Если вы посмотрите на их код, то он почти полностью лишен комментариев. Каждый фрагмент кода, который я нашел на сайте графа повышения, почти полностью лишен комментариев, и для такого универсального объекта это весьма обескураживает. - person Michael; 15.06.2010
comment
Это поможет, если вы укажете конкретные вещи, которые вам не ясны, или особенности, относящиеся к вашей структуре графа, которые затрудняют адаптацию. - person Owen S.; 15.06.2010