Stop boost :: depth_first_search a lo largo de una profundidad particular si se cumplen ciertos criterios

Question

Estoy usando BGL para almacenar mi DAG. Los vértices tienen estados. Dado un cambio de estado en uno de los vértices quiero actualizar los vértices dependientes. Esto puedo hacer usando boost :: depth_first_search y un visitante personalizado.

Ahora la lógica es que no quiero actualizar un vértice buscado y es dependiente si el vértice está en un estado particular. Básicamente, quiero controlar la puesta en cola de vértices en dfs o bfs. ¿Cuál es la mejor manera de lograr esto en BGL?

Gracias.

Answer 1

Parece que boost :: depth_first_search no es compatible con esto, pero el boost subyacente :: depth_first_visit lo hace, a través de su segunda sobrecarga, lo que permite una "función de terminación" (TerminatorFunc).

Para poder copiar la implementación de boost :: depth_first_search y sustituir el parámetro detail :: nontruth2() pasado a boost :: depth_first_visit con su propia función de terminador (no trivial).

Answer 2

La falta de terminación en la búsqueda de profundidad en primer lugar es la cosa más estúpida en la biblioteca de gráficos que he visto.

Puede ser, esta puede ser la salida: depth_first_search en filtered_graph. Puede marcar el stop-vértice de alguna manera, y en la función filter-edges de filtered_graph simplemente oculte los bordes del incidente