boost :: astar_search sur un graphe filtré

Question

J'ai besoin d'exécuter A * sur un graphe avec certaines arêtes supprimées. Pour ce faire, je construis un graphe filtré avec des bords sur liste noire et je veux lancer A * sur le graphe filtré. Les bords de la liste noire sont incorporés dans la classe BlackListEdgeConstraint, que je initialise en passant à son constructeur la liste des arêtes interdites. Ce BlackListEdgeConstraint est correctement construit, et je construis le graphique filtered avec ces contraintes. Le problème est que lorsque j'exécute A * sur le graphe filtré, un autre objet BlackListEdgeConstraint est mystérieusement construit avec un constructeur vide, et aucun bord n'est en effet sur la liste noire. Pourquoi cela se passe-t-il?

Ceci est mon code complet:

#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/filtered_graph.hpp> 
#include <boost/graph/astar_search.hpp> 
using namespace std; 

typedef std::pair<int, int> Edge; 
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, int> > graph_t; 
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor; 


struct BlackListEdgeConstraint 
{ 
private: 
    std::set<Edge> blackList; 
    graph_t* g; 

public: 

    BlackListEdgeConstraint():blackList(std::set<Edge>()),g(NULL){throw std::runtime_error("This should not be called");}; 

    BlackListEdgeConstraint(std::set<Edge>& list, graph_t* g_) : blackList(list), g(g_) 
    { 
     Edge edge = *blackList.begin(); 
     std::cout<<"The black list contains "<< edge.first<<"-"<<edge.second<<std::endl; 
    } 

    /** 
    * This is the "predicate function" used by boost::filtered_graph (
    * see http://www.boost.org/doc/libs/1_64_0/libs/graph/doc/filtered_graph.html) 
    * It it returns true, the edge is included in the filtered graph, otherwise it is excluded. 
    */ 
    bool operator()(const boost::graph_traits<graph_t>::edge_descriptor& e) const 
    { 
     Edge edge(source(e,*g), target(e,*g)); 
     std::cout<<"Should we include edge "<<source(e,*g)<<" ->"<< target(e,*g)<<" represented by a descriptor "<<e<<"? "; 
     //Include the edge if it's not in the blacklist. 
     bool include = (blackList.find(edge) == blackList.end()); 
     std::cout<<include<<std::endl; 
     return include; 
    } 
}; 

template<class GraphType> 
class MyHeuristic : public boost::astar_heuristic<GraphType, double> 
{ 
    private: 
     const GraphType* g; 

    public: 
     MyHeuristic(const GraphType* g_): g(g_) {}; 

     double operator()(vertex_descriptor v) 
     { 
      return 0; 
     } 
}; 

//Used to terminate our search 
struct GoalsReached{}; 

class MyVisitor : public boost::default_astar_visitor 
{ 
    private: 
     vertex_descriptor goal; 

    public: 
     MyVisitor(vertex_descriptor goal_): goal(goal_){}; 

     template<class GraphType> 
     void examine_vertex(vertex_descriptor u, const GraphType& g) 
     { if (u==goal) throw GoalsReached(); } 
}; 


