在自定义图形类型上使用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 graph库中提供的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）。我怀疑我没有能够正确地将映射的正确类型传递给函数。函数签名可在这里的boost-doc中找到。

文档中给出了许多示例，但它们使用的图形与我的不同。我无法更改图形声明，否则会破坏很多代码。我不习惯于使用boost的property_map概念。

- Dilawar

---

一个问题（也许是THE问题）是reverse_edge_map需要一个带有key_type=edge_descriptor和value_type=edge_descriptor的属性映射，而您使用的那个是value_type=long。您可以使用adjacency_list_traits<vecS,vecS,bidirectionalS>::edge_descriptor来声明您的rev。如果您添加一个简单的示例图，我可以尝试使其正常工作。 - user1252091

谢谢，兄弟。有些事情发生了。如果我搞不定，我会创建一个小例子然后通知你。 - Dilawar

@llonesmiz 兄弟，你救了我的一天。感激不尽。请将此作为答案添加，我会接受它的。再次感谢。 :-) - Dilawar

Answer 1

这个解决方案是由llonesmiz提出的。

问题在于reverse_edge_map需要一个键类型为edge_descriptor，值类型为edge_descriptor的属性映射，而我使用的那个属性映射的值类型是long。我将rev声明为adjacency_list_traits<vecS,vecS,bidirectionalS>::edge_descriptor。它虽然编译通过了，但我生成了一个段错误，我认为这是函数逻辑的问题，而不是函数原型的问题。

- Dilawar

---

这里是一个使用此示例图表的示例：http://liveworkspace.org/code/4c3IQV$0。 - user1252091