一个图的割集，Boost Graph Library [英] Cut set of a graph, Boost Graph Library

问题描述

我一直在努力弄清楚如何做到这一点.我对快速找到图形的割集很感兴趣.我知道 BGL 支持通过迭代来查找割集，例如 edmonds_karp_max_flow 支持的 colorMap 参数.Gomory Hu 算法需要多次调用最小割算法.

我希望得到的结果是一个多图，其中包含:(颜色，顶点)

以下代码尝试重写 Boost Graph 库中的示例，以将多重映射用于 associative_property_map.可以通过以下方式编译代码:铛 -lboost_graph -o edmonds_karp edmonds_karp.cpp或 g++ 而不是 clang.我不明白由此产生的错误.

#include #include #include <字符串>#include #include #include <boost/graph/edmonds_karp_max_flow.hpp>#include #include #include #include #include int main(){使用命名空间提升；typedef adjacency_list_traits <vecS, vecS, 定向 >性状；typedef adjacency_list <列表、向量、定向、财产vertex_name_t, std::string >,财产edge_capacity_t，长，财产edge_residual_capacity_t，长，财产edge_reverse_t, Traits::edge_descriptor >>>>图形;图g；property_map <图，edge_capacity_t >::type容量 = 获取(边缘容量，g)；property_map <图，edge_reverse_t >::type rev = get(edge_reverse, g);property_map <图，edge_residual_capacity_t >::type剩余容量 = 获取(边缘剩余容量，g)；std::multimap颜色图；boost::associative_property_map<std::map>颜色图(颜色图)；特性::vertex_descriptor s, t;read_dimacs_max_flow(g, 容量, rev, s, t);std::vectorpred(num_vertices(g));长流 = edmonds_karp_max_flow(g，s，t，容量，residual_capacity，rev，make_iterator_property_map(color_map.begin()),&pred[0]);std::cout <<"c 总流量:" <<std::endl;std::cout <<s"<<流量＜＜std::endl <<std::endl;std::cout <<c流量值:"<<std::endl;graph_traits <图 >::vertex_iterator u_iter, u_end;graph_traits <图 >::out_edge_iterator ei, e_end;for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)如果(容量[*ei] > 0)std::cout <<f"<<*u_iter<<" " <<目标(*ei，g)＜＜""<<(容量[*ei] - 残差容量[*ei])<

提示将不胜感激.谢谢.

解决方案

这是一个基于 Boost BiMap 的快速 PoC

typedef boost::bimap, bimaps::set_of>智能地图；smart_map colorMap;boost::associative_property_mapcolor_map(colorMap.right);

我从 http://lpsolve.sourceforge.net/5.5/中抽取了一个小样本DIMACS_maxf.htm，您可以看到它在 Coliru 上直播，输出:

c 总流程:15c 流量值:0 1 50 2 101 3 51 4 02 3 52 4 53 5 104 5 5ltr: 0 ->5升:4 ->0ltr: 0 ->1升:4 ->2ltr: 0 ->3ltr: 0 ->4rtl: 0 ->4rtl: 1 ->0rtl: 2 ->4rtl: 3 ->0rtl: 4 ->0rtl: 5 ->0

完整列表:

#include #include #include #include #include #include <boost/graph/edmonds_karp_max_flow.hpp>#include #include #include #include #include int main() {使用命名空间提升；typedef adjacency_list_traits性状；typedef adjacency_list<listS、vecS、directedS、属性、属性::type capacity = get(edge_capacity, g);property_map::type rev = get(edge_reverse, g);property_map::typeresidual_capacity = get(edge_residual_capacity, g);typedef boost::bimap, bimaps::set_of>智能地图；smart_map colorMap;boost::associative_property_mapcolor_map(colorMap.right);特性::vertex_descriptor s, t;read_dimacs_max_flow(g, 容量, rev, s, t);std::vectorpred(num_vertices(g));长流 = edmonds_karp_max_flow(g、s、t、容量、residual_capacity、rev、color_map, &pred[0]);std::cout <<"c 总流量:" <<std::endl;std::cout <<s"<<流量＜＜std::endl <<std::endl;std::cout <<c流量值:"<<std::endl;graph_traits<Graph>::vertex_iterator u_iter, u_end;graph_traits<Graph>::out_edge_iterator ei, e_end;for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)如果(容量[*ei] > 0)std::cout <<f"<<*u_iter<<" " <<目标(*ei，g)＜＜" " <<(容量[*ei] - 残差容量[*ei])<<std::endl;for (auto const& e : colorMap.left) std::cout <<ltr:"<<e.首先<<"-> " <<e.秒＜＜"
";for (auto const& e : colorMap.right) std::cout <<rtl:"<<e.首先<<"-> " <<e.秒＜＜"
";返回退出成功；}

