boostorg / boostorg/graph

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

Đang mở
#380 1 bình luận 0 reaction 0 người được giao Xem trên GitHub
algorithm named-parameters
Ngôn ngữ chính
C++
Star
392
Fork
239
Merge trung bình
1 ngày 11 phút
Pull request đã merge (30 ngày)
20

Mô tả

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

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.