stronglyconnected.cc

#ifndef STRONGLY_CONNECTED_CC
#define STRONGLY_CONNECTED_CC


using namespace SCIL;
using namespace std;
using namespace boost;

#define VALONE 10000


template <typename Graph>
StronglyConnected<Graph>::StronglyConnected(Graph& G_, var_map<edge_descriptor>& VM_)
   /*{\Mcreate balbla }*/
{ 
   //Graph has to provide in_edges() and out_edges()
   BOOST_CONCEPT_ASSERT((BidirectionalGraphConcept<Graph>));
   //Graph has to provide vertices() and edges()
   BOOST_CONCEPT_ASSERT((VertexAndEdgeListGraphConcept<Graph>));
   srand(time(NULL));
   edge_descriptor e;
   vertex_descriptor v;
   BGL_FORALL_VERTICES_T(v, G_, Graph)
      add_vertex(G);
   BGL_FORALL_EDGES_T(e, G_, Graph){
      VM[add_edge(source(e, G_), target(e, G_), G).first] = VM_[e];
      if (VM_[e].type() != Vartype_Binary)
      {
         cerr << "stronglyconnected.cc: All variables in VM need ";
         cerr << "to be Vartype_Binary" << endl;
         exit(1);
      }
   }
   BGL_FORALL_EDGES_T(e, G, Graph){
      if(edge(target(e, G), source(e, G), G).second){
         edge_reverse[e] = edge(target(e, G), source(e, G), G).first;
         edge_reverse[edge_reverse[e]] = e;
      }
      else{
         edge_reverse[e] = add_edge(target(e, G), source(e, G), G).first;
         edge_reverse[edge_reverse[e]] = e;
         VM[edge_reverse[e]] = NULL;
      }
   }
};

template <typename Graph>
void StronglyConnected<Graph>::min_cut(vertex_descriptor u, map<edge_descriptor, int>& C, map<edge_descriptor, int>& F, 
      map<vertex_descriptor, bool>& R, int& k) {
   R[u]=true;
   k++;
   edge_descriptor e;
   for(typename GraphTraits::out_edge_iterator it = out_edges(u, G).first; it != out_edges(u,G).second; it++)
      if((F[*it]!=C[*it]) && (!R[target(*it, G)])) {
         min_cut(target(*it, G), C, F, R, k);
      }

   for(typename GraphTraits::in_edge_iterator it = in_edges(u, G).first; it != in_edges(u,G).second; it++)
      if((F[*it]!=0) && (!R[source(*it, G)])) {
         min_cut(source(*it, G), C, F, R, k);
      }
};

template <typename Graph>
typename StronglyConnected<Graph>::status StronglyConnected<Graph>::standard_separation(subproblem& S)
  /*{\Mop computes violated subtour-elimination constraints.}*/
{
   if (S.configuration("StronglyConnected_Debug_Out")=="true")
      cerr << "StronglyConnected::standard_separation\n";

   status sta=no_constraint_found;
   // Preparation
   capacity_map_t Cap;
   capacity_map_t Res;
   edge_descriptor e,f;
   int j;
   BGL_FORALL_EDGES_T(e, G, Graph) { 
      if(VM[e] != NULL)
         j=(int) (VALONE*S.value(VM[e]));
      else
         j=0;
      Cap[e]=j;
   };

   int nodenumber=rand() % num_vertices(G);
   typename GraphTraits::vertex_iterator node = vertices(G).first;
   node += nodenumber;
   vertex_descriptor w, u, v;
   v= *node;

   vertex_index_t vertex_index_map;
   int i = 0;
   BGL_FORALL_VERTICES_T(v, G, Graph)
      vertex_index_map[v] = i++;



   associative_property_map<capacity_map_t> cap_map(Cap);
   associative_property_map<capacity_map_t> res_map(Res);
   associative_property_map<vertex_index_t> pm_vertex_index(vertex_index_map);
   associative_property_map<edge_reverse_t> pm_edge_reverse(edge_reverse);

   BGL_FORALL_VERTICES_T(u, G, Graph){
      if (u!=v) {
         for(int i=0; i<2; i++) {
            if(i==0) {
               w=u;
               j=boykov_kolmogorov_max_flow(G, cap_map, res_map,pm_edge_reverse,pm_vertex_index, u,v); 
            } else {
               w=v;
               j=boykov_kolmogorov_max_flow(G, cap_map, res_map,pm_edge_reverse,pm_vertex_index, v, u); 
            }

            if(j<VALONE-100) {
               // Make Constraint
               map<vertex_descriptor, bool> R;
               vertex_descriptor x;
               BGL_FORALL_VERTICES_T(x, G, Graph)
                  R[x]=false;
               capacity_map_t Flow;
               BGL_FORALL_EDGES_T(e, G, Graph)
                  Flow[e] = Cap[e] - Res[e];
               j=0;
               min_cut(w, Cap, Flow, R, j);
               row r;
               BGL_FORALL_EDGES_T(f, G, Graph) {
                  if((R[source(f, G)]) && (!R[target(f, G)])) {
                     if(VM[f] != NULL)
                        r+=VM[f];
                  };
               }
               if(r.size() != 0){
                  S.add_basic_constraint(r>=1);
                  sta=constraint_found;
               }
            };
         };
      }
   }
   return sta;
}

template <typename Graph>
typename StronglyConnected<Graph>::status StronglyConnected<Graph>::feasible(solution& S) {
   if (S.originating_subproblem()->configuration("StronglyConnected_Debug_Out")=="true")
      cerr << "StronglyConnected::feasible\n";
   map<vertex_descriptor, vertex_descriptor> GtoH;
   Graph H;
   vertex_descriptor u;
   BGL_FORALL_VERTICES_T(u, G, Graph)
      GtoH[u]=add_vertex(H);
   edge_descriptor e;
   BGL_FORALL_EDGES_T(e, G, Graph) {
      if(S.value(VM[e])>0.5) 
         add_edge(GtoH[source(e, G)], GtoH[target(e, G)], H);
   }

   vector<int> component(num_vertices(H));
   int num_components = strong_components(H, &component[0]);
   
   if (num_components==1) 
      return feasible_solution;
   return infeasible_solution;
}

template <typename Graph>
void StronglyConnected<Graph>::info() {
   cout<<"Configurations:\n";
   cout<<"StronglyConnected_Debug_Out [true|false]\n";
};

#undef VALONE

#endif

---