00001 #include <boost/foreach.hpp>
00002 #include <boost/graph/kruskal_min_spanning_tree.hpp>
00003 #include <boost/graph/random.hpp>
00004 #include <boost/property_map/property_map.hpp>
00005 #include <boost/random/mersenne_twister.hpp>
00006 #include <scil/constraints/spantree.h>
00007
00008
00009
00012 double ComputeBroadcast(Graph& G, std::list<edge_descriptor>& T) {
00013
00014 property_map<Graph, edge_weight_t>::type
00015 cost = get(edge_weight, G);
00016
00017 std::vector<edge_descriptor> MST;
00018 kruskal_minimum_spanning_tree(G, std::back_inserter(MST));
00019
00020 std::vector<double> MSTC(num_vertices(G));
00021 edge_descriptor e;
00022 BOOST_FOREACH(e,MST) {
00023 MSTC[source(e,G)]=std::max(MSTC[source(e,G)], cost[e]);
00024 MSTC[target(e,G)]=std::max(MSTC[target(e,G)], cost[e]);
00025 };
00026
00027 double mstc=0;
00028 BGL_FORALL_VERTICES(u,G,Graph)
00029 mstc+=MSTC[u]*MSTC[u];
00030
00031 if(0) {
00032 cout<<"cost of mst: " << mstc << endl;
00033 BOOST_FOREACH(e,MST) {
00034 cout << MSTC[source(e,G)] << " " << MSTC[target(e,G)] << endl;
00035 }
00036 exit(0);
00037 }
00038
00039 ILP_Problem IP(Optsense_Min);
00040
00041 var_map<edge_descriptor> VM;
00042 var_map<edge_descriptor> VMy;
00043 var_map<edge_descriptor> VMz;
00044
00045 BGL_FORALL_EDGES(e,G,Graph) {
00046 VM[e]=IP.add_binary_variable(-0.1);
00047 VMy[e]=IP.add_binary_variable(cost[e]*cost[e]);
00048 VMz[e]=IP.add_binary_variable(cost[e]*cost[e]);
00049 }
00050
00051
00052 BGL_FORALL_EDGES(e,G,Graph) {
00053 row r1;
00054 BGL_FORALL_OUTEDGES(source(e,G),f,G,Graph) if(cost[f]>=cost[e]-0.001) r1+=VMy[f];
00055 BGL_FORALL_INEDGES (source(e,G),f,G,Graph) if(cost[f]>=cost[e]-0.001) r1+=VMz[f];
00056 IP.add_basic_constraint(r1 >= VM[e]);
00057
00058 row r2;
00059 BGL_FORALL_OUTEDGES(target(e,G),f,G,Graph) if(cost[f]>=cost[e]-0.001) r2+=VMy[f];
00060 BGL_FORALL_INEDGES( target(e,G),f,G,Graph) if(cost[f]>=cost[e]-0.001) r2+=VMz[f];
00061 IP.add_basic_constraint(r2 >= VM[e]);
00062 }
00063
00064 BGL_FORALL_VERTICES(u,G,Graph) {
00065 row r;
00066 BGL_FORALL_OUTEDGES(u,e,G,Graph) r+=VMy[e];
00067 BGL_FORALL_INEDGES( u,e,G,Graph) r+=VMz[e];
00068 IP.add_basic_constraint(r==1);
00069 };
00070
00071 IP.add_sym_constraint(new SpanTree<Graph>(G,VM));
00072
00073
00074 IP.optimize();
00075
00076 double optc=0;
00077 BGL_FORALL_EDGES(e,G,Graph) {
00078 if(IP.get_solution(VM[e])>0.5) {
00079 T.push_back(e);
00080 };
00081 }
00082 BGL_FORALL_VERTICES(u,G,Graph)
00083 MSTC[u]=0;
00084
00085 BOOST_FOREACH(e,T) {
00086 MSTC[source(e,G)]=std::max(MSTC[source(e,G)], cost[e]);
00087 MSTC[target(e,G)]=std::max(MSTC[target(e,G)], cost[e]);
00088 };
00089 BGL_FORALL_VERTICES(u,G,Graph)
00090 optc+=MSTC[u]*MSTC[u];
00091
00092 cout<<"Number of nodes "<<num_vertices(G)<<endl;
00093 cout<<"Cost of mst "<<mstc<<"\n";
00094 cout<<"Cost of optimal solution "<<optc<<"\n";
00095
00096 cout<<"Save "<<(mstc-optc)/mstc*100<<"\n";
00097
00098
00099 return (mstc-optc)/mstc*100;
00100 }
