Почему BGL A* требует неявного графа для моделирования VertexListGraph?

Более конкретный дополнительный вопрос к моему предыдущему BGL Внутренние свойства для неявного графа

В Boost BGL есть версия алгоритма A*, которая должна работать с неявными графами, а именно функция astar_search_no_init(). Неявные графы можно смоделировать как IncidenceGraphs. В документации A* говорится: "Пожалуйста, обратите внимание, что astar_search_no_init() должен использоваться для неявных графов; для базовой функции astar_search() требуется граф, моделирующий концепцию графа списка вершин. Обе версии также требуют, чтобы тип графа моделировал концепцию графа заболеваемости».

Не означает ли это, что граф не должен моделировать концепцию графа со списком вершин? Если это так, я что-то упускаю, так как не могу найти ни одной версии функции astar_search_no_init(), которая использовала бы IncidenceGraphs? Доступны две версии astar_search_no_init(), и обе они, кажется, работают с VertexListGraphs. Я использую Boost 1.48, а A* находится в файле astar_search.hpp.

Я не вижу смысла вообще требовать неявного графа для моделирования графа списка вершин. Документация довольно запутанная и вводит меня в заблуждение. Любые идеи?


c++ boost graph a-star boost-graph
person Juho    schedule 29.12.2011    source источник
comment
Вы имели в виду две версии astar_search_no_init(), и обе они работают только с VertexListGraphs? Эти две концепции по существу ортогональны, поэтому неудивительно, что существуют VertexListGraph, которые также являются IncidenceGraphs.   -  person MSalters    schedule 29.12.2011
comment
@MSalters Да, это то, что я имел в виду. Оба они, кажется, работают только с VertexListGraphs. (Формальные) имена в .hpp по крайней мере противоречат друг другу и, таким образом, вводят в заблуждение документацию, но я скоро попробую!   -  person Juho    schedule 29.12.2011

Ответы (2)


arrow_upward
2
arrow_downward

Поддержка неявных графов была добавлена ​​в r50803 27 января 2009 г., чтобы исправить Ошибка №829. Исправление заключалось в том, чтобы не полагаться на num_vertices или использовать какие-либо другие требования к типам графов, моделирующим VertexListGraph.

Таким образом, несмотря на то, что параметр типа шаблона называется VertexListGraph, он должен работать только с типами графиков, которые моделируют только IncidenceGraph.

person Daniel Trebbien    schedule 29.12.2011

arrow_upward
2
arrow_downward

Понятия графа упорядочены сами по себе; вот хороший график концепций графа;)

Концепции ускоренного графа

Как видите, тот факт, что концепция Incidence Graph, требуемая astar_search_no_init(), не связана с концепцией Vertex List Graph. т.е. каждая концепция может быть смоделирована независимо. Итак, вашему графику достаточно моделировать только первую концепцию.

Обратите внимание, что неправильно использовать только модель Vertex List Graph для astar_search_no_init(), даже если может показаться, что это работает. Концепция Vertex List Graph не является частным случаем Incidence Graph. было бы нормально использовать модель Bidirectional Graph; это частный случай графика заболеваемости`

person MSalters    schedule 29.12.2011
comment
Верно, как я и подозревал. Тем не менее, это не отвечает на главный вопрос: почему все функции astar_search_no_init(), представленные в astar_search.hpp, требуют VertexListGraph? В документации сказано, что есть версия, работающая с IncidenceGraphs, и это имело бы смысл, но я не вижу ни одной. - person Juho; 29.12.2011
comment
Файл можно увидеть здесь - person Juho; 29.12.2011
comment
Я вижу inline void astar_search_no_init(const IncidenceGraph &g, ... задокументировано - разве это не то, что вы ищете? Не обращайте внимания на (формальные) имена в файле .hpp, это просто реализация. - person MSalters; 29.12.2011