spantree.h

#ifndef SPAN_TREE_H
#define SPAN_TREE_H

#include<scil/scil.h>
#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/adjacency_matrix.hpp>

using namespace boost;

namespace SCIL {

// The "vertex reached" property-tag
struct vertex_reached_t { 
  typedef vertex_property_tag kind;
};

template
<typename Graph>
class SpanTree : public sym_constraint { 

   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
   typedef typename graph_traits<Graph>::vertex_descriptor vertex;


   typedef adjacency_list_traits < vecS, vecS, bidirectionalS > Traits;

   typedef property < vertex_name_t, std::string,
           property < vertex_index_t, int,
           property < vertex_color_t, boost::default_color_type,
           property < vertex_distance_t, int,
           property < vertex_predecessor_t, Traits::edge_descriptor > > > > > kolmogorov_util_property;

   typedef property<vertex_reached_t, bool, kolmogorov_util_property> VertexProperty;

   typedef property<edge_capacity_t, int, 
           property<edge_residual_capacity_t, int,
           property<edge_reverse_t, Traits::edge_descriptor > > > EdgeProperty;
  
   typedef boost::adjacency_list<vecS,vecS,bidirectionalS, VertexProperty, EdgeProperty> bdGraph;
   typedef graph_traits<bdGraph>::vertex_descriptor H_vertex;
   typedef graph_traits<bdGraph>::edge_descriptor H_edge;

   private:
      Graph& G;
      var_map<edge_descriptor>& VM;     

      bdGraph H;
      std::map<vertex,H_vertex> GtoH;
      H_vertex son;
      H_vertex tan;
      std::map<edge_descriptor,H_edge> GtoH1;
      std::map<edge_descriptor,H_edge> GtoH2;

 
  class st_cutset_inequality;

   public:

      SpanTree(Graph& G_, var_map<edge_descriptor>& VM_);

      void init(subproblem& S);
  
      status standard_separation(subproblem& S);

      status feasible(solution& S);

      void min_cut(H_vertex u, property_map<bdGraph, edge_capacity_t>::type& C,  
         property_map<bdGraph, edge_residual_capacity_t>::type& resC,
         property_map<bdGraph, vertex_reached_t>::type& R, int& k);


      void info();

};
}
#include<../src/constraints/spantree.cc>
#endif

---