int main() 
{ 
    Edge edge_array[] = {Edge(0,1), Edge(1,2), Edge(2,3), Edge(3,0), Edge(1,3) }; 
    int weights[] = {1,1,1,1,1}; 
    int num_arcs = sizeof(edge_array)/sizeof(Edge); 
    int num_nodes = 4; 

    // Graph created from the list of edges 
    graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); 

    // Create descriptor for the source node 
    vertex_descriptor s = vertex(0, g); 
    vertex_descriptor goal = vertex(3,g) ; 
    std::set<Edge> blacklist; blacklist.insert(Edge(1,3) ); 

    BlackListEdgeConstraint filter(blacklist, &g); 
    boost::filtered_graph<graph_t, BlackListEdgeConstraint> filtered(g, filter); 

    cout<<"filtered constructed"<<endl; 

    // Create vectors to store the predecessors (p) and the distances from the root (d) 
    std::vector<vertex_descriptor> p(num_vertices(filtered)); 
    std::vector<int> d(num_vertices(filtered)); 

    try{ 
     cout<<"Launching astar_search"<<endl; 
     boost::astar_search(filtered, s, 
       MyHeuristic<boost::filtered_graph<graph_t, BlackListEdgeConstraint>>(&filtered), 
       boost::predecessor_map(&p[0]). 
       distance_map(&d[0]). 
       visitor(MyVisitor(goal)) 
     ); 
     cout<<"astar_search launched"<<endl; 
    }catch(const GoalsReached&) 
    { // Print the path 
     std::vector<boost::graph_traits<graph_t>::vertex_descriptor > path; 
     boost::graph_traits<graph_t>::vertex_descriptor current = goal; 

     while(current!=s) 
     { 
      path.push_back(current); 
      current = p[current]; 
     } 
     path.push_back(s); 

     // Prints the path obtained in reverse 
     std::vector<boost::graph_traits<graph_t>::vertex_descriptor >::reverse_iterator it; 

     for (it = path.rbegin(); it != path.rend(); ++it) { 
      std::cout << *it << " "; 
     } 
     std::cout << std::endl; 
    } 


    return EXIT_SUCCESS; 

} 

Et voici la sortie:

The black list contains 1-3 
filtered constructed 
Launching astar_search 
terminate called after throwing an instance of 'std::runtime_error' 
    what(): This should not be called 

Ma version boost est 1,54

Answer 1

Le problème est que, quand boost :: astar_search (..) est invoqué, le constructeur vide BlackListEdgeConstraint() est appelé.

Je ne sais pas comment vous arrivez à la conclusion. Je ne peux pas reproduire que:

Live On Coliru

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/filtered_graph.hpp> 
#include <boost/graph/astar_search.hpp> 

struct VertexProperties { 
}; 

struct EdgeProperties { 
    double weight = 1; 
}; 

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperties, EdgeProperties> MyGraph; 
struct StreetDirectory { 
    using Graph = MyGraph; 
    using Edge = Graph::edge_descriptor; 
    using Vertex = Graph::vertex_descriptor; 
}; 

struct BlackListEdgeConstraint : StreetDirectory 
{ 
    private: 
     std::set<StreetDirectory::Edge> blackList; 

    public: 
     BlackListEdgeConstraint(const std::set<Edge>& list) : blackList(list) {}; 

     BlackListEdgeConstraint() 
     { 
      throw std::runtime_error("This should not be called"); 
     }; 


     bool operator()(const Edge& e) const 
     { 
      //Include the edge if it's not in the blacklist. 
      return blackList.find(e) == blackList.end(); 
     } 
}; 


int main() { 
    MyGraph graph; 

    const std::set<StreetDirectory::Edge> blacklistEdges { 
     add_edge(1,2,graph).first, 
     add_edge(1,3,graph).first, 
     add_edge(2,4,graph).first, 
    }; 
    add_edge(4,2,graph); 

    BlackListEdgeConstraint filter(blacklistEdges); 
    boost::filtered_graph<MyGraph, BlackListEdgeConstraint> filtered(graph, filter); 
    std::vector<StreetDirectory::Vertex> p(boost::num_vertices(filtered)); //Output variable 
    std::vector<double>     d(boost::num_vertices(filtered)); //Output variable 

    boost::default_astar_visitor vis; 

    boost::astar_search(
      filtered, 
      1, 
      [](auto /*vd*/) { return 1; }, 
      boost::predecessor_map(&p[0]). 
       weight_map(boost::get(&EdgeProperties::weight, filtered)). 
       distance_map(&d[0]). 
       visitor(vis) 
     ); 
} 

Remarques

• en foncteurs généraux sont passés par valeur dans les algorithmes de bibliothèque (standard). Donc vous utiliseriez std::reference_wrapper<BlackListEdgeConstraint> si vous vouliez utiliser la même instance. Mais comme je l'ai dit, je ne vois pas ce qui se passe, donc ce n'est pas un problème. AFAICT

• Dans votre échantillon, il ne semblait pas y avoir de carte de poids. Je ne vois pas comment cela aurait dû être compilé