更新

使用 Boost MultiIndex 创建双向映射:

struct VertexColor {特性::vertex_descriptor 顶点；boost::default_color_type 颜色；};typedef boost::multi_index_container<顶点颜色，bmi::indexed_by

现在，使用 Boost Property Map 对 ReadWritePropertyMap:

struct bidi_color_map {typedef smart_map::index<by_vertex>::type impl_t;bidi_color_map(impl_t& ref) : ref_(&ref) {}impl_t &get() { 返回 *ref_;}impl_t const &get() const { return *ref_;}私人的:impl_t* ref_;};命名空间提升{模板 <>struct property_traits{typedef default_color_type value_type;typedef default_color_type 参考；typedef Traits::vertex_descriptor key_type;typedef read_write_property_map_tag 类别；};}boost::property_traits<bidi_color_map>::reference get(bidi_color_map const& idx, boost::property_traits<bidi_color_map>::key_type const& key) {auto it = idx.get().find(key);如果(它！= idx.get().end())返回它->颜色；别的throw std::range_error("在索引中找不到键");}void put(bidi_color_map& idx, boost::property_traits<bidi_color_map>::key_type const& key, boost::property_traits<bidi_color_map>::value_type val) {auto it = idx.get().find(key);如果(它！= idx.get().end())idx.get().modify(it, [val](VertexColor& p) { p.color = val; });别的idx.get().insert({key,val});}

现在您可以将其作为颜色图传递:

 smart_map colorMap;bidi_color_map color_map(colorMap.get());

查看在 Coliru 上直播>

I've been struggling a lot to figure out how to do this. I'm interested in quickly finding the cut set of a graph. I know that BGL supports finding the cut set by iteration over the colorMap arguments supported by, e.g., edmonds_karp_max_flow. The Gomory Hu algorithm needs to make several calls to a minimum cut algorithm.

The result that I was hoping for was to have a multimap that contains: (color, vertex)

The following code is an attempt at rewriting the example from the Boost Graph Library to use a multimap for the associative_property_map. Compiling the code can be done with: clang -lboost_graph -o edmonds_karp edmonds_karp.cpp or g++ instead of clang. I don't get the errors that come out of.

#include <boost/config.hpp>
#include <iostream>
#include <string>
#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>

int main()
{
  using namespace boost;

  typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
  typedef adjacency_list < listS, vecS, directedS,
    property < vertex_name_t, std::string >,
    property < edge_capacity_t, long,
    property < edge_residual_capacity_t, long,
    property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;

  Graph g;

  property_map < Graph, edge_capacity_t >::type
    capacity = get(edge_capacity, g);
  property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
  property_map < Graph, edge_residual_capacity_t >::type
    residual_capacity = get(edge_residual_capacity, g);

  std::multimap<default_color_type, Traits::vertex_descriptor> colorMap;
  boost::associative_property_map< std::map<default_color_type,
                                            Traits::vertex_descriptor> >
      color_map(colorMap);

  Traits::vertex_descriptor s, t;
  read_dimacs_max_flow(g, capacity, rev, s, t);

  std::vector<Traits::edge_descriptor> pred(num_vertices(g));
  long flow = edmonds_karp_max_flow
      (g, s, t, capacity, residual_capacity, rev,
       make_iterator_property_map(color_map.begin()),
       &pred[0]);

  std::cout << "c  The total flow:" << std::endl;
  std::cout << "s " << flow << std::endl << std::endl;

  std::cout << "c flow values:" << std::endl;
  graph_traits < Graph >::vertex_iterator u_iter, u_end;
  graph_traits < Graph >::out_edge_iterator ei, e_end;
  for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
    for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
      if (capacity[*ei] > 0)
        std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
          << (capacity[*ei] - residual_capacity[*ei]) << std::endl;

  // if using the original example, unedited, this piece of code works
  // BOOST_FOREACH(default_color_type x, color){
  //   std::cout << x << std::endl;
  // }

  return EXIT_SUCCESS;
}

Hints will be greatly appreciated. Thank you.

解决方案

Here's a quick PoC based on Boost BiMap

typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
smart_map colorMap;
boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);

I've taken a small sample from http://lpsolve.sourceforge.net/5.5/DIMACS_maxf.htm and you can see it Live On Coliru, output:

c  The total flow:
s 15

