1

我通过以下方式在 boost 中创建了一个图表：

typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<setS, vecS, directedS, 
    property<vertex_name_t, std::string>,
    property<edge_capacity_t, double,
    property<edge_residual_capacity_t, double,
    property<edge_reverse_t, Traits::edge_descriptor> > >
    > Graph;
Graph g; 
Traits::vertex_descriptor s, t;

然后我在它上面运行最大流量：

flow = boost::edmonds_karp_max_flow(g, s, t);

在此之后，我创建了该图的副本 g_copy.H：

class CG{
  public:
  CG( Graph G, Traits::vertex_descriptor s, Traits::vertex_descriptor t)
    : H(G), src(s), sink(t) {

  Graph H;
  Traits::vertex_descriptor src;
  Traits::vertex_descriptor sink;
  property_map<Graph, boost::edge_capacity_t>::type capacity ;
  property_map<Graph, boost::edge_reverse_t>::type rev;
  property_map<Graph, boost::edge_residual_capacity_t>::type residual_capacity;
  }
}

主要：

CG g_copy(g,s,t)

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

将 s 和 t 更改为新的 s' 和 t'，然后再次运行最大流，这次是在复制的图 g_copy.H 上：

new_flow = boost::edmonds_karp_max_flow(g_copy.H, s', t');

如果我查看原始图的剩余容量，g，它们在 new_flow = boost::edmonds_karp_max_flow(g_copy.H, s', t'); 以前有人有同样的问题吗？我在这里做错了什么导致原始图的剩余容量发生了这种意外变化吗？感谢任何帮助或反馈！

这就是我设法复制图表的方式：

CG( Graph G, Traits::vertex_descriptor s, Traits::vertex_descriptor t ){

        //add the vertices to h
        std::vector<vertex_descriptor> verts;
        for(long vi = 0;  vi < num_vertices(G); ++vi)
            verts.push_back(add_vertex(H));


        // get the property map for vertex indices
        typedef property_map<Graph, vertex_index_t>::type IndexMap;
        IndexMap index = get(vertex_index, G);

        this->rev = get(edge_reverse, H);
        //get the edges
        boost::graph_traits<Graph>::vertex_iterator u_iter, u_end;
        boost::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){

                edge_descriptor e1,e2;
                bool in1, in2;
                int idx_s = index[source(*ei,G)];
                int idx_t = index[target(*ei, G)];
                boost::tie(e1, in1) = add_edge(idx_s, idx_t, H);    
                boost::tie(e2, in2) = add_edge(idx_t, idx_s, H);
                if(in1)
                    this->rev[e1] = e2; 
                if(in2)
                    this->rev[e2] = e1;
            }

        //get the properties of G
        property_map<Graph, edge_capacity_t>::type 
            cap = get(edge_capacity, G);
        property_map<Graph, edge_reverse_t>::type 
            reverse = get(edge_reverse, G);
        property_map<Graph, edge_residual_capacity_t>::type 
            residual_cap = get(edge_residual_capacity, G);

        //initiate the properties of H
        this->capacity = get(edge_capacity, H);
        this->residual_capacity = get(edge_residual_capacity, H);

        boost::graph_traits<Graph>::vertex_iterator u_iter1, u_end1, u_iter_2, u_end_2;
        boost::graph_traits<Graph>::out_edge_iterator ei1, e_end1, ei_2, e_end_2;
        for (boost::tie(u_iter1, u_end1) = vertices(G), boost::tie(u_iter_2, u_end_2) = vertices(H) ; 
                u_iter1 != u_end1 && u_iter_2 != u_end_2; ++u_iter1, ++u_iter_2)
            for (boost::tie(ei1, e_end1) = out_edges(*u_iter1, G), boost::tie(ei_2, e_end_2) = out_edges(*u_iter_2, H); ei1 != e_end1 && ei_2 != e_end_2;
                    ++ei1, ++ei_2){

                double temp_res = residual_cap[*ei1];
                this->residual_capacity[*ei_2] = temp_res;
                double temp_cap = cap[*ei1];
                this->capacity[*ei_2] = temp_cap;

            }
    };
4

0 回答 0