c++ - 使用boost库找到图形的最小切割

标签 c++ algorithm boost graph

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

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

问题在于使stoer_wagner_min_cut 工作。我红this 文档,我遇到了两件事:

  1. “图类型必须是顶点列表图和关联图的模型。”
  2. 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 时遇到了困难,我很乐意为此提供一些指导和示例..

谢谢。

最佳答案

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

    这意味着图形类型必须建模命名的概念。这些概念记录在此处:


  2. 第二个问题是关于属性映射的。它们也是 concept

    在这种情况下,提供静态属性映射是最简单的:

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

关于c++ - 使用boost库找到图形的最小切割,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30804298/

相关文章:

algorithm - 高效的分布式算法,用于合并具有公共(public)元素的集合

c++ - 将二维数组复制到 C++ 中未知大小的其他二维数组

c++模板或+运算符从指针创建 vector

c++ - 最简单的template-template为什么编译不出来?

JavaScript:mergeSort 返回 RangeError:超出最大调用堆栈大小

c++ - boost::filesystem::path::append(通过迭代器)导致编译器错误

c++ - 类型删除的 C++ 输出迭代器

c++ - CMake 未使用 brew (macOS) 找到 boost_python 库

c++ - QDataStream 无法序列化数据

c++ - NSMetaDataQuery:未收到更新或收集完成的通知