00001 #define K 4
00002 using namespace SCIL;
00003
00004 void ComputeDMST(Graph& G, std::list<edge_descriptor>& T) {
00005
00006 ILP_Problem IP(Optsense_Min);
00007
00008 Graph H;
00009
00010 std::map<vertex_descriptor, vertex_descriptor> GtoH[K];
00011
00012 var_map<edge_descriptor> VM;
00013 map<edge_descriptor, std::pair<bool, edge_descriptor> > EM;
00014 BGL_FORALL_VERTICES(u, G, Graph) {
00015 for(int i=0; i<K; i++) {
00016 GtoH[i][u] = add_vertex(H);
00017 if(i != 0) {
00018 edge_descriptor f = (add_edge(GtoH[i-1][u], GtoH[i][u], H)).first;
00019 VM[f] = IP.add_binary_variable(0);
00020 EM[f] = std::pair<bool, edge_descriptor>(0,f);
00021 }
00022 }
00023 }
00024
00025 BGL_FORALL_EDGES(e, G, Graph) {
00026 for(int i=1; i<K; i++) {
00027 edge_descriptor f = (add_edge(GtoH[i-1][source(e, G)],
00028 GtoH[i][target(e, G)], H)).first;
00029 VM[f] = IP.add_binary_variable(G[e].distance);
00030 EM[f] = std::pair<bool, edge_descriptor>(1,e);
00031 }
00032 }
00033
00034 vertex_descriptor s=GtoH[0][*(vertices(G).first)];
00035 BGL_FORALL_VERTICES(u, G, Graph) {
00036 IP.add_sym_constraint(new PATH<Graph>(H, s, GtoH[K-1][u], VM));
00037 }
00038
00039 IP.optimize();
00040
00041 BGL_FORALL_EDGES(e, H, Graph)
00042 if(EM[e].first && (IP.get_solution(VM[e])==1))
00043 T.push_back(EM[e].second);
00044 }
