在 Boost.Graph 中向图形添加边
Adding edges to a graph in Boost.Graph
我正在尝试将 Boost.Graph 库用于 运行 Goldberg 的最大流算法。 Boost.Graph 称之为 push_relabel_max_flow。
但是,我很难理解该库及其类型系统。我在上面链接的文档提供了示例代码。但在那个例子中,图形是从文件中读取的。我想在 运行 时间生成图表。这是我到目前为止的代码(大部分是从示例中复制的):
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::property<boost::vertex_name_t, std::string>,
boost::property<boost::edge_capacity_t, long,
boost::property<boost::edge_residual_capacity_t, long,
boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> DirectedGraph;
DirectedGraph g;
Traits::vertex_descriptor s, t;
s = boost::add_vertex(g);
t = boost::add_vertex(g);
boost::add_vertex(g);
boost::add_vertex(g);
在我向图中添加 4 个顶点后,我应该 "connect" 它们,即制作具有容量、剩余容量和反向值的边。此任务的函数是 boost::add_edge()
但我不知道如何传递我的参数。示例代码没有显示,因为正如我所说,数据是从文件中读取的,然后直接解析为图形。也许有 Boost.Graph 图书馆经验的人可以告诉我怎么做。
您可以在顶点 s
和 t
之间添加边,如下所示:
boost::add_edge(s, t, {33, 44}, g);
这里设置edge_capacity
为33,edge_residual_capacity
为44。
据我所知,要实际访问边缘属性,您必须执行以下操作:
std::cout << boost::get(boost::edge_capacity, g, boost::edge(s,t,g).first) << '\n';
这很烦人。如果您改用捆绑属性会更容易,如下所示:
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
struct VertexProps {
std::string name;
};
struct EdgeProps {
long capacity;
long residual_capacity;
Traits::edge_descriptor reverse;
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
VertexProps, EdgeProps > DirectedGraph;
然后你可以用同样的方法添加顶点和边,但是更容易访问边属性,例如
auto e = boost::edge(s,t,g).first; // get the edge descriptor for an edge from s to t, if any
std::cout << g[e].capacity << '\n';
要在您添加的匿名第三个和第四个顶点之间添加一条边,您可以使用
boost::add_edge(2, 3, {17, 26}, g);
因为底层存储是 vector
,所以 vertex_descriptor
只是向量索引(这里又名 size_t
,又名 unsigned long
)。但要更严格正确,你应该这样做
boost:add_edge(boost::vertex(2, g), boost::vertex(3, g), {17, 26}, g);
为了获得第 3 个和第 4 个顶点的 vertex_descriptor
。
我正在尝试将 Boost.Graph 库用于 运行 Goldberg 的最大流算法。 Boost.Graph 称之为 push_relabel_max_flow。
但是,我很难理解该库及其类型系统。我在上面链接的文档提供了示例代码。但在那个例子中,图形是从文件中读取的。我想在 运行 时间生成图表。这是我到目前为止的代码(大部分是从示例中复制的):
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::property<boost::vertex_name_t, std::string>,
boost::property<boost::edge_capacity_t, long,
boost::property<boost::edge_residual_capacity_t, long,
boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> DirectedGraph;
DirectedGraph g;
Traits::vertex_descriptor s, t;
s = boost::add_vertex(g);
t = boost::add_vertex(g);
boost::add_vertex(g);
boost::add_vertex(g);
在我向图中添加 4 个顶点后,我应该 "connect" 它们,即制作具有容量、剩余容量和反向值的边。此任务的函数是 boost::add_edge()
但我不知道如何传递我的参数。示例代码没有显示,因为正如我所说,数据是从文件中读取的,然后直接解析为图形。也许有 Boost.Graph 图书馆经验的人可以告诉我怎么做。
您可以在顶点 s
和 t
之间添加边,如下所示:
boost::add_edge(s, t, {33, 44}, g);
这里设置edge_capacity
为33,edge_residual_capacity
为44。
据我所知,要实际访问边缘属性,您必须执行以下操作:
std::cout << boost::get(boost::edge_capacity, g, boost::edge(s,t,g).first) << '\n';
这很烦人。如果您改用捆绑属性会更容易,如下所示:
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> Traits;
struct VertexProps {
std::string name;
};
struct EdgeProps {
long capacity;
long residual_capacity;
Traits::edge_descriptor reverse;
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
VertexProps, EdgeProps > DirectedGraph;
然后你可以用同样的方法添加顶点和边,但是更容易访问边属性,例如
auto e = boost::edge(s,t,g).first; // get the edge descriptor for an edge from s to t, if any
std::cout << g[e].capacity << '\n';
要在您添加的匿名第三个和第四个顶点之间添加一条边,您可以使用
boost::add_edge(2, 3, {17, 26}, g);
因为底层存储是 vector
,所以 vertex_descriptor
只是向量索引(这里又名 size_t
,又名 unsigned long
)。但要更严格正确,你应该这样做
boost:add_edge(boost::vertex(2, g), boost::vertex(3, g), {17, 26}, g);
为了获得第 3 个和第 4 个顶点的 vertex_descriptor
。