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

Question

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

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

Спасибо.

Answer 1

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

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

Answer 2

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

Может быть, это может быть выходом: deep_first_search на Filter_graph. Вы можете пометить стоп-вершину как-нибудь, а в функции filter-ребра filter_graph просто скрыть падающие ребра