boost :: astar_search過濾圖

Question

我需要在圖上運行A *，並刪除一些邊。爲此，我構建了一個包含黑名單邊的過濾圖，並且我想在過濾圖上運行A *。列入黑名單的邊被嵌入類BlackListEdgeConstraint中，我通過傳遞其構造函數來初始化禁止邊的列表。這個BlackListEdgeConstraint被正確地構建，並且我用這些約束構建了filtered圖。問題是，當我在篩選的圖上運行A *時，另一個BlackListEdgeConstraint對象被神奇地用空的構造函數構造，並且沒有邊被實際上列入黑名單。爲什麼會發生？

這是我的完整代碼：

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

} 

這是輸出：

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 

我增壓版本是1.54

Answer 1

的問題是，當升壓::調用astar_search（..）時，會調用空的構造函數BlackListEdgeConstraint（）。

我不知道你如何得出結論。我不能重現：

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

注

• 在一般仿函數由值（標準）庫的算法通過。所以如果你想使用相同的實例，你會使用std::reference_wrapper<BlackListEdgeConstraint>。但就像我說過的，我沒有看到它發生，所以這不是問題AFAICT

• 在您的示例中，似乎沒有顯示邊緣權重映射。我不知道應該如何編譯