boostorg / boostorg/graph

kruskal_minimum_spanning_tree not working on filtered graph with weight map as named property

未关闭
#380 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
algorithm named-parameters
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
20

描述

Hi everyone,

i cant use kruskal's alg on a filtered graph with a weight_map as named property.

```
#include
#include "boost/graph/graph_utility.hpp"
#include
#include
#include

using Graph = boost::adjacency_list;
using Vertex = boost::graph_traits::vertex_descriptor;
using Edge = boost::graph_traits::edge_descriptor;

int main()
{
Graph G;

// create a complete graph with 4 nodes.
for (int i = 0; i < 5 ; ++i)
{
for (int j = i+1; j< 5; ++j)
boost::add_edge(i, j, G);
}
boost::print_graph(G);
/* 0 <--> 1 2 3 4
1 <--> 0 2 3 4
2 <--> 0 1 3 4
3 <--> 0 1 2 4
4 <--> 0 1 2 3 */

struct Filter
{
bool operator()(Vertex const & v) const
{
if (v != 0 && v != 2)
return true;
return false;
}
};
boost::filtered_graph G_f(G, boost::keep_all(), Filter());
boost::print_graph(G_f);
/* 1 <--> 3 4
3 <--> 1 4
4 <--> 1 3 */

auto wmap = boost::make_function_property_map([](Edge const & e){ return 1.0; });
std::vector mst;

// Works:
kruskal_minimum_spanning_tree(G, std::back_inserter(mst), boost::weight_map(wmap));

// Does not compile:
kruskal_minimum_spanning_tree(G_f, std::back_inserter(mst), boost::weight_map(wmap));

double result = 0;
for (auto const & e : mst)
result += wmap[e];
std::cout << result << "\n"; // prints 4
}
````

Gives following errors:

```
error C2039: 'type': is not a member of 'boost::vertex_property_type'
error C2039: [
error C2039: with
error C2039: Graph=boost::filtered_graph
error C2039: ]
error C3203: 'type': unspecialized class template can't be used as a template argument for template parameter 'Property', expected a real type
```

Workaround:
`kruskal_minimum_spanning_tree(G_f, std::back_inserter(mst), boost::weight_map(wmap).vertex_index_map(get(boost::vertex_index, G_f)));`

More details on stackoverflow (Thanks to user sehe who helped me out):
https://stackoverflow.com/questions/78612600/boost-graph-using-kruskal-algorithm-on-filtered-graph-doesnt-compile

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。