kconnected.h

/******************************************************
 * baumann
 * Fri Aug 15 14:13:45 CEST 2008
 * symbolic constraint for k-edge-connected graphs
 ******************************************************/
#ifndef KCONNECTED_H
#define KCONNECTED_H

#include <boost/foreach.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/type_traits/is_same.hpp>
#include <cstdarg>
#include <iostream>
#include <list>
#include <scil/core/cutTree.h>
#include <scil/core/min_cut.h>
#include <scil/scil.h>

namespace SCIL {

template <typename Graph>
class KCONNECTED : public sym_constraint { 

   private:

      typedef boost::graph_traits<Graph> GraphTraits;
      typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
      typedef typename GraphTraits::edge_descriptor edge_descriptor;

      Graph& G;                     
      var_map<edge_descriptor>& VM; 
      int k;

   public:
      KCONNECTED(Graph& G_, var_map<edge_descriptor>& VM_, int k_);

      void init(subproblem& S);

      int cutTreeSeparation(solution& sol, std::list<cons_obj*>& newCons);

      status standard_separation(subproblem& S);

      /* Tests whether the subgraph induced by the edges is k-connected
       */
      status feasible(solution& S);

      void info();

};

};

#include "../../../src/constraints/kconnected.cc"
#endif

---