double ComputeBroadcast2(graph& G, edge_array<double>& Cost, list<edge>& T,
GraphWin& GW) {
list<edge> MST=MIN_SPANNING_TREE(G, Cost);
node_array<double> MSTC(G,0);
edge e;
forall(e,MST) {
MSTC[source(e)]=leda_max(MSTC[source(e)], Cost[e]);
MSTC[target(e)]=leda_max(MSTC[target(e)], Cost[e]);
};
node u; double mstc=0;
forall_nodes(u, G) mstc+=MSTC[u]*MSTC[u];
graph H;
edge f;
node_array<node> GtoH(G);
node_map<point> P(H);
edge_array<edge> HtoG(H,2*G.number_of_edges(),e);
forall_nodes(u, G) {
GtoH[u]=H.new_node();
P[GtoH[u]]=GW.get_position(u);
};
forall_edges(e, G) {
f=H.new_edge(GtoH[source(e)], GtoH[target(e)]);
HtoG[f]=e;
f=H.new_edge(GtoH[target(e)], GtoH[source(e)]);
HtoG[f]=e;
};
edge_array<double> Cost2(H);
forall_edges(e, H) Cost2[e]=Cost[HtoG[e]];
cout<<"created copy\n";
ILP_Problem IP(Optsense_Min);
e=nil;
var_map<edge> VM;
var_map<edge> VMy;
forall_edges(e,H) {
VM[e]=IP.add_variable(0, 0, 1, Vartype_Integer);
VMy[e]=IP.add_variable(Cost[HtoG[e]]*Cost[HtoG[e]], 0, 1, Vartype_Integer);
}
cout<<"made constr 1\n";
forall_edges(e,H) {
row r1;
forall_out_edges(f,source(e)) if(Cost[HtoG[f]]>=Cost[HtoG[e]]-0.001) r1+=VMy[f];
IP.add_basic_constraint(r1 >= VM[e]);
}
cout<<"made cosntr 2\n";
forall_nodes(u, H) {
row r;
forall_out_edges(e, u) r+=VMy[e];
IP.add_basic_constraint(r==1);
};
cout<<"mad constr 3\n";
IP.add_sym_constraint(new StronglyConnected(H,VM));
IP.add_sym_constraint(new Broadcast2(H, VM, VMy, GW, Cost2));
IP.optimize();
forall_edges(e, H) {
if(IP.get_solution(VM[e])>0.5) {
GW.get_window().draw_arrow(P[source(e)],P[target(e)],red);
T.append(HtoG[e]);
};
}
GW.wait();
*/
list<edge> T1;
double optc=0;
forall_edges(e, H) {
if(IP.get_solution(VM[e])>0.5) {
T1.append(e);
T.append(HtoG[e]);
};
}
node_array<double> OPTC(H, 0);
forall(e,T1) {
OPTC[source(e)]=leda_max(OPTC[source(e)], Cost2[e]);
};
forall_nodes(u, H) optc+=OPTC[u]*OPTC[u];
cout<<"Number of nodes "<<G.number_of_nodes()<<endl;
cout<<"Cost of mst "<<mstc<<"\n";
cout<<"Cost of optimal solution "<<optc<<"\n";
cout<<"Save "<<(mstc-optc)/mstc*100<<"\n";
return (mstc-optc)/mstc*100;
}
