Статья, первая часть которой здесь представлена, содержит различные соображения автора, накопившиеся в ходе длительной разработки специализированной системы поиска социальных связей, базирующейся на библиотеке Boost Graph Library (BGL). В этом (техническом) разделе суммируются впечатления автора от работы с этой библиотекой, поднимаются вопросы инструментовки при создании графовых приложений и затрагиваются некоторые практические проблемы метапрограммирования на C++.
Читать полностью »
Рубрика «boost.graph»
Маскируем класс под граф Boost. Часть 3: Находим путь
2014-02-17 в 11:20, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Часть 2: Завершаем реализацию поддержки концепций
В прошлых статьях цикла описывался процесс адаптации класса клеточного игрового поля под концепции графов boost. Сейчас рассмотрим собственно то, ради чего все затевалось — поиск пути на клеточном поле. Реализация поиска boost позволяет достаточно тонко настраивать алгоритм, в этой статье будет приведет только один пример такой параметризации — возможность задавать различную длину ребер графа.
Читать полностью »
Маскируем класс под граф Boost. Часть 2: Завершаем реализацию поддержки концепций
2014-02-10 в 22:34, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Пролог: Концепции Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс исходного класса
Кратко напомню задачу. Есть двумерное игровое поле из клеток, часть из которых свободна, а часть занята. Требуется найти путь по свободным клеткам из одной позиции поля в другую. Алгоритм поиска пути реализован в Boost. Но он требует, чтобы наше поле подходило под определение графа. Точнее класс должен удовлетворять двум концепциям — boost::VertexListGraph и boost:: IncidenceGraph. При этом интерфейс игрового поля менять не хочется — для всего остального проекта это не граф и графом никогда не станет.
В прошлой части было рассмотрено подключение внешних ассоциированных типов, необходимых для интерпретации класса как boost-графа. Конечно, одних типов недостаточно. Также требуется реализовать несколько функций с заданной сигнатурой и итераторов, с помощью которых библиотека сможет манипулировать игровым полем как графом.
Читать полностью »
Маскируем класс под граф Boost. Часть 1: Не трогаем интерфейс
2014-02-06 в 9:27, admin, рубрики: astar, boost, boost.graph, c++, graph_traits, граф, кратчайший путь, поиск пути, Программирование, метки: astar, boost, boost.graph, graph_traits, граф, кратчайший путь, поиск пути 
Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «найди функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную гибкость использования, что негативно сказалось на простоте. В то же время и ничего смертельного — все лучше, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться желания не было, в то время как boost в проекте используется давно…
Читать полностью »