Остановить boost::depth_first_search на определенной глубине, если выполняются определенные критерии

Я использую BGL для хранения своей DAG. Вершины имеют состояния. Учитывая изменение состояния в одной из вершин, я хочу обновить зависимые вершины. Это я могу сделать с помощью boost::depth_first_search и пользовательского посетителя.

Теперь логика заключается в том, что я не хочу обновлять искомую вершину и ее зависимость, если вершина находится в определенном состоянии. В основном я хочу контролировать постановку в очередь вершин либо в dfs, либо в bfs. Каков наилучший способ добиться этого в BGL.

Спасибо.


c++ boost graph depth-first-search boost-graph
person Vikas    schedule 17.01.2011    source источник

Ответы (2)


arrow_upward
9
arrow_downward

Кажется, что boost::depth_first_search не поддерживает это, но базовый boost::depth_first_visit поддерживает благодаря своей второй перегрузке, позволяющей использовать «функцию терминатора» (TerminatorFunc).

Таким образом, вы можете скопировать реализацию boost::depth_first_search и заменить параметр detail::nontruth2(), переданный в boost::depth_first_visit, своей собственной (нетривиальной) функцией терминатора.

person Daniel Gehriger    schedule 17.01.2011

arrow_upward
0
arrow_downward

Отсутствие терминации в поиске в глубину - самая глупая вещь в библиотеке графов, которую я когда-либо видел.

Может быть, это выход: depth_first_search на filtered_graph. Вы можете как-то пометить стоп-вершину, а в функции filter-edges filtered_graph просто скрыть инцидентные ребра

person al.zatv    schedule 15.02.2011