我主要使用自己的网络流算法。但是,我最近才开始使用 boost,但在定义图形时遇到了困难。更具体地说,我自己的代码中的顶点编号为 0 到 n-1。边从 0 到 m-1 编号。我正在尝试构建一个非常简单的 4 边网络。
所有四个边的容量都是 4 个单元。我正在寻找 boost 以找到从 s = 0 到 t = 3 的最大流量。(答案是 8。)
为了让它运行,我有以下代码,但尽管它编译和构建没有错误,但代码没有按照我的预期进行。有关我的具体问题,请参阅代码中的注释。有两个问题(Q1)和(Q2)。
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < vecS, vecS, directedS,
property < vertex_name_t, std::string,
property < vertex_index_t, int,
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, double,
property < vertex_predecessor_t, Traits::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::edge_descriptor > > > > > > Graph;
int main()
{
Graph g;
property_map<Graph, vertex_index_t>::type v = get(vertex_index, g);
property_map<Graph, edge_index_t>::type e = get(edge_index, g);
property_map<Graph, edge_capacity_t>::type cap = get(edge_capacity, g);
property_map<Graph, edge_weight_t>::type cost = get(edge_weight, g);
property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
int nonodes = 4;
for (int i = 0; i < nonodes; i++) {
Traits::vertex_descriptor vd;
vd = add_vertex(g);
assert(v[vd] == i);//(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?
}
Graph::vertex_iterator vertexIt, vertexEnd;
tie(vertexIt, vertexEnd) = vertices(g);
//Create edges
Traits::edge_descriptor edf, edb;//Max flow algorithms seem to want both forward and backward edges. edf is for forward, edb is for backward
//Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error when boykov_kolmogorov_max_flow() is finally called.
edf = (add_edge(*(vertexIt+0), *(vertexIt + 1), g)).first;
edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;
e[edf] = 0;
e[edb] = 1;
cap[edf] = 4;
cap[edb] = 4;
edf = (add_edge(*(vertexIt + 0), *(vertexIt + 2), g)).first;
edb = (add_edge(*(vertexIt + 2), *(vertexIt + 0), g)).first;
e[edf] = 2;
e[edb] = 3;
cap[edf] = 4;
cap[edb] = 4;
edf = (add_edge(*(vertexIt + 1), *(vertexIt + 3), g)).first;
edb = (add_edge(*(vertexIt + 3), *(vertexIt + 1), g)).first;
e[edf] = 4;
e[edb] = 5;
cap[edf] = 4;
cap[edb] = 4;
edf = (add_edge(*(vertexIt + 2), *(vertexIt + 3), g)).first;
edb = (add_edge(*(vertexIt + 3), *(vertexIt + 2), g)).first;
e[edf] = 6;
e[edb] = 7;
cap[edf] = 4;
cap[edb] = 4;
double flow = boykov_kolmogorov_max_flow(g, *(vertexIt + 0), *(vertexIt + 3));
return 0;
}
关于问题 1)我查找了提供的解决方案 On C++ Boost Graph Creation and the vertex_index Property. .但是,我不清楚为什么 v[vd] = i;
会导致编译时错误,但 e[edf] = 0;
之后不会导致编译时间错误。
关于问题 2)我真正想要的是一种访问顶点以传递给 add_edge()
函数的方法。更一般地说,有没有一种方法可以通过诸如 vertex[2]
之类的某种机制访问第二条边(从 0 开始计数),或者通过诸如 edge[3]
等?
最佳答案
i); //(Q1)Here, v[vd] = i; produces an error. Is there any other way to assign integer indices to vertices?
当您使用 vecS
时,顶点索引是隐式 并且是顶点 vector 的整数索引。因此,如果不对周围的顶点进行物理洗牌,就无法分配它。
但是,您可以在没有内置隐式顶点索引的情况下自由操作,方法是选择一个非随机访问的顶点容器,例如listS
.
但是:如果这样做,您(显然)可以不再使用 ID 作为顶点描述符,使所有代码都像
edf = (add_edge(*(vertexIt + 0), *(vertexIt + 1), g)).first;
edb = (add_edge(*(vertexIt + 1), *(vertexIt + 0), g)).first;
很笨拙,更像是
auto find_vertex_by_id = [&g](size_t id) {
for(auto vd : boost::make_iterator_range(boost::vertices(g)))
if (id == g[vd])
return vd;
throw std::range_error("vertex id " + std::to_string(id));
};
edf = (add_edge(find_vertex_by_id(g[*vertexIt].id + 0), find_vertex_by_id(g[*vertexIt].id + 1), g)).first;
edb = (add_edge(find_vertex_by_id(g[*vertexIt].id + 1), find_vertex_by_id(g[*vertexIt].id + 0), u)).first;
查看 Live On Coliru ,我希望你同意这会加重病情。
Note it also crashes. Don't worry, that's a minor issue (mainly because the reverse edge map is not built up correctly). Fixing that, quickly, gives you the elusive
Flow: 8
! Sneak Preview
我建议走另一条路!拥抱隐式顶点索引,它与描述符类型一致。然后,不要为迭代器的迂回方式而烦恼,只需绝对地址:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <iostream>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
vecS, vecS, directedS,
property<
vertex_name_t, std::string,
property<vertex_index_t, int,
property<vertex_color_t, boost::default_color_type,
property<vertex_distance_t, double,
property<vertex_predecessor_t, Traits::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::edge_descriptor>
> > > > >
Graph;
int main() {
Graph g;
property_map<Graph, edge_index_t>::type e = get(edge_index, g);
property_map<Graph, edge_capacity_t>::type cap = get(edge_capacity, g);
//property_map<Graph, edge_weight_t>::type cost = get(edge_weight, g);
//property_map<Graph, edge_residual_capacity_t>::type rescap = get(edge_residual_capacity, g);
property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);
int nonodes = 4;
for (int i = 0; i < nonodes; i++) {
Traits::vertex_descriptor vd;
vd = add_vertex(g);
assert(vd == i);
}
// Create edges
Traits::edge_descriptor edf, edb; // Max flow algorithms seem to want both forward and backward edges. edf is for
// forward, edb is for backward
// Q2. All of the add_edge() functions below do not seem to add any edges to the graph, leading to a run time error
// when boykov_kolmogorov_max_flow() is finally called.
edf = (add_edge(0, 1, g)).first;
edb = (add_edge(1, 0, g)).first;
e[edf] = 0;
e[edb] = 1;
cap[edf] = 4;
cap[edb] = 4;
rev[edf] = edb;
rev[edb] = edf;
edf = (add_edge(0, 2, g)).first;
edb = (add_edge(2, 0, g)).first;
e[edf] = 2;
e[edb] = 3;
cap[edf] = 4;
cap[edb] = 4;
rev[edf] = edb;
rev[edb] = edf;
edf = (add_edge(1, 3, g)).first;
edb = (add_edge(3, 1, g)).first;
e[edf] = 4;
e[edb] = 5;
cap[edf] = 4;
cap[edb] = 4;
rev[edf] = edb;
rev[edb] = edf;
edf = (add_edge(2, 3, g)).first;
edb = (add_edge(3, 2, g)).first;
e[edf] = 6;
e[edb] = 7;
cap[edf] = 4;
cap[edb] = 4;
rev[edf] = edb;
rev[edb] = edf;
double flow = boykov_kolmogorov_max_flow(g, 0, 3);
std::cout << "Flow: " << flow << "\n";
}
打印
Flow: 8
那不是更好吗?现在,让我们继续改进那些仍然丑陋/烦人的东西
奖励 1:只需创建 4 个节点
add_vertex
循环现在看起来相当无能:
for (int i = 0; i < nonodes; i++) {
Traits::vertex_descriptor vd;
vd = add_vertex(g);
assert(vd == i);
}
确实,让我们写:
Graph g(nonodes);
奖励 2:捆绑这些属性
以必须将属性映射传递给算法为代价,您可以使用 Bundled Properties 使构建图形更容易接受。 :
等等 - 什么?那不是改进,是吗?好吧,等你看到这个:
struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
int edge_id = 0;
for (auto& edge : edges) {
auto edf = add_edge(edge.from, edge.to, EdgeProperty{edge_id++, 4}, g).first,
edb = add_edge(edge.to, edge.from, EdgeProperty{edge_id++, 4}, g).first;
rev[edf] = edb;
rev[edb] = edf;
}
耶!
奖励 3:分离临时顶点属性
那些特定于流算法的属性并不真正属于图中,那么为什么要包含它们呢?让我们做一些花哨的步法并使用外部 map 。这开始变得更先进了,但真正让我们明白了属性映射的要点:它们就像C++ 的镜头。
未发表评论:
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <functional>
#include <iostream>
using namespace boost;
struct VertexProperty { std::string name; };
struct EdgeProperty {
int id;
double capacity, residual_capacity;
EdgeProperty(int id, double cap, double res = 0)
: id(id), capacity(cap), residual_capacity(res)
{ }
};
typedef adjacency_list<vecS, vecS, directedS, VertexProperty, EdgeProperty> Graph;
int main() {
int nonodes = 4;
Graph g(nonodes);
// reverse edge map
auto e = get(&EdgeProperty::id, g);
auto rev = make_vector_property_map<Graph::edge_descriptor>(e);
// Create edges
struct { int from,to; } edges[] = { { 0, 1 }, { 0, 2 }, { 1, 3 }, { 2, 3 }, };
int edge_id = 0;
for (auto& pair : edges) {
auto a = add_edge(pair.from, pair.to, EdgeProperty { edge_id++, 4 }, g).first;
auto b = add_edge(pair.to, pair.from, EdgeProperty { edge_id++, 4 }, g).first;
rev[a] = b;
rev[b] = a;
}
// property maps
struct VertexEx {
default_color_type color;
double distance;
Graph::edge_descriptor pred;
};
auto idx = get(vertex_index, g);
auto vex = make_vector_property_map<VertexEx>(idx);
auto pred = make_transform_value_property_map(std::mem_fn(&VertexEx::pred), vex);
auto color = make_transform_value_property_map(std::mem_fn(&VertexEx::color), vex);
auto dist = make_transform_value_property_map(std::mem_fn(&VertexEx::distance), vex);
auto cap = get(&EdgeProperty::capacity, g);
auto rescap = get(&EdgeProperty::residual_capacity, g);
// algorithm
double flow = boykov_kolmogorov_max_flow(g, cap, rescap, rev, pred, color, dist, idx, 0, 3);
std::cout << "Flow: " << flow << "\n";
}
好处 4:也适用于边缘属性图
Live On Coliru ,评论更少。
关于c++ - 访问 boost::graph 中的特定顶点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45925625/