path.cc

#ifndef PATH_CONSTRAINT_CC
#define PATH_CONSTRAINT_CC

#include<scil/scil.h>
#include<LEDA/graph.h>
#include<LEDA/graph_alg.h>
#include<LEDA/set.h>
#include<scil/constraints/path.h>
#include<LEDA/p_queue.h>

using namespace LEDA;
using namespace SCIL;

<<<<<<< path.cc
#define VALONE 1000.0
#define NT int
=======
#define VALONE 1000.0
//#define NT int
>>>>>>> 1.3

class PATH::path_cutset_inequality : public cons_obj {
private:
  graph& G;
  scil_map<edge>& VM;
  node_array<bool> cut;
  double rhs;
  
public:
  
  path_cutset_inequality(graph& Gt, scil_map<edge>& VM_, list<node>& L) 
    : cons_obj(Greater, 1), G(Gt), VM(VM_) {
    node v;
    cut.init(G, false);
    forall(v,L) cut[v]=true;
  }

  void non_zero_entries(row& r) { 
    edge e;
    forall_edges(e,G) {
      if(coeff(e)==1) r+=VM(e);
    }
  }

  virtual
  ~path_cutset_inequality() {};
  
  double coeff(edge e) { 
    if(e==nil) return 0;
    if((cut[G.source(e)]) && (!cut[G.target(e)])) return 1;
    return(0);
  };
};

PATH::PATH(graph& G_, node u_, node v_, scil_map<edge>& 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_) { 
};

void PATH::dfs(graph& G, node u, node_array<bool>& R) {
  R[u]=true;
  edge e;
  forall_out_edges(e, u) if(!R[target(e)]) {
    dfs(G, target(e), R);
  };
};

void PATH::dfs(graph& G, node u, edge_array<NT>& val, edge_array<NT>& f, 
               node_array<bool>& R, list<node>& mc) {
  R[u]=true; mc.append(u);
  edge e;
  forall_out_edges(e, u) if((!R[target(e)]) && (val[e]!=f[e])) {
    dfs(G, target(e), val, f, R, mc);
  };
  forall_in_edges(e, u) if((!R[source(e)]) && (f[e]!=0)) {
    dfs(G, source(e), val, f, R, mc);
  };
};

#define NT int