c flow values:
f 0 1 5
f 0 2 10
f 1 3 5
f 1 4 0
f 2 3 5
f 2 4 5
f 3 5 10
f 4 5 5
ltr: 0 -> 5
ltr: 4 -> 0
ltr: 0 -> 1
ltr: 4 -> 2
ltr: 0 -> 3
ltr: 0 -> 4
rtl: 0 -> 4
rtl: 1 -> 0
rtl: 2 -> 4
rtl: 3 -> 0
rtl: 4 -> 0
rtl: 5 -> 0

Full Listing:

#include <boost/foreach.hpp>
#include <boost/bimap.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/unordered_map.hpp>

int main() {
    using namespace boost;

    typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
    typedef adjacency_list<
        listS, vecS, directedS, property<vertex_name_t, std::string>,
        property<edge_capacity_t, long,
        property<edge_residual_capacity_t, long, 
        property<edge_reverse_t, Traits::edge_descriptor> > > > Graph;

    Graph g;

    property_map<Graph, edge_capacity_t>::type capacity                   = get(edge_capacity, g);
    property_map<Graph, edge_reverse_t>::type rev                         = get(edge_reverse, g);
    property_map<Graph, edge_residual_capacity_t>::type residual_capacity = get(edge_residual_capacity, g);

    typedef boost::bimap<bimaps::list_of<default_color_type>, bimaps::set_of<Traits::vertex_descriptor> > smart_map;
    smart_map colorMap;
    boost::associative_property_map<smart_map::right_map> color_map(colorMap.right);

    Traits::vertex_descriptor s, t;
    read_dimacs_max_flow(g, capacity, rev, s, t);

    std::vector<Traits::edge_descriptor> pred(num_vertices(g));
    long flow = edmonds_karp_max_flow(
            g, s, t, capacity, residual_capacity, rev,
            color_map, &pred[0]);

    std::cout << "c  The total flow:" << std::endl;
    std::cout << "s " << flow << std::endl << std::endl;

    std::cout << "c flow values:" << std::endl;
    graph_traits<Graph>::vertex_iterator u_iter, u_end;
    graph_traits<Graph>::out_edge_iterator ei, e_end;
    for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
        for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
            if (capacity[*ei] > 0)
                std::cout << "f " << *u_iter << " " << target(*ei, g) << " " << (capacity[*ei] - residual_capacity[*ei])
                          << std::endl;

    for (auto const& e : colorMap.left)  std::cout << "ltr: " << e.first << " -> " << e.second << "
";
    for (auto const& e : colorMap.right) std::cout << "rtl: " << e.first << " -> " << e.second << "
";

    return EXIT_SUCCESS;
}

UPDATE

Using Boost MultiIndex to create a bidirectional mapping:

struct VertexColor {
    Traits::vertex_descriptor vertex;
    boost::default_color_type color;
};

typedef boost::multi_index_container<
    VertexColor,
    bmi::indexed_by<
        bmi::hashed_non_unique<bmi::tag<struct by_color>,  bmi::member<VertexColor, boost::default_color_type, &VertexColor::color> >,
        bmi::ordered_unique   <bmi::tag<struct by_vertex>, bmi::member<VertexColor, Traits::vertex_descriptor, &VertexColor::vertex> >
    >
> smart_map;

Now, using Boost Property Map to model a ReadWritePropertyMap:

struct bidi_color_map {
    typedef smart_map::index<by_vertex>::type impl_t;
    bidi_color_map(impl_t& ref) : ref_(&ref) {}
    impl_t       &get()       { return *ref_; }
    impl_t const &get() const { return *ref_; }
private:
    impl_t* ref_;
};

namespace boost { 
    template <> struct property_traits<bidi_color_map> {
        typedef default_color_type          value_type;
        typedef default_color_type          reference;
        typedef Traits::vertex_descriptor   key_type;
        typedef read_write_property_map_tag category;
    };
}

boost::property_traits<bidi_color_map>::reference get(bidi_color_map const& idx, boost::property_traits<bidi_color_map>::key_type const& key) {
    auto it = idx.get().find(key);
    if (it != idx.get().end())
        return it->color;
    else
        throw std::range_error("key not found in index");
}

void put(bidi_color_map& idx, boost::property_traits<bidi_color_map>::key_type const& key, boost::property_traits<bidi_color_map>::value_type val) {
    auto it = idx.get().find(key);
    if (it != idx.get().end())
        idx.get().modify(it, [val](VertexColor& p) { p.color = val; });
    else
        idx.get().insert({key,val});
}

Now you can just pass that as the colormap:

    smart_map colorMap;
    bidi_color_map color_map(colorMap.get<by_vertex>());

See it Live On Coliru as well

这篇关于一个图的割集，Boost Graph Library的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！