Hierarchical Index

00001 #ifndef STRONGLY_CONNECTED_CC
00002 #define STRONGLY_CONNECTED_CC
00003 
00004 #include<scil/scil.h>
00005 #include<LEDA/graph.h>
00006 #include<LEDA/graph_alg.h>
00007 #include<LEDA/set.h>
00008 #include<scil/constraints/stronglyconnected.h>
00009 
00010 using namespace SCIL;
00011 using namespace LEDA;
00012 
00013 #define VALONE 10000
00014 
00015 
00016 StronglyConnected::StronglyConnected(graph& G_, scil_map<edge>& VM_)
00017   /*{\Mcreate balbla }*/
00018   : G(G_), VM(VM_)
00019 { };
00020 
00021 void StronglyConnected::min_cut(node u, edge_array<int>& C, edge_array<int>& F, 
00022                                 node_array<bool>& R, int& k) {
00023   R[u]=true;
00024   k++;
00025   edge e;
00026   forall_out_edges(e, u) if((F[e]!=C[e]) && (!R[target(e)])) {
00027     min_cut(target(e), C, F, R, k);
00028   };
00029   forall_in_edges(e, u) if((F[e]!=0) && (!R[source(e)])) {
00030     min_cut(source(e), C, F, R, k);
00031   };
00032 };
00033 
00034 StronglyConnected::status StronglyConnected::separate(subproblem& S)
00035   /*{\Mop computes violated subtour-elimination constraints.}*/
00036 {
00037   status sta=no_constraint_found;
00038   // Preperation
00039   edge_array<int> Cap(G);
00040   edge e,f;
00041   int j;
00042   forall_edges(e, G) { 
00043     j=(int) (VALONE*S.value(VM(e)));
00044     Cap[e]=j;
00045   };
00046 
00047   node w, u, v=G.choose_node();
00048   
00049   edge_array<int> Flow(G);
00050   forall_nodes(u, G) if (u!=v) {
00051     for(int i=0; i<2; i++) {
00052       if(i==0) {
00053         w=u;
00054         j=MAX_FLOW(G, u, v, Cap, Flow);
00055       } else {
00056         w=v;
00057         j=MAX_FLOW(G, v, u, Cap, Flow);
00058       }
00059       
00060       if(j<VALONE-100) {
00061         // Make Constraint
00062         node_array<bool> R(G, false);
00063         j=0;
00064         min_cut(w, Cap, Flow, R, j);
00065         row r;
00066         forall_edges(f, G) {
00067           if((R[source(f)]) && (!R[target(f)])) {
00068             r+=VM(f);
00069           };
00070         }
00071         S.add_basic_constraint(r>=1);
00072         sta=constraint_found;
00073       };
00074     };
00075   };
00076   return sta;
00077 }
00078 
00079 StronglyConnected::status StronglyConnected::feasible(solution& S) {
00080   node_array<node> GtoH(G);
00081   graph H;
00082   node u;
00083   forall_nodes(u, G)
00084     GtoH[u]=H.new_node();
00085   edge e;
00086   forall_edges(e,G) {
00087     if(S.value(VM(e))>0.5) H.new_edge(GtoH[source(e)], GtoH[target(e)]);
00088   }
00089   node_array<int> C(H);
00090   int i=STRONG_COMPONENTS(H, C);
00091   if (i==1) return feasible_solution;
00092   cout<<"integer feasible, but infeasible\n";
00093   return infeasible_solution;
00094 }
00095 
00096 #undef VALONE
00097 
00098 #endif
stronglyconnected.cc
