tjoin.cc

#ifndef TJOIN_CC
#define TJOIN_CC

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

template <typename Graph>
TJOIN<Graph>::TJOIN(Graph& G_, var_map<edge_descriptor>& VM_, map<vertex_descriptor, bool>& T_)
   :G(G_), VM(VM_), T(T_)
{
   //Check whether graph is undirected
   typedef typename GraphTraits::directed_category directed_category;
   bool graph_is_undirected = is_same<directed_category,undirected_tag>::value
      || is_base_and_derived<undirected_tag, directed_category>::value;
   BOOST_ASSERT(graph_is_undirected);

   edge_descriptor e;
   vertex_descriptor v;

   BGL_FORALL_EDGES_T(e, G, Graph) {
         if( VM[e].type() != Vartype_Binary ) {
             cerr << "TJOIN: All variables in VM need to be Vartype_Binary";
             cerr << endl;
             exit(1);
         }
   }

   //T has to describe a vertex set of even cardinality
   unsigned int i = 0;
   BGL_FORALL_VERTICES_T(v, G, Graph)
      if(T[v]) i++;
   if(i % 2 == 1) {
      cerr << "TJOIN: T has to describe a vertex set of even cardinality" <<endl;
      exit(1);
   }

   //Graph has to provide vertices() and edges()
   BOOST_CONCEPT_ASSERT((VertexAndEdgeListGraphConcept<Graph>));
   //Graph has to provide out_edges()
   BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
   //Graph has to provide clear_vertex()
   BOOST_CONCEPT_ASSERT((MutableGraphConcept<Graph>));

}

template <typename Graph>
void TJOIN<Graph>::init(subproblem& S){
   if( S.configuration("TJOIN_Debug_Out")=="true" )
      cerr << "TJOIN::init\n";
   return;
}

template <typename Graph>
typename TJOIN<Graph>::status TJOIN<Graph>::feasible(solution& S){
   typename GraphTraits::out_edge_iterator out_i, out_end;
   vertex_descriptor v;
   unsigned int i;
   BGL_FORALL_VERTICES_T(v, G, Graph){
      i = 0;
      for(tie(out_i, out_end)=out_edges(v, G); out_i != out_end; out_i++)
         if(S.value(VM[*out_i]) > 0.5)
            i++;
      if((T[v] && (i % 2 == 0) || (!T[v] && (i % 2 == 1))))
         return infeasible_solution;
   }
   return feasible_solution;
}

template <typename Graph>
typename TJOIN<Graph>::status TJOIN<Graph>::standard_separation(subproblem& S){
   double min;
   edge_descriptor e;
   vertex_descriptor v, w;
   map<edge_descriptor, double> c;
   map<vertex_descriptor, vertex_descriptor> p;
   map<vertex_descriptor, double> fl;
   map<edge_descriptor, double> flow;
   vector<int> mincomp(num_vertices(G));

   //initialize edge weights
   BGL_FORALL_EDGES_T(e, G, Graph)
      c[e] = S.value(VM[e]);

   //compute H, stored in p and fl
   computeCutTree(G, c, p, fl);

#ifdef DEBUG_TJOIN
   BGL_FORALL_VERTICES_T(v, G, Graph)
      if(v == 0)
         continue;
      else
         cout<<v<<"-"<<p[v]<<": "<<fl[v]<<endl;
#endif

   //Convert tree H into boost graph
   Graph H(num_vertices(G));
   BGL_FORALL_VERTICES_T(v, G, Graph)
      if(v == 0)
         continue;
      else
         flow[add_edge(v, p[v], H).first] = fl[v];

   //Find the minimum T-Cut among the fundamental cuts of H
   min = 1.;
   BGL_FORALL_EDGES_T(e, H, Graph) {
      vertex_descriptor s = source(e,H);
      vertex_descriptor t = target(e,H);
      Graph H1(H);
      remove_edge(s,t,H1);
      vector<int> components(num_vertices(H1));
      int num = connected_components(H1, &components[0]);

      //check if cut is a T-Cut
      unsigned int i = 0;
      BGL_FORALL_VERTICES_T(w, H1, Graph)
         if(components[w] == 0)
           i++;
      if((i % 2 == 1) && (flow[e] <= min)) {
         min = flow[e];
         mincomp = components;
      }
   }

#ifdef DEBUG_TJOIN
   BGL_FORALL_VERTICES_T(v, G, Graph)
      cout<<v<<": "<<mincomp[v]<<endl;
#endif

   if(min < 1 - .001) {
      //build constraint
      row r;
      BGL_FORALL_EDGES_T(e, G, Graph)
         if((mincomp[source(e, G)] && !mincomp[target(e,G)]) || (mincomp[target(e, G)] && !mincomp[source(e, G)]))
            r += VM[e];

      S.add_basic_constraint(r>=1);
      return constraint_found;
   }
   else
      return no_constraint_found;
}

#endif

---