时间戳

首页 > 解决方案 > Boost graph - 理解编译错误和最小属性

c++ - Boost graph - 理解编译错误和最小属性

问题描述

以下代码（片段 1）编译良好：

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
typedef adjacency_list_traits<vecS, vecS, undirectedS> Traits_vvu;

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type,
    property<vertex_distance_t, double,
    property<vertex_predecessor_t, Traits_vvd::edge_descriptor>
    > > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits_vvd::edge_descriptor>
> > > > >
Graph_vvd;

class MAXFLOW_ {
public:
    double solve_max_flow(int s, int t){
        double retval = boykov_kolmogorov_max_flow(g, s, t);
        return retval;
    }
private:
    Graph_vvd g;
};

int main(){
    return 0;
}

但是，在从图中删除时vertex_distance_t，vertex_predecessor_t我们的代码（片段 2）无法编译：

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
typedef adjacency_list_traits<vecS, vecS, undirectedS> Traits_vvu;

typedef adjacency_list<
    vecS, vecS, directedS,
    property<
    vertex_index_t, int,
    property<vertex_color_t, boost::default_color_type
    > >,
    property<
    edge_index_t, int,
    property<edge_capacity_t, double,
    property<edge_weight_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits_vvd::edge_descriptor>
> > > > >
Graph_vvd;

class MAXFLOW_ {
public:
    double solve_max_flow(int s, int t){
        double retval = boykov_kolmogorov_max_flow(g, s, t);
        return retval;
    }
private:
    Graph_vvd g;
};

int main(){
    return 0;
}

Snippet 1 和 Snippet 2 之间的唯一区别是，在第二个中，没有与vertex_distance_t和相关的顶点属性vertex_predecessor_t。

我的问题是：

(1)这里的编译错误对我来说是无法理解的。有没有办法开始理解错误并随后发现一个人错过了指定算法正常运行所需的属性，在这种情况下，算法使用 boykov_kolmogorov 方法找到最大流量？

(2) 在浏览此算法的 boost 文档中提供的代码示例（可在此处获得）时，确实顶点具有所需的属性：

property < vertex_name_t, std::string,
    property < vertex_index_t, long,
    property < vertex_color_t, boost::default_color_type,
    property < vertex_distance_t, long,
    property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,

但是这段代码也有一些不必要的属性，比如vertex_name_t没有哪些 Snippet 1 编译得很好。有没有办法找出最小的属性集来指定 boost 算法的正常运行？

标签： c++boostboost-graph

解决方案

算法记录了所需的属性：https ://www.boost.org/doc/libs/1_76_0/libs/graph/doc/boykov_kolmogorov_max_flow.html

您可以查看哪些参数是 IN/OUT 或 UTIL，哪些具有默认值（除非默认表达式对您的图形类型无效，否则它们是非强制性的）。

我在你之前的问题上反复这样做过：

简而言之：

  • 编译器消息令人生畏。阅读它们需要一些图书馆的经验。遗憾的是，这是将 C++03 与高度通用的模板一起使用的必然结果。如果您不需要这种通用库的原始功能，那么可能有更多用户友好的图形算法库。

    我说 C++03 是因为更新的标准可以提供更好的诊断。具体来说，我很高兴拥有一个支持概念的 BGL 版本。“不幸的是”（？）BGL 仍然与 C++03 兼容。

  • 基本上，您可以做的是专注于文档，而不是编译器消息。如果你“搞砸”了 C++ 特定的东西，而不是特定于库的东西（或遇到障碍） ，你仍然需要了解这些消息

  • 如果您对最低要求感兴趣，请关注 API 参考，而不是示例。示例经常随着时间的推移而演变，或者重用来自其他示例的数据/模型，因此不能假定它们是最小的。（有时，什么是最小的甚至可能取决于您的选择和偏好）。

推荐阅读