c++ - BGL-使用具有捆绑属性的流算法

我似乎无法弄清楚如何使BGL的push-relabel最大流算法与 bundle 的属性一起使用。

像这样设置图形:

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))
);

这无法编译(带有非常不可读的错误消息)。

不幸的是，文档提供的示例仍在使用其自身已标记为不推荐使用的内部属性，因此，我一直在努力寻找方法中的错误。有人碰巧看到它吗？

而且，当我们使用它时(并且很可能是相关的)，我可以以某种方式使边缘的反向边缘成为( bundle 的一部分!)边缘属性吗？如果是这样，怎么办？

更新

不知道这是怎么回事，但事实证明

        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

)

最佳答案

至少您必须在期望的位置传递属性映射:

.reverse_edge_map(make_assoc_property_map(reverse_edge_of))

关于c++ - BGL-使用具有捆绑属性的流算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33350553/