Czy możliwe jest zmienienie pierwszego warunku zakończenia wyszukiwania w BGL?

Question

Jestem nowy w BGL (biblioteka wykresów doładowania). Uczę się interfejsu breadth_first_search i wygląda na przydatny. Jednak w mojej aplikacji muszę wyciąć the widthth_first_search, gdy spełnione są inne warunki zakończenia, takie jak liczba węzłów w przestrzeni wyszukiwania spełnia maksymalną wartość.

Czy mogę dodać nowy warunek zakończenia z BFSVisitors lub czy jest jakaś inna sztuczka?

Dzięki!

Answer 1

Po (trochę późno) w komentarzu @yuyoyuppe można utworzyć odwiedzającego proxy, który otoczy rzeczywistego użytkownika i rzuci po spełnieniu danego predykatu. Wdrożona przeze mnie implementacja oferuje możliwość uruchamiania predykatów na discover_vertex i examine_edge. Najpierw definiujemy domyślny predykat, zwracając zawsze wartość false:

namespace details { 

struct no_halting { 
    template <typename GraphElement, typename Graph> 
    bool operator()(GraphElement const&, Graph const&) { 
     return false; 
    } 
}; 
} // namespace details 

Następnie sam szablon.

template <typename VertexPredicate = details::no_halting, 
      typename EdgePredicate = details::no_halting, 
      typename BFSVisitor = boost::default_bfs_visitor> 
struct bfs_halting_visitor : public BFSVisitor { 
    // ... Actual implementation ... 
private: 
    VertexPredicate vpred; 
    EdgePredicate epred; 
}; 

potrwa 3 szablony argumenty:

1. orzecznika wierzchołek stosowany na każdym wywołaniu discover_vertex (co najwyżej raz na wierzchołku)
2. predykat krawędzi, stosowana na każdym wywołaniu examine_edge (co najwyżej raz na krawędzi)
3. Rzeczywista implementacja dla odwiedzających, z której będziemy dziedziczyć

ją zbudować, po prostu zainicjować użytkownik bazową i nasze dwa predykaty:

template <typename VPred, typename EPred, typename ... VisArgs> 
bfs_halting_visitor(VPred&& vpred, EPred&& epred, VisArgs&&... args) : 
        BFSVisitor(std::forward<VisArgs>(args)...), 
        vpred(vpred), epred(epred) {} 

Następnie musimy utworzyć funkcję (prywatny) proxy, aby wykonać odpowiednie wezwanie do realizacji podstawy i sprawdzić predykat:

template <typename Pred, typename R, typename ... FArgs, typename ... Args> 
void throw_on_predicate(R (BFSVisitor::*base_fct)(FArgs...), Pred&& pred, Args&&... args) { 
    bool result = pred(args...); 
    (this->*base_fct)(std::forward<Args>(args)...); 
    if (result) { 
     throw std::runtime_error("A predicate returned true"); 
    } 
} 

oczywiście, ja leniwie wykorzystywane std::runtime_error ale należy zdefiniować własny typ wyjątku, pochodzący z std::exception lub cokolwiek podstawa wyjątek klasa użyć.

Teraz możemy łatwo określić nasze dwa wywołania zwrotne:

template <typename Edge, typename Graph> 
void examine_edge(Edge&& e, Graph&& g) { 
    throw_on_predicate(&BFSVisitor::template examine_edge<Edge, Graph>, epred, 
         std::forward<Edge>(e), std::forward<Graph>(g)); 
} 

template <typename Vertex, typename Graph> 
void discover_vertex(Vertex&& v, Graph&& g) { 
    throw_on_predicate(&BFSVisitor::template discover_vertex<Vertex, Graph>, vpred, 
         std::forward<Vertex>(v), std::forward<Graph>(g)); 
} 

Będziemy testować nasz obiekt na niestandardowym wierzchołka predykat, która zwraca true odkrycia N-tego wierzchołka.

struct VertexCounter { 
    VertexCounter(std::size_t limit) : count(0), limit(limit) {} 
    VertexCounter() : VertexCounter(0) {} 

    template <typename V, typename G> 
    bool operator()(V&&, G&&) { 
     return ((++count) > limit); 
    } 
private: 
    std::size_t count; 
    std::size_t const limit; 
}; 

Aby wykonać BFS na danym wykresie, to będzie łatwe:

Graph graph = get_graph(); 
Vertex start_vertex; 
bfs_halting_visitor<VertexCounter> vis(VertexCounter(2), details::no_halting()); 
try { 
    boost::breadth_first_search(graph, start_vertex, boost::visitor(vis)); 
} catch (std::runtime_error& e) { 
    std::cout << e.what() << std::endl; 
} 

live demo on Coliru jest dostępne, aby pomóc Ci zobaczyć wszystkie kawałki w działaniu.