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

Question

Более конкретный дополнительный вопрос к моему ранее 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.

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

Answer 1

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

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

Answer 2

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

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

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