使用Boost库寻找图的最小割

Question

使用Boost库寻找图的最小割

c++algorithmboostgraph

4

我正在尝试理解如何使用boost库构建图形并运行stoer_wagner_min_cut算法。

到目前为止，我已经使用adjacency_matrix容器构建了图形。

问题在于如何使stoer_wagner_min_cut正常工作。我阅读了this文档，并遇到了两个问题：

"图形类型必须是Vertex List Graph和Incidence Graph的模型。"
WeightMap weights作为输入。

第一部分是什么意思？adjacency_matrix是某种类型的"Vertex List Graph和Incidence Graph"吗？有没有示例？

此外，图中所有边的权重都为1。我不明白如何组装WeightMap weights，也找不到任何示例。

编辑：

这是我能够做到的-

#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必须是可写属性映射的模型，并且其值类型应该是bool类型）。

我对构建和使用这些映射有点困惑，希望能得到一些指导和示例。

谢谢。

- user1673206

请一次只提出一个问题。如果您需要具体的指导，请包含具体的代码。 - sehe

奇偶校验映射不是返回值，而是可选的输出参数。 - sehe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sehe · Accepted Answer

what does the first section means? is adjacency_matrix some type of "Vertex List Graph and Incidence Graph"? is there an example for that?

It means the graph type must model the named concepts. The concepts are documented here:
- http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_concepts.html

The second question is about property maps. They're also a concept

And in this case it would be easiest to supply a static property map:

http://www.boost.org/doc/libs/1_58_0/libs/property_map/doc/static_property_map.html

Live On Coliru

#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";
}