c++ - 使用Boost库查找图形的最小割

原文 标签 c++ algorithm boost graph

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

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

问题是使stoer_wagner_min_cut有效。我红this
文档,我遇到两件事:

  • “图类型必须是“顶点列表图”和“关联图”的模型。”
  • WeightMap weights作为输入。

  • 第一部分是什么意思? adjacency_matrix是某种类型的“顶点列表图和关联图”吗?有一个例子吗?

    同样,图中的所有边的权重均为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, ..?..);
    }
    

    我应该如何定义此静态属性映射以返回int值1?我对此有点挣扎。
    我还看到stoer_wagner_min_cut的返回值为parity_map(ParityMap必须是可写属性映射的模型,其值类型应该是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?



    这意味着图类型必须为命名的概念建模。这里记录了这些概念:
  • http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_concepts.html

  • 第二个问题是关于属性映射的。他们也是concept

    在这种情况下,提供静态属性图将是最简单的:
  • 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";
    }
    

    相关文章:

    java - 如何使用深度优先搜索(DFS)在有向图中检测多个重叠周期?

    c++ - 管道实现问题

    c++ - LinkList代码中的错误

    algorithm - 从列表中查找具有最小XOR值的对

    c++ - 如何使g++引起异常而不是格式错误警告

    algorithm - 如何在Unity中对齐“轨道”或模块化对象?

    c++ - 如何返回boost::property_tree的叶节点

    c++ - 如何在C++中同步和合并来自多个线程的结果?

    c# - 如何使用C#客户端获取另一个应用程序中单击的GUI元素的信息?

    c++ - Gnuplot,Windows中的C++。命令窗口打开和关闭