kconnected.cc

//TODO: Toleranzen und EPS bestimmen, MIN_CUT braucht int-Gewichte!

#ifndef SCIL_KCONNECTED_CC
#define SCIL_KCONNECTED_CC

#define LEPS 1e-4
#define UEPS 1e4

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

template <typename Graph>
KCONNECTED<Graph>::KCONNECTED(Graph& G_, var_map<edge_descriptor>& VM_, int k_)
   : G(G_), VM(VM_), k(k_) {
   edge_descriptor e;
   feps = 1.0e-4;
   BGL_FORALL_EDGES_T(e, G, Graph)
      if(VM[e].type() != Vartype_Binary) {
         cerr << "kconnected.cc: All variables in VM need to be";
         cerr << " Vartype_Binary" << endl;
         exit(1);
      }
   //Graph has to provides edges() and vertices()
   BOOST_CONCEPT_ASSERT((VertexAndEdgeListGraphConcept<Graph>));
   //Graph has to provide out_edges()
   BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<Graph>));
}

template <typename Graph>
void KCONNECTED<Graph>::init(subproblem& S) {
   if (S.configuration("KCONNECTED_Debug_Out")=="true")
      cerr << "KCONNECTED::init\n";
   //Check whether Graph is undirected
   typedef typename GraphTraits::directed_category directed_category;
   if (!(is_same<directed_category,undirected_tag>::value
         || is_base_and_derived<undirected_tag, directed_category>::value)) {
      cerr << "kconnected.cc: The graph has to be undirected." << endl;
      exit(1);
   };

   //Check for parallel edges
   map<vertex_descriptor, map<vertex_descriptor, int> > edge_count;
   BGL_FORALL_EDGES_T(e, G, Graph)
      edge_count[source(e, G)][target(e, G)] = 0;
   BGL_FORALL_EDGES_T(e, G, Graph) {
      edge_count[source(e, G)][target(e, G)]++;
      edge_count[target(e, G)][source(e, G)]++;
      if (edge_count[source(e, G)][target(e, G)] > 1) {
         cerr << "kconnected.cc: The graph should not contain parallel edges.";
         cerr << endl;
         exit(1);
      }
   }
   BGL_FORALL_VERTICES_T(v, G, Graph) {
      row r;
      typename GraphTraits::out_edge_iterator oe_it, oe_it_end;
      for(tie(oe_it, oe_it_end)=out_edges(v, G); oe_it != oe_it_end; oe_it++)
         r += VM[*oe_it];
      if(r.size() > 0 )
         S.add_basic_constraint(r>=k, Static);
   }
   return;
};

template <typename Graph>
typename KCONNECTED<Graph>::status KCONNECTED<Graph>::feasible(solution& S) {
   if (S.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
      cerr << "KCONNECTED::feasible\n";
   map<edge_descriptor, int> w;

   BGL_FORALL_EDGES_T(e, G, Graph) {
      w[e] = int(double(UEPS) * S.value(VM[e]));
      if( w[e] < 0 )
               w[e] = 0;
   }

   MIN_CUT<Graph> *min_cut = new MIN_CUT<Graph>(G, w);
   int cv = (min_cut->run())->first;
   if( cv < k * UEPS )
      return infeasible_solution;
   else
      return feasible_solution;
}

template <typename Graph>
int KCONNECTED<Graph>::cutTreeSeparation(solution& sol, 
                                         list<cons_obj*>& newCons) {
   if (sol.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
      cerr << "KCONNECTED::cutTreeSeparation\n";

   int numfound = 0;
   map<edge_descriptor, double> ctc;
   map<vertex_descriptor, vertex_descriptor> p;
   map<vertex_descriptor, double> fl;
   BGL_FORALL_VERTICES_T(v, G, Graph) {
      p[v] = 0;
      fl[v] = -1.;
   }
   BGL_FORALL_EDGES_T(b, G, Graph) {
      ctc[b] = sol.value(VM[b]);
      if( ctc[b] < 1e-4 )
               ctc[b] = 1e-4;
   }
   computeCutTree(G, ctc, p, fl);

   BGL_FORALL_VERTICES_T(v, G, Graph) {
      if( p[v] == v || fl[v] >= double(k) - .0001 )
               continue;
      if (sol.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
         cerr << "fl: " << fl[v] << endl;
      row s;
      int rt = 0;

      //temporarily delete one edge of the cut tree
      vertex_descriptor ov = p[v];
      p[v] = v;

      //determine the cut nodes
      typedef map<vertex_descriptor, set<vertex_descriptor>* > vertex_partition;
      vertex_partition vpartition;
      //Initialize the vertex_partition
      BGL_FORALL_VERTICES_T(w, G, Graph) {
         vpartition[w] = new set<vertex_descriptor>();
         vpartition[w]->insert(w);
      }

      //Store the number of blocks in the Partition
      int num_blocks = num_vertices(G);
      //Union sets of vertices w with sets of vertices p[w]
      BGL_FORALL_VERTICES_T(w, G, Graph) {
         set<vertex_descriptor> *tmp = vpartition[p[w]];
         vpartition[w]->insert(tmp->begin(), tmp->end());
         typename set<vertex_descriptor>::iterator it;
         //Update the pointers of the vertices in vpartition[p[w]]
         for(it = tmp->begin(); it != tmp->end(); it++)
            vpartition[*it] = vpartition[w];
         num_blocks--;
      }

      if (sol.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
         cerr << "blocks: " << num_blocks << endl;
      BGL_FORALL_EDGES_T(f, G, Graph) {
         // Check whether source and target of edge f are in the same block
         if( *(vpartition[source(f, G)]) == *(vpartition[target(f, G)] ))
            s += VM[f];
      }
      newCons.push_back(s>=double(k));
      if (sol.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
         cerr << s << endl;
      numfound++;
      p[v] = ov;
   }
   return numfound;
}

template<typename Graph>
typename KCONNECTED<Graph>::status KCONNECTED<Graph>::standard_separation(subproblem& S) {
   if (S.configuration("KCONNECTED_Debug_Out")=="true")
      cerr << "KCONNECTED::standard_separation\n";
   solution sol;
   sol.save_solution(S);
   list<cons_obj*> newCons;
   bool found = false;

   if( cutTreeSeparation(sol, newCons) ) {
      //if( separateCut(sol, newCons) ) {
      list<cons_obj*>::const_iterator c;
      for(c = newCons.begin(); c != newCons.end(); c++) {
         if (sol.originating_subproblem()->configuration("KCONNECTED_Debug_Out")=="true")
            cerr << "vio: " << (*c)->violation(S) << endl;
         if( (*c)->violation(S) > feps ) {
            S.add_basic_constraint(*c);
            found = true;
         }
         else
            delete *c;
      }
      // exit(1);
   }
   if( found )
      return constraint_found;

   return no_constraint_found;
}

template <typename Graph>
void KCONNECTED<Graph>::info() {
   cout<<"Configurations:\n";
   cout<<"KCONNECTED_Debug_Out [true|false]\n";
};
#endif

---