フィルタリングされたグラフの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

• あなたのサンプルにエッジウェイトマップが表示されないようだったようだ。どのようにコンパイルする必要があるか分かりません