PATH::status PATH::separate(subproblem& S) {
  //cout<<"prep\n";
  // Preperation
  int i=0;
  edge e;
  //node s=G.new_node();
  //edge e1=G.new_edge(s,u);

  edge_array<NT> val(G);
  forall_edges(e, G) 
    //if(e==e1) { 
    //  val[e]=VALONE;
    //} else {
    val[e]=leda_max((int) (VALONE*S.value(VM(e)))+1,1);
  //};

<<<<<<< path.cc
/*
  node_array<bool> R1(G, false);
  R1[u]=true;
  p_queue<NT, edge> PQ;
  edge_array<pq_item> EI(G, nil);
  NT cval=(int) VALONE, cs=0;

  forall_out_edges(e, u) {
      EI[e]=PQ.insert(-val[e], e);
      cs+=val[e];
  };

  bool sucess=false;
  edge e1;
  list<node> NL;
  NL.append(u);
  //cout<<"start\n";

  while (!PQ.empty()) {
      while(!PQ.empty() && (-PQ.prio(PQ.find_min())>=cval)) {
          e1=PQ.inf(PQ.find_min());
          PQ.del_min();
          R1[target(e1)]=true;
          NL.append(target(e1));
          cs-=val[e1];
          forall_in_edges(e, target(e1)) if((e!=e1) && (R1[source(e)])) {
              cs-=val[e];
              if(EI[e]==nil) cout<<"EROR2\n";
              PQ.del_item(EI[e]);
          };
          forall_out_edges(e, target(e1)) if(!R1[target(e)]) {
              cs+=val[e];
              EI[e]=PQ.insert(-val[e],e);
          };
          if(target(e1)==v) {
              cs=2*(int) VALONE;
              PQ.clear();
          };
      };

      if(cs<VALONE*900/1000) {
          cout<<cs<<" Heuristic found cut\n";
          cout<<NL.size()<<" size\n";
          cons_obj* c=new path_cutset_inequality(G,VM,NL);
          if(!(c->violated(S))) cout<<"ERROR\n";
          S.add_basic_constraint(c, Dynamic);
          sucess=true;
      };
      if(!PQ.empty())
          cval=PQ.prio(PQ.find_min());
  };

  if(sucess) return constraint_found;
  cout<<"no cut by heuristic\n";
*/

  //cout<<"start\n";
=======
/*
  node_array<bool> R1(G, false);
  R1[u]=true;
  p_queue<NT, edge> PQ;
  edge_array<pq_item> EI(G, nil);
  NT cval=(int) VALONE, cs=0;

  forall_out_edges(e, u) {
      EI[e]=PQ.insert(-val[e], e);
      cs+=val[e];
  };

  bool sucess=false;
  edge e1;
  list<node> NL;
  NL.append(u);
  cout<<"start\n";

  while (!PQ.empty()) {
      while(!PQ.empty() && (-PQ.prio(PQ.find_min())>=cval)) {
          e1=PQ.inf(PQ.find_min());
          PQ.del_min();
          R1[target(e1)]=true;
          NL.append(target(e1));
          cs-=val[e1];
          forall_in_edges(e, target(e1)) if((e!=e1) && (R1[source(e)])) {
              cs-=val[e];
              if(EI[e]==nil) cout<<"EROR2\n";
              PQ.del_item(EI[e]);
          };
          forall_out_edges(e, target(e1)) if(!R1[target(e)]) {
              cs+=val[e];
              EI[e]=PQ.insert(-val[e],e);
          };
          if(target(e1)==v) {
              cs=2*(int) VALONE;
              PQ.clear();
          };
      };

      if(cs<VALONE*900/1000) {
          cout<<cs<<" Heuristic found cut\n";
          cout<<NL.size()<<" size\n";
          cons_obj* c=new path_cutset_inequality(G,VM,NL);
          if(!(c->violated(S))) cout<<"ERROR\n";
          S.add_basic_constraint(c, Dynamic);
          sucess=true;
      };
      if(!PQ.empty())
          cval=PQ.prio(PQ.find_min());
  };

  if(sucess) return constraint_found;
  cout<<"no cut by heuristic\n";
*/

>>>>>>> 1.3
  // exact separation
  edge_array<NT> f(G);
  MAX_FLOW(G, u, v, val, f);
  node_array<bool> R(G, false);
  list<node> mc;
  dfs(G, u, val, f, R, mc);
  if(R[v]) cout<<"ERRROR\n";
  //mc.pop_front();
  //G.del_node(s);
  //cout<<"add\n";
  cons_obj* c=new path_cutset_inequality(G,VM,mc);
  //cout<<"constr\n";
  if (c->violated(S)) {
    //cout<<"jetzt\n";
    i++; S.add_basic_constraint(c, Dynamic); 
    //cout<<"end\n";
  } else delete c;
  //cout<<"edn\n";
  if(i>0) {
    return constraint_found;
  }
  //cout<<"No path constraint\n";
  return no_constraint_found;
}

PATH::status PATH::feasible(solution& S) {
  node_array<node> GtoH(G);
  graph H;
  node u1;
  forall_nodes(u1, G)
    GtoH[u1]=H.new_node();
  edge e;
  forall_edges(e,G) {
    if(S.value(VM(e))>0.5) H.new_edge(GtoH[source(e)], GtoH[target(e)]);
  }
  node_array<bool> R(H, false);
  dfs(H, GtoH[u], R);
  if (R[GtoH[v]]) return feasible_solution;
  return infeasible_solution;
};

#undef VALONE

#endif

---