path.cc

#ifndef PATH_CONSTRAINT_CC
#define PATH_CONSTRAINT_CC


using namespace SCIL;
using namespace std;

#define VALONE 1000.0

template< typename Graph >
class PATH<Graph>::path_cutset_inequality : public cons_obj {
   private:
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
      typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

      Graph& G;
      var_map<edge_descriptor>& VM;
      std::map<vertex_descriptor,bool> cut;
      double rhs;

   public:

      path_cutset_inequality(Graph& Gt, var_map<edge_descriptor>& VM_, std::list<vertex>& L) 
         : cons_obj(Greater, 1), G(Gt), VM(VM_) {

            BGL_FORALL_VERTICES_T(v,G,Graph) 
               cut[v] = false; 

            typename std::list<vertex>::const_iterator it;         
            foreach(it,L) 
               cut[*it]=true;
         }

      void non_zero_entries(row& r) { 
         BGL_FORALL_EDGES_T(e,G,Graph)
            if((VM[e] != 0) && (coeff(e)==1)) 
                  r+=VM[e];
      }

      virtual
         ~path_cutset_inequality() {};

      double coeff(edge_descriptor e) { 
         if((cut[source(e,G)]) && (!cut[target(e,G)])) return 1;
         return(0);
      };
};



template< typename Graph >
PATH<Graph>::PATH(Graph& G_, vertex u_, vertex v_, var_map<edge_descriptor>& VM_)
   /*{\Mcreate Ensures that there is a path from $u$ to $v$ in the graph
      selected by the edges in VM.\\
      For a demo see: ptsp.
      }*/
  : G(G_), u(u_), v(v_), VM(VM_), H(num_vertices(G_)) { 

   // Asure G uses vertex_index_t and vertices are ordered by [0...num_vertices)
   if( !is_directed(G_) ) {
      cerr << "path.cc: The Graph G has to be directed" << endl;
     // exit(1);
   }

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

   // add reverse edges to local copy of G  (used for max flow algo)
   property_map<dGraph, edge_reverse_t>::type 
      rev = get(edge_reverse, H);
   dedge e1,e2;
   BGL_FORALL_EDGES_T(e,G,Graph) {
      if(edge(source(e,G), target(e,G),H).second){
         GtoH[e]=edge(source(e,G), target(e,G),H).first;
         continue;
      }
      e1 = add_edge( source(e,G), target(e,G), H).first;
      e2 = add_edge( target(e,G), source(e,G), H).first;
      GtoH[e] = e1;
      rev[e1] = e2;
      rev[e2] = e1;
   }   

   feps = 1.0e-4;
};


template< typename Graph >
void PATH<Graph>::dfs(dGraph& dG, dvertex u, std::vector<bool>& R) { 
   R[u]=true;
   BGL_FORALL_OUTEDGES_T(u,e,dG,dGraph) 
      if( !R[target(e,dG)] )
         dfs(dG, target(e,dG), R); 
};


template< typename Graph >
typename PATH<Graph>::status PATH<Graph>::standard_separation(subproblem& S) {
   if (S.configuration("PATH_Debug_Out")=="true")
      cerr << "PATH::standard_separation\n";
   // Preparation

   /* calculate the capacity for each edge e coming from G 
    * remark: each reverse edge gets capacity 0 */
   property_map<dGraph, edge_capacity_t>::type 
      cap = get(edge_capacity, H);

   property_map<dGraph, edge_reverse_t>::type 
      rev = get(edge_reverse, H); 

   property_map<dGraph, vertex_index_t>::type
      ind = get(vertex_index, H);

   property_map<dGraph, edge_residual_capacity_t>::type
      rescap = get(edge_residual_capacity, H);

   typedef map<vertex, default_color_type> color_map_t;
   color_map_t color_map;
   BGL_FORALL_VERTICES_T(v, H, dGraph) {
      color_map[v] = white_color;
   }
   associative_property_map<color_map_t> pm_color(color_map);

   BGL_FORALL_EDGES_T(e,H,dGraph)
      cap[e]=0;

   BGL_FORALL_EDGES_T(e,G,Graph) {
      if(VM[e] == 0)
         cap[GtoH[e]] = 1;
      else
         cap[GtoH[e]]=(int) (VALONE*S.value(VM[e]))+1;
   }

   // exact separation
   boykov_kolmogorov_max_flow(H, cap, rescap, rev, pm_color,ind, u,v);


   std::list<vertex> mc;
   BGL_FORALL_VERTICES_T(v, H, dGraph)
      if(color_map[v]==black_color)
         mc.push_back(v);

   int i=0;
   cons_obj* c=new path_cutset_inequality(G,VM,mc);
   if (c->violation(S) > feps) {
      i++; 
      S.add_basic_constraint(new path_cutset_inequality(G, VM, mc), Dynamic);
   }
   delete c;
   if(i>0) {
      return constraint_found; 
   }
   if(S.configuration("PATH_Debug_Out")=="true")
      cerr << "No path constraint\n";
   return no_constraint_found;
}


template< typename Graph >
typename PATH<Graph>::status PATH<Graph>::feasible(solution& S) {
   if (S.originating_subproblem()->configuration("PATH_Debug_Out")=="true")
      cerr << "PATH::feasible\n";

   dGraph H;
   std::map<vertex,dvertex> GtoH;

   BGL_FORALL_VERTICES_T(v,G,Graph)
      GtoH[v] = add_vertex(H);

   BGL_FORALL_EDGES_T(e,G,Graph) { 
      if((VM[e]!=0) && (S.value(VM[e])>0.5)) 
         add_edge( GtoH[ source(e,G) ], GtoH[ target(e,G) ], H);
   }   

   std::vector<bool> R(num_vertices(H),false);
   dfs(H, GtoH[u], R);

   if(R[GtoH[v]]) return feasible_solution;
   return infeasible_solution; 
};

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

#undef VALONE

#endif

---