c++ - 在自定义图形类型上使用 boost::push_relabel 算法

Question

我的图表有以下声明

struct vertex_info 
{
  std::string name;
  std::string label;    
  unsigned int type;
  bool isND; 
};

struct edge_info 
{
  std::string name;
  long capacity;
  long residualCapacity;
  long rev;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS
  , vertex_info, edge_info > expr_graph_t;

我构建了一个图(流网络)flowG，其中包含source 和sink 节点。现在我想使用 boost 图形库中提供的 push_relabel 方法计算最大流量。我正在调用该函数，如下所示。

  push_relabel_max_flow(flowG, source, sink
      , get(&edge_info::capacity, flowG)
      , get(&edge_info::residualCapacity, flowG)
      , get(&edge_info::rev, flowG)
      , get(boost::vertex_index, flowG)
      );

编译器 (g++) 正在生成长错误消息 (pasted here)。我怀疑我无法将正确类型的 map 传递给函数。函数签名可用here in boost-doc .

文档中给出了很多示例，但他们使用的图表与我的不同。我无法更改图形声明，否则很多代码都会中断。我不习惯提升 property_map 概念。

Answer 1

此解决方案归功于 llonesmiz。

问题是 reverse_edge_map需要 key_type= edge_descriptor 的属性映射和 value_type= edge_descriptor我使用的那个有 value_type= long .我声明了 rev作为adjacency_list_traits<vecS,vecS,bidirectionalS>::edge_descriptor .它编译时认为我生成了一个段错误，我认为这是函数逻辑的问题，而不是函数原型(prototype)的问题。