Boost：将dijkstra_shortest_path（）应用于filtered_graph [英] Boost: applying dijkstra_shortest_path() to filtered_graph

问题描述

我有一个带有捆绑属性的图表

  //属性
结构边缘
 {
 int距离; 
}; 
 
 // graph 
 typedef boost :: adjacency_list< boost :: vecS，boost :: vecS，boost :: bidirectionalS，Node，Edge> graph_t; 
 
 //谓词
模板< typename Graph> 
结构过滤器
 {
 const Graph gr; 
 Filter（const Graph& g）：gr（g）{} 
 bool operator（）（const Edge& e）const {
 if（gr [e] .distance< 5）返回0; 
返回1; 
} 
}; 
 
过滤< graph_t>器（G）; 
 boost :: filtered_graph< graph_t，Filter< graph_t> > fg（g，filter）; 
  

我想将dijkstra_shortest_path算法应用于过滤图。

  std :: vector< int> d（为num_vertices（FG））; 
 std :: vector< v> P（升压::为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））））; 
  

编译时出现的错误是：

/Users/artem/Documents/boost_1_55_0/boost/concept_check.hpp:142：error：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>>'不能分配，因为它的拷贝赋值运算符被隐式删除
a = b; //需要赋值运算符
^

什么是不正确的？不能真正理解，如何解决这个问题。

正如在 post ，你的 operator（）应该接受一个边描述符而不是边。

例如，你可以尝试类似这个：
$ b $ pre $ bool operator（）（const boost :: graph_traits< graph_t> :: edge_descriptor& e）const
{
...以某种方式从edge_descriptor e中获取类型Edge的变量边缘...

if（gr [edge] .distance< 5）return 0;
返回1;

$ / code>

所有这些都使得 boost :: graph code>非常讨厌使用。我希望开发人员能够提高可用性，目前这种可用性非常差。

查看 this post 。

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.

解决方案

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：将dijkstra_shortest_path（）应用于filtered_graph的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！