00001 #define K 4
00002
00003 void ComputeDMST(graph& G, edge_array<double>& Cost, list<edge>& T) {
00004
00005 ILP_Problem IP(Optsense_Min);
00006
00007 graph H;
00008
00009 node_array<node> GtoH[K];
00010 for(int i=0; i<K; i++) GtoH[i].init(G);
00011
00012 edge e,f;
00013 var_map<edge> VM;
00014 edge_map<edge> EM(H);
00015 node u;
00016 forall_nodes(u, G) {
00017 for(int i=0; i<K; i++) {
00018 GtoH[i][u]=H.new_node();
00019 if(i!=0) {
00020 f=H.new_edge(GtoH[i-1][u],GtoH[i][u]);
00021 VM[f]=IP.add_variable(0,0,1,Vartype_Integer);
00022 EM[f]=nil;
00023 };
00024 };
00025 };
00026
00027 cout<<"NODES\n";
00028
00029 forall_edges(e, G) {
00030 for(int i=1; i<K; i++) {
00031 f=H.new_edge(GtoH[i-1][source(e)],GtoH[i][target(e)]);
00032 VM[f]=IP.add_variable(Cost[e],0,1,Vartype_Integer);
00033 EM[f]=e;
00034 }
00035 }
00036
00037 cout<<"EDGES\n";
00038
00039 node s=GtoH[0][G.first_node()];
00040 forall_nodes(u,G) {
00041 IP.add_sym_constraint(new PATH(H, s, GtoH[K-1][u], VM));
00042 }
00043
00044 cout<<"CONSTR\n";
00045
00046 IP.optimize();
00047
00048 cout<<"OPT\n";
00049
00050 forall_edges(e, H) if((EM[e]!=nil) && (IP.get_solution(VM[e])==1))
00051 T.append(EM[e]);
00052 };
