我试图了解如何构建图形并使用 boost 库运行 stoer_wagner_min_cut
算法。
到目前为止,我使用 adjacency_matrix
容器构建了图形。
问题在于使stoer_wagner_min_cut
工作。我红this
文档,我遇到了两件事:
- “图类型必须是顶点列表图和关联图的模型。”
WeightMap 权重
作为输入。
第一部分是什么意思? adjacency_matrix
是某种类型的“顶点列表图和关联图”吗?有这方面的例子吗?
此外,图中所有边的权重均为 1。我不明白如何组装 WeightMap 权重
。并且找不到任何示例。
编辑:
这是我能做到的-
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/stoer_wagner_min_cut.hpp>
#include <boost/property_map/property_map.h>
using namespace boost;
typedef adjacency_matrix<undirectedS> UGraph;
void main()
{
static_property_map<UGraph, int>; // im not sure about UGraph
G = buildGraph(); // this function works fine
parity_map = stoer_wagner_min_cut(G, ..?..);
}
我应该如何定义此静态属性映射以返回 1 的 int 值?我有点挣扎。
我还看到 stoer_wagner_min_cut
的返回值是 parity_map
(ParityMap 必须是 Writable Property Map 的模型,它的值类型应该是 bool 类型)
我在构建和使用这些 map 时遇到了困难,我很乐意为此提供一些指导和示例..
谢谢。
最佳答案
-
what does the first section means? is adjacency_matrix some type of "Vertex List Graph and Incidence Graph"? is there an example for that?
这意味着图形类型必须建模命名的概念。这些概念记录在此处:
第二个问题是关于属性映射的。它们也是 concept
在这种情况下,提供静态属性映射是最简单的:
#include <boost/functional/hash.hpp> #include <boost/graph/adjacency_matrix.hpp> #include <boost/graph/stoer_wagner_min_cut.hpp> #include <boost/property_map/property_map.hpp> using namespace boost; typedef adjacency_matrix<undirectedS> UGraph; UGraph buildGraph() { UGraph g(10); // todo return g; } #include <iostream> int main() { UGraph g = buildGraph(); // this function works fine int i = stoer_wagner_min_cut(g, boost::make_static_property_map<UGraph::edge_descriptor>(1)); std::cout << "i: " << i << "\n"; }
关于c++ - 使用boost库找到图形的最小切割,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30804298/