kruskal_minimum_spanning_tree not working on filtered graph with weight map as named property
- 主要语言
- 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 还没有评估数据。