c++ - 过滤图上的 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

我的boost版本是1.54

Answer 1

The problem is that, when boost::astar_search(..) is invoked, the empty constructor BlackListEdgeConstraint() is called.

我不知道你是怎么得出结论的。我无法重现:

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

• 在您的样本中似乎没有指示边缘权重图。我不明白应该如何编译