È possibile modificare la condizione di interruzione della prima ricerca in BGL?

Question

Sono nuovo in BGL (Boost Graph Library). Sto imparando l'interfaccia breadth_first_search e sembra a portata di mano. Tuttavia, nella mia applicazione, ho bisogno di tagliare il breadth_first_search quando si incontrano altre condizioni di terminazione come il conteggio del nodo dello spazio di ricerca che incontra il massimo.

Posso aggiungere una nuova condizione di terminazione con BFSVisitors o c'è qualche altro trucco?

Grazie!

Answer 1

In seguito (un po 'in ritardo) sul commento @yuyoyuppe, è possibile creare un visitatore proxy che eseguirà il wrapping di un visitatore effettivo e il lancio quando viene raggiunto un determinato predicato. L'implementazione che ho scelto di affrontare offre la possibilità di eseguire predicati su discover_vertex e examine_edge. Per prima cosa definiamo un predicato predefinito che restituisce sempre falso:

namespace details { 

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

Quindi, il modello stesso.

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

Ci vorranno 3 modelli argomenti:

1. Un predicato vertice applicato a ogni chiamata a discover_vertex (al massimo una volta per vertice)
2. un predicato bordo, applicato a ogni chiamata a examine_edge (al massimo una volta per spigolo)
3. Un'attuale implementazione del visitatore da cui erediteremo

Per costruirla, abbiamo semplicemente inizializzare il visitatore di base e le nostre due predicati:

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

Poi, dobbiamo fare una funzione di proxy (privato) per eseguire la chiamata appropriata per l'implementazione di base e verifichiamo il predicato:

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

Certo, ho usato pigramente std::runtime_error ma si dovrebbe definire il proprio tipo di eccezione, derivato da std::exception o qualunque classe di eccezioni di base che si usa.

Ora possiamo definire facilmente i nostri due funzioni di callback:

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

Verificheremo la nostra struttura in un predicato vertex personalizzato che restituisce true sulla scoperta della N-esimo vertice.

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

Per eseguire le BFS su un determinato grafico, sarà facile:

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

Un live demo on Coliru è a disposizione per aiutarvi a vedere tutti i pezzi in azione.