Boost: applying dijkstra_shortest_path() to filter

2019-07-15 11:39发布

问题:

I have a graph with bundled properties

//property
struct Edge
{
    int distance;
};

//graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Node, Edge> graph_t;

//predicate
template <typename Graph>
struct Filter
{
    const Graph gr;
    Filter(const Graph &g): gr(g) {}
    bool operator() (const Edge &e) const {
        if(gr[e].distance < 5) return 0;
        return 1;
    }
};

Filter <graph_t> filter(g);
boost::filtered_graph <graph_t, Filter <graph_t> > fg(g, filter);

And I want to apply dijkstra_shortest_path algorithm to filtered graph.

std::vector<int> d(num_vertices(fg));
std::vector<v> p(boost::num_vertices(fg));
boost::dijkstra_shortest_paths(fg, nodes[0], boost::weight_map(get(&Edge::distance, fg))
        .distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, fg)))
        .predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, fg))));

The errors i get, while compiling are:

/Users/artem/Documents/boost_1_55_0/boost/concept_check.hpp:142: error: object of type 'boost::filter_iterator >, boost::keep_all, boost::filtered_graph, Filter >, boost::keep_all> >, boost::detail::out_edge_iter, void *>, Edge> *>, unsigned long, boost::detail::edge_desc_impl, long> >' cannot be assigned because its copy assignment operator is implicitly deleted a = b; // require assignment operator ^

What is incorrect? Can't really understand, how to solve this problem.

回答1:

As referred in this post, your operator() should accept an edge descriptor and not an edge.

For example, you can try something like this:

bool operator() (const boost::graph_traits<graph_t>::edge_descriptor& e) const 
{
    ... get the variable edge of type Edge from the edge_descriptor e in some way ...

    if(gr[edge].distance < 5) return 0;
    return 1;
}

All these things make boost::graph very annoying to use. I hope the developers will improve the usability, which for the moment is very poor.

It may be useful to have a look to this post as well.



标签: boost graph