我似乎无法弄清楚如何让 BGL 的推送重新标记最大流量算法与捆绑属性一起使用。
像这样设置图表:
struct VertexProperties{
};
struct EdgeProperties{
int id;
int capacity;
int residual_capacity;
};
typedef boost::adjacency_list<vecS,vecS,directedS,VertexProperties,EdgeProperties> Graph;
typedef boost::graph_traits<Graph> Traits;
typedef Traits::vertex_descriptor Vertex;
typedef Traits::edge_descriptor Edge;
我创建了一个
Graph g(nofNodes); // nofNodes > 2
并选择
Vertex s = vertex(nofNodes-2,g); //source
Vertex t = vertex(nofNodes-1,g); //sink
然后我继续向图中添加边,并为插入的每条边添加容量为 0 的反向边。
使用 map
std::map<Edge,Edge> reverse_edge_of;
和
void do_add_edge(int& next_id, const Vertex& a, const Vertex& b, const int c, Graph& g,std::map<Edge,Edge>& reverse_edge_of){
Edge e,re; bool success;
std::tie(e,success) = add_edge(a,b,g);
g[e].id = next_id;
g[e].capacity = c;
g[e].residual_capacity = c;
//reverse edge
std::tie(re,success) = add_edge(b,a,g);
g[re].id = next_id + 1;
g[re].capacity = 0;
g[re].residual_capacity = 0;
reverse_edge_of[e] = re;
reverse_edge_of[re] = e;
next_id += 2;
}
完成后,我尝试调用库函数 push_relabel_max_flow像这样:
push_relabel_max_flow(
g,
s,
t,
capacity_map(get(&EdgeProperties::capacity,g))
.residual_capacity_map(get(&EdgeProperties::residual_capacity,g))
.reverse_edge_map(make_assoc_property_map(reverse_edge_of))
.vertex_index_map(get(vertex_index,g))
);
编译失败(错误信息非常难读)。
不幸的是,文档提供的示例仍在使用它自己标记为已弃用的内部属性,因此我正在努力寻找我的方法中的错误。有人碰巧看到了吗?
当我们讨论它时(因为它很可能相关),我能否以某种方式使边缘的反向边缘成为(捆绑的一部分!)边缘属性?如果是,怎么办?
更新
不知道这里发生了什么,但事实证明
int maxflow = push_relabel_max_flow(
g,
s,
t,
capacity_map(get(&EdgeProperties::capacity,g))
.residual_capacity_map(get(&EdgeProperties::residual_capacity,g))
.reverse_edge_map(make_assoc_property_map(reverse_edge_of))
.vertex_index_map(get(vertex_index,g))
);
会产生错误,而
int maxflow = push_relabel_max_flow(
g,
s,
t,
get(&EdgeProperties::capacity,g),
get(&EdgeProperties::residual_capacity,g),
make_assoc_property_map(reverse_edge_of),
get(vertex_index,g)
);
没有。
(例如
按预期工作:http://ideone.com/U3O0p8
编译器错误:http://ideone.com/uUuiKc
)
最佳答案
至少你必须在预期的地方传递 propertymap:
.reverse_edge_map(make_assoc_property_map(reverse_edge_of))
关于c++ - BGL - 使用具有捆绑属性的流算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33350553/