Я создаю график в 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;
}
};
Задача ещё не решена.
Других решений пока нет …