Ist es möglich, die erste Abbruchbedingung in BGL zu ändern?

Question

Ich bin neu in BGL (Boost-Graph-Bibliothek). Ich lerne die breasth_first_search Schnittstelle und es sieht praktisch aus. In meiner Anwendung muss ich jedoch die breath_first_search-Funktion abbrechen, wenn eine andere Beendigungsbedingung erfüllt ist, z. B. wenn die Anzahl der Suchbereichs-Knoten das Maximum erreicht.

Kann ich eine neue Beendigungsbedingung mit den BFSVisitoren hinzufügen oder gibt es einen anderen Trick?

Danke!

Answer 1

Nach (etwas spät) auf @yuyoyuppe Kommentar, können Sie einen Proxy-Besucher, der einen tatsächlichen Besucher wickeln und werfen, wenn ein gegebenes Prädikat erfüllt ist. Die von mir gewählte Implementierung bietet Ihnen die Möglichkeit, Prädikate auf discover_vertex und examine_edge auszuführen. Zuerst definieren wir ein Prädikat Standard immer falsch Rückkehr:

namespace details { 

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

Dann wird die Vorlage selbst.

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; 
}; 

Es wird 3 templates Argument:

1. ein Scheitel Prädikat bei jedem Aufruf von discover_vertex angewandt (höchstens einmal pro Vertex)
2. eine Kante Prädikat, um examine_edge auf jeden Anruf angewandt (höchstens einmal pro Kante)
3. Eine tatsächliche Besucher Implementierung von denen wir
erben

es zu erstellen, initialisieren wir einfach die Basis Besucher und unsere zwei Prädikate:

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) {} 

Dann müssen wir eine (privat) Proxy-Funktion machen den entsprechenden Aufruf der Basisimplementierung durchzuführen und das Prädikat überprüfen:

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"); 
    } 
} 

natürlich habe ich faul std::runtime_error aber Sie sollten Ihren eigenen Exception-Typen, abgeleitet von std::exception oder was auch immer Basisausnahmeklasse Sie verwenden definieren.

Jetzt können wir einfach unsere zwei Rückrufe definieren:

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)); 
} 

Wir haben unsere Anlage auf einem benutzerdefinierten Vertex Prädikat testen, die auf die Entdeckung des N-ten Eckpunkt true zurückgibt.

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; 
}; 

Um die bfs auf einem gegebenen Graphen ausführen, wird es leicht sein:

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; 
} 

A live demo on Coliru ist verfügbar Sie alle Teile in Aktion zu helfen.