graphsup.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
 *
 *  Copyright:
 *     Patrick Pekczynski, 2005
 *
 *  Last modified:
 *     $Date: 2009-03-24 10:26:04 +0100 (Tue, 24 Mar 2009) $ by $Author: tack $
 *     $Revision: 8539 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

namespace Gecode { namespace Int { namespace GCC {

  enum BC {UBC = 1, LBC = 0};

  class Edge;
  class VVGNode {
  private:
    Edge* e;
    Edge* fst;
    Edge* lst;
    Edge* ie;
    bool  lm;
    bool  um;
    bool  type;
  public:


    VVGNode(void);

    virtual ~VVGNode(void){};
    void*  operator new(size_t, void*);



    Edge** adj(void);
    Edge*  first(void);
    Edge*  last(void);
    Edge*  inedge(void);
    bool   get_type(void);
    template <BC>
    bool   get_match_flag(void);
    virtual int  get_info(void) = 0;
    virtual bool is_matched(BC) = 0;

    virtual bool removed(void) = 0;



    void   first(Edge* p);
    void   last(Edge* p);
    void   inedge(Edge* p);
    void   set_type(bool t);
    template <BC>
    void   set_match_flag(bool f);
    virtual void set_info(int i) = 0;
  };

  class VarNode : public VVGNode {
  private:
    Edge* ubm;
    Edge* lbm;

  public:
    int var;
    int noe;

    int xindex;



    VarNode(int i, int oidx);



    template <BC>
    Edge* get_match(void);
    int   get_info(void);
    bool  is_matched(BC);
    template <BC>
    bool  matched(void);

    bool removed(void);



    void  set_info(int i);
    template <BC>
    void  set_match(Edge* m);
    template <BC>
    void  match(void);
    template <BC>
    void  unmatch(void);
  };

  class ValNode : public VVGNode {
  private:
    int _klb;
    int _kub;
    int _kidx;
    int _kcount;


    int noc;

    int lb;
    int ublow;
    int ub;

  public:
    int val;
    int idx;
    int noe;



    ValNode(int min, int max, int value, int kidx, int kshift, int count);



    void set_maxlow(int i);
    int  get_maxlow(void);


    void card_conflict(int c);
    int card_conflict(void);
    void red_conflict(void);

    bool removed(void);

    void inc(void);
    int kcount(void);
    template <BC>
    int incid_match(void);
    int kindex(void);
    int  get_info(void);
    template <BC>
    bool matched(void);
    bool sink(void);
    bool source(void);
    int  kmin(void);
    int  kmax(void);
    template <BC>
    int  kbound(void);

    bool is_matched(BC);


    void kcount(int);
    void kindex(int);
    template <BC>
    void dec(void);
    template <BC>
    void inc(void);
    template <BC>
    int  cap(void);
    template <BC>
    void set_cap(int c);
    template <BC>
    void match(void);
    template <BC>
    void unmatch(void);
    void reset(void);
    void set_info(int i);
    void set_kmin(int min);
    void set_kmax(int max);
  };

  class Edge{
  private:
    VarNode* x;
    ValNode* v;
    Edge* next_edge;
    Edge* prev_edge;
    Edge* next_vedge;
    Edge* prev_vedge;
    bool  mrklb;
    bool  mrkub;
    bool  um;
    bool  lm;
    bool  deleted;   // del

  public:


    Edge(VarNode* x, ValNode* v);
    void* operator new(size_t, void*);



    template <BC>
    bool used(void);
    template <BC>
    bool matched(void);
    bool is_deleted(void);
    Edge*    next(bool t) const;
    Edge*    next(void) const;
    Edge*    prev(void) const;
    Edge*    vnext(void) const;
    Edge*    vprev(void) const;
    VarNode* getVar(void);
    ValNode* getVal(void);
    VVGNode* getMate(bool t);



    template <BC>
    void use(void);
    template <BC>
    void free(void);
    template <BC>
    void reset(void);
    template <BC>
    void match(void);
    template <BC>
    void unmatch(void);
    template <BC>
    void unmatch(bool t);
    void unlink(void);
    void del_edge(void);
    void insert_edge(void);
    Edge**   next_ref(void);
    Edge**   prev_ref(void);
    Edge**   vnext_ref(void);
    Edge**   vprev_ref(void);
  };


  template <class View, class Card, bool isView>
  class VarValGraph {
  private:
    bool fail;
    char* mem;
    size_t _allocated;
    ViewArray<View>& x;
    ViewArray<View>& y;
    ViewArray<Card>& k;
    VarNode** vars;
    ValNode** vals;           // value partition    De
    Edge* edges;              // edges e
    int n_var;
    int n_val;
    int n_edge;
    int node_size;
    int sum_min;
    int sum_max;
  public:

    VarValGraph(ViewArray<View>&, ViewArray<View>&, ViewArray<Card>&,
                int , int , int );
    ~VarValGraph(void);
    size_t allocated(void) const;


    bool failed(void) const;
    void failed(bool b);

    bool min_require(Space& home);

    bool sync(Space& home);

    void* operator new(size_t t);
    void operator delete(void* p);

    template <BC>
    bool narrow(Space& home);

    template <BC>
    bool maximum_matching(Space& home);

    template <BC>
    void free_alternating_paths(Space& home);
    template <BC>
    void strongly_connected_components(Space& home);
    template <BC>
    bool augmenting_path(Space& home, VVGNode*);

  protected:
    template <BC>
    void dfs(VVGNode*,
             bool[], bool[], int[],
             Support::StaticStack<VVGNode*,Region>&,
             Support::StaticStack<VVGNode*,Region>&,
             int&);

  };

  forceinline
  VVGNode::VVGNode(void){} //no-op

  forceinline void*
  VVGNode::operator new(size_t, void* p){
    return p;
  }

  forceinline Edge**
  VVGNode::adj(void){
    return &e;
  }

  forceinline  Edge*
  VVGNode::first(void){
    return fst;
  }

  forceinline Edge*
  VVGNode::last(void){
    return lst;
  }

  forceinline void
  VVGNode::first(Edge* p){
    fst = p;
  }

  forceinline void
  VVGNode::last(Edge* p){
    lst = p;
  }

  forceinline bool
  VVGNode::get_type(void){
    return type;
  }

  forceinline void
  VVGNode::set_type(bool b){
    type = b;
  }

  forceinline Edge*
  VVGNode::inedge(void){
    return ie;
  }

  forceinline void
  VVGNode::inedge(Edge* p){
    ie = p;
  }

  template <BC direction>
  forceinline void
  VVGNode::set_match_flag(bool b){
    if (direction == UBC) {
      um = b;
    } else {
      lm = b;
    }
  }

  template <BC direction>
  forceinline bool
  VVGNode::get_match_flag(void){
    if (direction == UBC) {
      return um;
    } else {
      return lm;
    }
  }



  forceinline bool
  VarNode::removed(void) {
    return noe == 0;
  }



  forceinline
  VarNode::VarNode(int x, int orig_idx) :
    ubm(NULL), lbm(NULL), var(x), noe(0), xindex(orig_idx){
    first(NULL);
    last(NULL);
    inedge(NULL);
    unmatch<LBC>();
    unmatch<UBC>();
    set_type(false);
  }

  forceinline bool
  VarNode::is_matched(BC d) {
    if (d == UBC) {
      return matched<UBC>();
    } else {
      return matched<LBC>();
    }
  }

  template <BC direction>
  forceinline bool
  VarNode::matched(void){
    return get_match_flag<direction>();
  }

  template <BC direction>
  forceinline void
  VarNode::match(void){
    set_match_flag<direction>(true);
  }

  template <BC direction>
  forceinline void
  VarNode::unmatch(void){
    set_match_flag<direction>(false);
    set_match<direction>(NULL);
  }

  template <BC direction>
  forceinline void
  VarNode::set_match(Edge* p){
    if (direction == UBC) {
      ubm = p;
    } else {
      lbm = p;
    }
  }

  template <BC direction>
  forceinline Edge*
  VarNode::get_match(void){
    if (direction == UBC) {
      return ubm;
    } else {
      return lbm;
    }
  }

  forceinline void
  VarNode::set_info(int i){
    var = i;
  }

  forceinline int
  VarNode::get_info(void){
    return var;
  }


  forceinline void
  ValNode::set_maxlow(int i){
    assert(i >= lb);
    ublow = i;
  }

  forceinline int
  ValNode::get_maxlow(void) {
    if (_klb == _kub) {
      assert(ublow == lb);
    }

    return ublow;
  }


  forceinline void
  ValNode::card_conflict(int c){
    noc = c;
  }

  forceinline void
  ValNode::red_conflict(void){
    noc--;
    assert(noc >= 0);
  }

  forceinline int
  ValNode::card_conflict(void){
    return noc;
  }

  forceinline bool
  ValNode::removed(void) {
    return noe == 0;
  }

  forceinline bool
  ValNode::is_matched(BC d) {
    if (d == UBC) {
      return matched<UBC>();
    } else {
      return ublow == 0;
    }
  }

  forceinline void
  ValNode::reset(void){
    lb = _klb;
    ublow = _kub;
    ub = _kub;
    noe = 0;
  }

  template <BC direction>
  forceinline int
  ValNode::kbound(void){
    if (direction == UBC) {
      return _kub;
    } else {
      return _klb;
    }
  }

  forceinline int
  ValNode::kmax(void){
    return _kub;
  }

  forceinline int
  ValNode::kmin(void){
    return _klb;
  }

  forceinline void
  ValNode::set_kmin(int klb){
    _klb = klb;
  }

  forceinline void
  ValNode::set_kmax(int kub){
    _kub = kub;
  }

  template <BC direction>
  forceinline int
  ValNode::cap(void){
    if (direction == UBC) {
      return ub;
    } else {
      return lb;
    }
  }

  template <BC direction>
  forceinline void
  ValNode::dec(void){
    if (direction == UBC) {
      ub--;
    } else {
      lb--;
      ublow--;
    }
  }

  template <BC direction>
  forceinline void
  ValNode::inc(void){
    if (direction == UBC) {
      ub++;
    } else {
      lb++;
      ublow++;
    }
  }

  template <BC direction>
  forceinline void
  ValNode::match(void){
    dec<direction>();
  }

  template <BC direction>
  forceinline void
  ValNode::unmatch(void){
    inc<direction>();
  }

  template <BC direction>
  forceinline bool
  ValNode::matched(void){
    return ( cap<direction>() == 0);
  }

  forceinline
  ValNode::ValNode(int min, int max, int value,
                   int kidx, int kshift, int count) :
    _klb(min), _kub(max), _kidx(kidx), _kcount(count),
    noc(0),
    lb(min), ublow(max), ub(max),
    val(value), idx(kshift), noe(0) {
    first(NULL);
    last(NULL);
    inedge(NULL);
    Edge** vadjacent = adj();
    *vadjacent = NULL;
    set_type(true);
  }

  template<BC direction>
  forceinline void
  ValNode::set_cap(int c){
    if (direction == UBC) {
      ub = c;
    } else {
      lb = c;
//       ublow = c;
    }
  }

  forceinline void
  ValNode::set_info(int i){
    idx = i;
  }

  forceinline int
  ValNode::get_info(void){
    return idx;
  }

  forceinline void
  ValNode::inc(void) {
    _kcount++;
  }

  forceinline int
  ValNode::kcount(void) {
    return _kcount;
  }

  forceinline void
  ValNode::kcount(int c) {
    _kcount = c;
  }

  forceinline void
  ValNode::kindex(int i){
    _kidx = i;
  }

  forceinline int
  ValNode::kindex(void){
    return _kidx;
  }

  template <BC direction>
  forceinline int
  ValNode::incid_match(void){
    if (direction == LBC) {
      // std::cout << "LBC: "<< _kub <<"-"<<ublow <<"+"<<_kcount<<"\n";
      return _kub - ublow + _kcount;
    } else {
      // std::cout << "UBC: "<< _kub <<"-"<<ub <<"+"<<_kcount<<"\n";
      return _kub - ub + _kcount;
    }
  }


  forceinline bool
  ValNode::sink(void){
    // there are only incoming edges
    // in case of the UBC-matching
    bool is_sink = false;
    is_sink = (_kub - ub == noe);
    return is_sink;
  }

  forceinline bool
  ValNode::source(void){
    // there are only incoming edges
    // in case of the UBC-matching
    bool is_sink = false;
    is_sink = (_klb - lb == noe);
    return is_sink;
  }

  forceinline void
  Edge::unlink(void){
    // unlink from variable side
    Edge* p = prev_edge;
    Edge* n = next_edge;

    if (p != NULL) {
      Edge** pnext = p->next_ref();
      *pnext = n;
    }

    if (n != NULL) {
      Edge** nprev = n->prev_ref();
      *nprev = p;
    }

    if (this == x->first()) {
      Edge** ref = x->adj();
      *ref = n;
      x->first(n);
    }

    if (this == x->last()) {
      x->last(p);
    }

    // unlink from value side
    Edge* pv = prev_vedge;
    Edge* nv = next_vedge;

    if (pv != NULL) {
      Edge** pvnext = pv->vnext_ref();
      *pvnext = nv;
    }

    if (nv != NULL) {
      Edge** nvprev = nv->vprev_ref();
      *nvprev = pv;
    }

    if (this == v->first()) {
      Edge** ref = v->adj();
      *ref = nv;
      v->first(nv);
    }

    if (this == v->last()) {
      v->last(pv);
    }
  }

  forceinline
  Edge::Edge(VarNode* var, ValNode* val) :
    x(var), v(val),
    next_edge(NULL), prev_edge(NULL),
    next_vedge(NULL), prev_vedge(NULL),
    mrklb(false), mrkub(false),
    um(false), lm(false), deleted(false) {}

  forceinline void*
  Edge::operator new(size_t, void* p){ //why is there no argument?
    return p;
  }

  template <BC direction>
  forceinline void
  Edge::use(void){
    if (direction == UBC) {
      mrkub = true;
    } else {
      mrklb = true;
    }
  }

  template <BC direction>
  forceinline void
  Edge::free(void){
    if (direction == UBC) {
      mrkub = false;
    } else {
      mrklb = false;
    }
  }

  template <BC direction>
  forceinline void
  Edge::reset(void){
    this->free<direction>();
    this->unmatch<direction>();
  }

  template <BC direction>
  forceinline bool
  Edge::used(void){
    if (direction == UBC){
      return mrkub;
    } else {
      return mrklb;
    }
  }

  forceinline Edge*
  Edge::next(void) const{
    return next_edge;
  }

  forceinline Edge*
  Edge::next(bool t) const{
    if (t) {
      return next_vedge;
    } else {
      return next_edge;
    }
  }

  forceinline Edge*
  Edge::vnext(void) const{
    return next_vedge;
  }

  forceinline Edge**
  Edge::vnext_ref(void) {
    return &next_vedge;
  }

  forceinline Edge*
  Edge::prev(void) const{
    return prev_edge;
  }

  forceinline Edge**
  Edge::prev_ref(void) {
    return &prev_edge;
  }

  forceinline Edge*
  Edge::vprev(void) const{
    return prev_vedge;
  }

  forceinline Edge**
  Edge::vprev_ref(void) {
    return &prev_vedge;
  }

  forceinline Edge**
  Edge::next_ref(void){
    return &next_edge;
  }
  forceinline VarNode*
  Edge::getVar(void){
    assert(x != NULL);
    return x;
  }

  forceinline ValNode*
  Edge::getVal(void){
    assert(v != NULL);
    return v;
  }

  forceinline VVGNode*
  Edge::getMate(bool type){
    if (type) {
      return x;
    } else {
      return v;
    }
  }

  template <BC direction>
  forceinline void
  Edge::unmatch(void){
    if (direction == UBC) {
      um = false;
    } else {
      lm = false;
    }
    x->unmatch<direction>();
    v->unmatch<direction>();
  }

  template <BC direction>
  forceinline void
  Edge::unmatch(bool node){
    if (direction == UBC) {
      um = false;
    } else {
      lm = false;
    }
    if (node) {
      v->template unmatch<direction>();
    } else {
      x->template unmatch<direction>();
    }
  }

  template <BC direction>
  forceinline void
  Edge::match(void){
    if (direction == UBC) {
      um = true;
      x->template match<direction>();
      x->template set_match<direction>(this);
      v->template match<direction>();
    } else {
      lm = true;
      x->template match<direction>();
      x->template set_match<direction>(this);
      assert(x->template matched<direction>());
      v->template match<direction>();
//       assert(v->template matched<direction>());
    }
  }

  template <BC direction>
  forceinline bool
  Edge::matched(void){
    if (direction == UBC) {
      return um;
    } else {
      return lm;
    }
  }

  forceinline void
  Edge::del_edge(void){
    deleted = true;
  }

  forceinline void
  Edge::insert_edge(void){
    deleted = false;
  }


  forceinline bool
  Edge::is_deleted(void){
    return deleted;
  }

  template <class View, class Card, bool isView>
  VarValGraph<View, Card, isView>::VarValGraph(ViewArray<View>& xref,
                                               ViewArray<View>& yref,
                                               ViewArray<Card>& kref,
                                               int noe,
                                               int smin, int smax)
    : fail(false),
      x(xref),
      y(yref),
      k(kref),
      n_var(x.size()),
      n_val(k.size()),
      n_edge(noe),
      node_size(n_var + n_val),
      sum_min(smin),
      sum_max(smax) {

    //memory allocation
    size_t  edge_size      = sizeof(Edge)     * n_edge;
    size_t  var_size       = sizeof(VarNode)  * n_var;
    size_t  var_ptr_size   = sizeof(VarNode*) * n_var;
    size_t  val_size       = sizeof(ValNode)  * n_val;
    size_t  val_ptr_size   = sizeof(ValNode*) * n_val;
    size_t  size           = edge_size + var_size + var_ptr_size +
      val_size + val_ptr_size;

    _allocated = size;

    mem      = static_cast<char*>
      (heap.ralloc(size));
    edges    = Support::ptr_cast<Edge*>
      (mem);
    VarNode* vars_ptr = Support::ptr_cast<VarNode*>
      (mem + edge_size);
    ValNode* vals_ptr = Support::ptr_cast<ValNode*>
      (mem + edge_size + var_size);
    vars     = Support::ptr_cast<VarNode**>
      (mem + edge_size + var_size + val_size);
    vals     = Support::ptr_cast<ValNode**>
      (mem + edge_size + var_size + val_size + var_ptr_size);

    for (int i = n_val; i--; ){
      int kmi = k[i].min();
      int kma = k[i].max();
      int kc  = k[i].counter();
      if (kc != kma) {
        if (kmi >= kc) {
          kmi -=kc;
          assert(kmi >=0);
        } else {
          kmi = 0;
        }
        kma -= kc;
        assert (kma > 0);
        vals[i] = new (vals_ptr + i)
          ValNode(kmi, kma, k[i].card(), i, i + n_var, kc);
      } else {
        vals[i] = new (vals_ptr + i)
          ValNode(0, 0, k[i].card(), i, i + n_var, kc);
      }
    }

    for (int i = n_var; i--; ){

      vars[i]          = new (vars_ptr + i) VarNode(i, i);
      VarNode* vrn     = vars[i];
      // get the space for the edges of the varnode
      Edge** xadjacent = vrn->adj();

      ViewValues<View> xiter(x[i]);
      int j = 0;
      for (; xiter(); ++xiter){
        int v = xiter.val();
        // get the correct index for the value
        while(vals[j]->val < v){
          j++;
        }
        ValNode* vln = vals[j];
        *xadjacent = new (edges) Edge(vars_ptr + i, vals_ptr + j);
        vrn->noe++;
        if (vrn->first() == NULL) {
          vrn->first(*xadjacent);
        }
        Edge* oldprev  = vrn->last();
        vrn->last(*xadjacent);
        Edge** newprev = vrn->last()->prev_ref();
        *newprev       = oldprev;

        if (vln->first() == NULL) {
          vln->first(*xadjacent);
          vln->last(*xadjacent);
          vln->noe++;
        } else {
          Edge* old      = vln->first();
          vln->first(*xadjacent);
          Edge** newnext = vln->first()->vnext_ref();
          *newnext       = old;
          Edge** setprev = old->vprev_ref();
          *setprev       = vln->first();
          vln->noe++;
        }
        edges++;
        xadjacent = (*xadjacent)->next_ref();
      }
      *xadjacent = NULL;
    }
  }

  template <class View, class Card, bool isView>
  forceinline size_t
  VarValGraph<View, Card, isView>::allocated(void) const {
    return _allocated + sizeof(VarValGraph<View, Card, isView>);
  }

  template <class View, class Card, bool isView>
  forceinline bool
  VarValGraph<View, Card, isView>::failed(void) const {
    return fail;
  }

  template <class View, class Card, bool isView>
  forceinline void
  VarValGraph<View, Card, isView>::failed(bool b){
    fail = b;
  }



  template <class View, class Card, bool isView>
  inline bool
  VarValGraph<View, Card, isView>::min_require(Space& home){
    bool modified = false;
    for (int i = n_val; i--; ) {
      ValNode* vln = vals[i];
      if (vln->noe > 0) {
        if (k[i].min() == vln->noe) {
          // all variable nodes reachable from vln should be equal to vln->val
          for (Edge* e = vln->first(); e != NULL; e = e->vnext()) {
            VarNode* vrn = e->getVar();
            int vi = vrn->get_info();
            for (Edge* f = vrn->first(); f != NULL; f = f->next()) {
              if (f != e) {
                ValNode* w = f->getVal();
                w->noe--;
                vrn->noe--;
                f->del_edge();
                f->unlink();
              }
            }
            assert(vrn->noe == 1);

            ModEvent me = x[vi].eq(home, vln->val);
            if (me_failed(me))
              failed(true);
            if (me_modified(me))
              modified = true;

            vars[vi] = vars[--n_var];
            vars[vi]->set_info(vi);

            int n = x.size();
            x[vi] = x[--n];
            x.size(n);

            node_size--;
            vln->noe--;
          }


          int vidx = vln->kindex();
          if (isView) {
            ModEvent me = k[vidx].eq(home, k[vidx].min());
            if (me_failed(me))
              failed(true);
            if (me_modified(me))
              modified = true;
          }

          k[vidx].counter(k[vidx].min());

          vln->template set_cap<UBC>(0);
          vln->template set_cap<LBC>(0);
          vln->set_maxlow(0);

          if (sum_min && sum_min >= k[vidx].min()) {
            sum_min -= k[vidx].min();
          }
          assert(sum_min >=0);

          if (sum_max && sum_max >= k[vidx].max()) {
            sum_max -= k[vidx].max();
          }
          assert(sum_max >=0);
        }
      } else {
        vals[i]->template set_cap<UBC>(0);
        vals[i]->template set_cap<LBC>(0);
        vals[i]->set_maxlow(0);
        vals[i]->set_kmax(0);
        vals[i]->set_kmin(0);

      }

      if (isView) {
        if (k[i].counter() == 0) {
          ModEvent me = k[i].lq(home, vals[i]->noe);
          if (me_failed(me))
            failed(true);
          if (me_modified(me) && k[i].max() != vals[i]->noe)
            modified = true;
        }
      }
    }

    for (int i = n_val; i--; )
      vals[i]->set_info(n_var + i);

    return modified;
  }

  template <class View, class Card, bool isView>
  inline bool
  VarValGraph<View, Card, isView>::sync(Space& home) {
    Region r(home);
    VVGNode** re = r.alloc<VVGNode*>(node_size);
    int n_re = 0;

    // synchronize cardinality variables
    if (isView) {
      for (int i = n_val; i--; ) {
        ValNode* v  = vals[i];
        int inc_ubc = v->template incid_match<UBC>();
        int inc_lbc = v->template incid_match<LBC>();
        if (v->noe == 0) {
          inc_ubc = 0;
          inc_lbc = 0;
        }
        int rm = v->kmax() - k[i].max();
        // the cardinality bounds have been modified
        if (k[i].max() < v->kmax() || k[i].min() > v->kmin()) {
          if (k[i].max() != k[i].counter() || k[i].max() == 0) {
            // update the bounds
            v->set_kmax(k[i].max());
            v->set_kmin(k[i].min());

            //everything is fine
            if (inc_ubc <= k[i].max()) {
              // adjust capacities
              v->template set_cap<UBC>(k[i].max() - (inc_ubc));
              v->set_maxlow(k[i].max() - (inc_lbc));
              if (v->kmin() == v->kmax()) {
                v->template set_cap<LBC>(k[i].max() - (inc_lbc));
              }
            } else {
              // set cap to max and resolve conflicts on view side
              // set to full capacity for later rescheduling
              if (v->template cap<UBC>()) {
                v->template set_cap<UBC>(k[i].max());
              }
              v->set_maxlow(k[i].max() - (inc_lbc));
              if (v->kmin() == v->kmax()) {
                v->template set_cap<LBC>(k[i].max() - (inc_lbc));
              }
              v->card_conflict(rm);
            }
          }
        }
        if (inc_lbc < k[i].min() && v->noe > 0) {

          v->template set_cap<LBC>(k[i].min() - inc_lbc);
          re[n_re] = v;
          n_re++;
        }
      }

      for (int i = n_var; i--; ) {
        Edge* mub = vars[i]->template get_match<UBC>();
        if (mub != NULL) {
          ValNode* vu = mub->getVal();
          if (! (vars[i]->noe == 1) ) {
            if (vu->card_conflict()) {
              vu->red_conflict();
              mub->template unmatch<UBC>(vars[i]->get_type());
              re[n_re] = vars[i];
              n_re++;
            }
          }
        }
      }
    }

    // go on with synchronization
    assert(x.size() == n_var);
    for (int i = n_var; i--; ) {

      VarNode* vrn = vars[i];
      if(static_cast<int>(x[i].size()) != vrn->noe){
        // if the variable is already assigned
        if (x[i].assigned()) {
          int  v = x[i].val();
          ValNode* rv = NULL;
          int rv_idx  = 0;
          Edge* mub = vrn->template get_match<UBC>();
          if (mub != NULL) {
            if (v != mub->getVal()->val) {
              mub->template unmatch<UBC>();
              re[n_re] = vars[i];
              n_re++;
            }
          }

          Edge* mlb = vrn->template get_match<LBC>();
          if (mlb != NULL) {
            ValNode* vln = mlb->getVal();
            if (v != vln->val) {
              mlb->template unmatch<LBC>();
              int nom = vln->template incid_match<LBC>();
              // less values than required
              bool cond = nom < vln->kmin();
              if (cond) {
                re[n_re] = vln;
                n_re++;
              }
            }
          }

          for (Edge* e = vrn->first(); e != NULL; e = e->next()){
            ValNode* vln = e->getVal();
            if (vln->val != v) {
              vrn->noe--;
              e->getVal()->noe--;
              e->del_edge();
              e->unlink();
            } else {
              rv = e->getVal();
              rv_idx = rv->kindex();
            }
          }
        } else {

          // delete the edge
          ViewValues<View> xiter(x[i]);
          Edge*  mub = vrn->template get_match<UBC>();
          Edge*  mlb = vrn->template get_match<LBC>();
          Edge** p   = vrn->adj();
          Edge*  e   = *p;
          do {
            // search the edge that has to be deleted
            while (e != NULL && e->getVal()->val < xiter.val()) {
              // Skip edge
              e->getVal()->noe--;
              vrn->noe--;
              e->del_edge();
              e->unlink();
              e = e ->next();
              *p = e;
            }

            assert(xiter.val() == e->getVal()->val);

            // This edge must be kept
            e->template free<UBC>();
            e->template free<LBC>();
            ++xiter;
            p = e->next_ref();
            e = e->next();
          } while (xiter());
          *p = NULL;
          while (e) {
            e->getVar()->noe--;
            e->getVal()->noe--;
            e->del_edge();
            e->unlink();
            e = e->next();
          }

          if (mub != NULL){
            if (mub->is_deleted()) {
              mub->template unmatch<UBC>();
              re[n_re] = vars[i];
              n_re++;
            }
          }

          //lower bound matching can be zero
          if (mlb != NULL) {
            if (mlb->is_deleted()) {
              ValNode* vln = mlb->getVal();
              mlb->template unmatch<LBC>();
              int nom   = vln->template incid_match<LBC>();
              bool cond = nom < vln->kmin();
              if (cond) {
                re[n_re] = vln;
                n_re++;
              }
            }
          }
        }
      }
      vars[i]->set_info(i);
    }

    for (int i = n_val; i--; ) {
      if (k[i].min() > vals[i]->noe && k[i].counter() == 0) {
        failed(true);
        return false;
      }
      vals[i]->set_info(n_var + i);
    }

    if (n_re == 0) {
      // no repair needed
      return true;
    } else {
      // start repair

      bool repaired = true;
      while (n_re ) {
        n_re--;
        assert(re[n_re] != NULL);
        if (!(re[n_re]->removed())) {
          if (!(re[n_re]->get_type())) {
            VarNode* vrn = static_cast<VarNode*>(re[n_re]);
            if (!vrn->template matched<UBC>()) {
              repaired &= augmenting_path<UBC>(home,vrn);
            }
          } else {
            assert(re[n_re]->get_type());
            ValNode* vln = static_cast<ValNode*>(re[n_re]);
            while(!vln->template matched<LBC>()) {
              repaired &= augmenting_path<LBC>(home,vln);
              if (!repaired) {
                break;
              }
            }
          }
        }
      }
      return repaired;
    }
  }

  template <class View, class Card, bool isView> template <BC direction>
  inline bool
  VarValGraph<View, Card, isView>::narrow(Space& home) {
    bool modified  = false;
    for (int i = n_var; i--; ) {
      VarNode* vrn = vars[i];
      if (vrn->noe == 1) {
        Edge* e = vrn->first();
        ValNode* v = e->getVal();
        e->template free<direction>();
        ModEvent me = x[i].eq(home, v->val);
        if (me_failed(me)) {
          failed(true);
          return false;
        }
        if (me_modified(me))
          modified = true;
        v->inc();
      }
    }
    for (int i = n_val; i--; ) {
      ValNode* v = vals[i];
      if (isView)
        if (k[i].counter() == 0) {
          ModEvent me = k[i].lq(home, v->noe);
          if (me_failed(me)) {
            failed(true);
            return false;
          }
          modified |= me_modified(me);
        }

      if (v->noe > 0) {

        if (isView) {
          ModEvent me = k[i].lq(home, v->noe);
          if (me_failed(me)) {
            failed(true);
            return false;
          }
          modified |= me_modified(me);
        }

        // If the maximum number of occurences of a value is reached
        // it cannot be consumed by another view

        if (v->kcount() == v->kmax()) {
          int vidx = v->kindex();

          k[i].counter(v->kcount());

          if (isView) {
            if (!k[i].assigned()) {
              ModEvent me = k[i].eq(home, k[i].counter());
              if (me_failed(me)) {
                failed(true);
                return false;
              }
              modified |= me_modified(me);
            }
          }

          bool delall = false;
          if (v->card_conflict() &&
              v->noe > v->kmax()) {
            delall = true;

          }

          for (Edge* e = v->last(); e != NULL; e = e->vprev()) {
            VarNode* vrn = e->getVar();
            if (vrn->noe == 1) {
              vrn->noe--;
              v->noe--;
              int vi= vrn->get_info();

              int n = x.size();
              x[vi] = x[--n];
              //              x[vi].index(vi);
              x.size(n);

              vars[vi] = vars[--n_var];
              vars[vi]->set_info(vi);
              node_size--;
              e->del_edge();
              e->unlink();

            } else {
              if (delall) {
                ModEvent me = x[vrn->get_info()].nq(home, v->val);
                if (me_failed(me)) {
                  failed(true);
                  return false;
                }
                modified |= me_modified(me);
                vrn->noe--;
                v->noe--;
                e->del_edge();
                e->unlink();
              }
            }
          }
          v->template set_cap<UBC>(0);
          v->template set_cap<LBC>(0);
          v->set_maxlow(0);
          if (sum_min && sum_min >= k[vidx].min()) {
            sum_min -= k[vidx].min();
          }
          assert(sum_min >=0);

          if (sum_max && sum_max >= k[vidx].max()) {
            sum_max -= k[vidx].max();
          }
          assert(sum_max >=0);

        } else {
          int cur = v->kcount();
          if (cur > 0) {
            v->kcount(0);
          }
        }
      }
    }
    for (int i = n_var; i--; )
      vars[i]->set_info(i);

    for (int i = n_val; i--; ) {
      if (vals[i]->noe == 0) {
        vals[i]->template set_cap<UBC>(0);
        vals[i]->template set_cap<LBC>(0);
        vals[i]->set_maxlow(0);
      }
      vals[i]->set_info(n_var + i);
    }

    for (int i = n_var; i--; )
      if (vars[i]->noe > 1)
        for (Edge* e = vars[i]->first(); e != NULL; e = e->next()) {
          bool keepedge = false;
          keepedge =  (e->template matched<direction>() ||
                       e->template used<direction>());
          if (!keepedge) {
            ValNode* v = e->getVal();
            ModEvent me = x[i].nq(home, v->val);
            if (me_failed(me)) {
              failed(true);
              return false;
            }
            modified |= me_modified(me);
          } else {
            e->template free<direction>();
          }
        }
    return modified;
  }

  template <class View, class Card, bool isView>  template <BC direction>
  inline bool
  VarValGraph<View, Card, isView>::maximum_matching(Space& home) {

    int required_size = 0;
    int card_match    = 0;

    if (direction == UBC) {
      required_size = n_var;
    } else {
      required_size = sum_min;
    }

    // find an intial matching in O(n*d)
    // greedy algorithm

    for (int i = n_val; i--; ) {
      ValNode* vln = vals[i];
      for (Edge* e = vln->first(); e != NULL ; e = e->vnext()) {
        VarNode* vrn = e->getVar();
        if (!vrn->template matched<direction>() &&
            !vln->template matched<direction>()) {
          e->template match<direction>();
          card_match++;
        }
      }
    }

    Region r(home);
    if (card_match < required_size) {
      if (direction == LBC) {
        // collect free value nodes
        ValNode** free = r.alloc<ValNode*>(n_val);
        int f = 0;
        // find failed nodes
        for (int i = n_val; i--; ) {
          ValNode* vln = vals[i];
          if (!vln->template matched<direction>()) {
            free[f++] = vln;
          }
        }

        for (int i = 0; i < f; i++) {
          while(!free[i]->template matched<direction>()) {
            if (augmenting_path<direction>(home,free[i])) {
              card_match++;
            } else {
              break;
            }
          }
        }
      } else {
        VarNode** free = r.alloc<VarNode*>(n_var);
        int f = 0;
        // find failed nodes
        for (int i = n_var; i--; ) {
          VarNode* vrn = vars[i];
          if (!vrn->template matched<direction>()) {
            free[f++] = vrn;
          }
        }

        for (int i = 0; i < f; i++) {
          if (!free[i]->template matched<direction>()) {
            if (augmenting_path<direction>(home,free[i])) {
              card_match++;
            }
          }
        }
      }
    }
    return (card_match >= required_size);
  }

  template <class View, class Card, bool isView> template<BC direction>
  inline bool
  VarValGraph<View, Card, isView>::augmenting_path(Space& home, VVGNode* v) {
    Region r(home);
    Support::StaticStack<VVGNode*,Region> ns(r,node_size);
    bool* visited = r.alloc<bool>(node_size);
    Edge** start = r.alloc<Edge*>(node_size);

    // augmenting path starting in a free var node
    assert(!v->is_matched(direction));

    // keep track of the nodes that have already been visited
    VVGNode* sn = v;

    // mark the start partition
    bool sp = sn->get_type();

    // nodes in sp only follow free edges
    // nodes in V - sp only follow matched edges

    for (int i = node_size; i--; )
      visited[i] = false;

    for (int i = node_size; i--; )
      if (i >= n_var) {
        vals[i - n_var]->inedge(NULL);
        start[i]   = vals[i - n_var]->first();
      } else {
        vars[i]->inedge(NULL);
        start[i]   = vars[i]->first();
      }

    v->inedge(NULL);
    ns.push(v);
    visited[v->get_info()] = true;
    while (!ns.empty()) {
      VVGNode* v = ns.top();
      Edge* e = NULL;
      if (v->get_type() == sp) {
        // follow next free edge
        e = start[v->get_info()];
        while (e != NULL && e->template matched<direction>()) {
          e = e->next(v->get_type());
        }
      } else {
        e = start[v->get_info()];
        while (e != NULL && !e->template matched<direction>()) {
          e = e->next(v->get_type());
        }
        start[v->get_info()] = e;
      }
      if (e != NULL) {
        start[v->get_info()] = e->next(v->get_type());
        VVGNode* w = e->getMate(v->get_type());
        if (!visited[w->get_info()]) {
          // unexplored path
          if (!w->is_matched(direction) && w->get_type() != sp) {
            if (v->inedge() != NULL) {
              // augmenting path of length l > 1
              e->template match<direction>();
              break;
            } else {
              // augmenting path of length l = 1
              e->template match<direction>();
              ns.pop();
              return true;
            }
          } else {
            w->inedge(e);
            visited[w->get_info()] = true;
            // find matching edge m incident with w
            ns.push(w);
          }
        }
      } else {
        // tried all outgoing edges without finding an augmenting path
        ns.pop();
      }
    }

    bool pathfound = false;
    if (!ns.empty()) {
      pathfound = true;
    }

    while (!ns.empty()) {
      VVGNode* t = ns.top();
      if (t != sn) {
        Edge* in   = t->inedge();
        if (t->get_type() != sp) {
          assert(in != NULL);
          in->template match<direction>();
        } else {
          // avoid defects
          if (!sp) {
            in->template unmatch<direction>(!sp);
          } else {
            in->template unmatch<direction>();
          }
        }
        ns.pop();
      } else {
        ns.pop();
      }
    }
    return pathfound;
  }

  template <class View, class Card, bool isView> template<BC direction>
  inline void
  VarValGraph<View, Card, isView>::free_alternating_paths(Space& home) {
    Region r(home);
    Support::StaticStack<VVGNode*,Region> ns(r,node_size);
    bool* visited = r.alloc<bool>(node_size);
    // keep track of the nodes that have already been visited
    for (int i = node_size; i--; )
      visited[i] = false;

    if (direction == LBC) {
      // after a maximum matching on the value nodes there still can be
      // free value nodes, hence we have to consider ALL nodes whether
      // they are the starting point of an even alternating path in G
      for (int i = n_var; i--; ){
        if(!vars[i]->is_matched(LBC)){
          // unmatched var-node
          ns.push(vars[i]);
          visited[vars[i]->get_info()] = true;
        }
      }
      for (int i = n_val; i--; ){
        if(!vals[i]->is_matched(LBC)){
          // unmatched val-node
          ns.push(vals[i]);
          visited[vals[i]->get_info()] = true;
        }
      }

    } else {
      // clearly, after a maximum matching on the x variables
      // corresponding to a set cover on x there are NO free var nodes
      //       std::cout << "alt_path for ubm: \n";
      // after  max_match_ub there can only be free val-nodes
      for (int i = n_val; i--; ){
        if(!vals[i]->is_matched(UBC)){
          // still capacities left
          ns.push(vals[i]);
          visited[vals[i]->get_info()] = true;
        }
      }
    }

    while (!ns.empty()){
      VVGNode* node = ns.top();
      ns.pop();
      if (node->get_type()) {
        // ValNode
        ValNode* vln = static_cast<ValNode*>(node);
        for (Edge* cur = vln->first(); cur != NULL; cur = cur->vnext()) {
          VarNode* mate = cur->getVar();
          bool follow = false;
          switch (direction) {
            // edges in M_l are directed from values to variables
          case LBC:
            follow = cur->template matched<direction>();
            break;
          case UBC:
            follow = !cur->template matched<direction>();
            break;
          default: GECODE_NEVER;
          }
          if (follow) {
            // mark the edge
            cur->template use<direction>();
            if (!visited[mate->get_info()]) {
              ns.push(mate);
              visited[mate->get_info()] = true;
            }
          }
        }
      } else {
        // VarNode
        VarNode* vrn = static_cast<VarNode*>(node);
        switch (direction) {
          // after LBC-matching we can follow every unmatched edge
        case LBC: {
          for (Edge* cur = vrn->first(); cur != NULL; cur = cur->next()){
            ValNode* mate = cur->getVal();
            if (!cur->template matched<LBC>()) {
              cur->template use<LBC>();
              if (!visited[mate->get_info()]) {
                ns.push(mate);
                visited[mate->get_info()] = true;
              }
            }
          }
          break;
        }
          // after ub-matching we can only follow a matched edge
        case UBC: {
          Edge* cur = vrn->template get_match<UBC>();
          if (cur != NULL) {
            cur->template use<UBC>();
            ValNode* mate = cur->getVal();
            if (!visited[mate->get_info()]) {
              ns.push(mate);
              visited[mate->get_info()] = true;
            }
          }
          break;
        }
        default: GECODE_NEVER;
        }
      }
    }
  }

  template <class View, class Card, bool isView> template <BC direction>
  inline void
  VarValGraph<View, Card, isView>::dfs(VVGNode* v,
                                       bool inscc[],
                                       bool in_unfinished[],
                                       int dfsnum[],
                                       Support::StaticStack<VVGNode*,Region>& roots,
                                       Support::StaticStack<VVGNode*,Region>& unfinished,
                                       int& count){
    count++;
    int v_index            = v->get_info();
    dfsnum[v_index]        = count;
    inscc[v_index]         = true;
    in_unfinished[v_index] = true;

    unfinished.push(v);
    roots.push(v);
    for (Edge* e = v->first(); e != NULL; e = e->next(v->get_type())) {
      bool condition = false;
      // LBC-matching
      if (direction == LBC) {
        // ValNode
        if (v->get_type()) {
          condition = e->template matched<LBC>();
        } else {
          condition = !e->template matched<LBC>();
        }
        // UBC - matching
      } else {
        if (v->get_type()) {
          // in an upper bound matching a valnode only can follow unmatched edges
          condition = !e->template matched<UBC>();
        } else {
          condition = e->template matched<UBC>();
        }
      }
      if (condition) {
        VVGNode* w = e->getMate(v->get_type());
        int w_index = w->get_info();

        assert(w_index < node_size);
        if (!inscc[w_index]) {
          // w is an uncompleted scc
          w->inedge(e);
          dfs<direction>(w, inscc, in_unfinished, dfsnum,
                         roots, unfinished, count);
        } else {
          if (in_unfinished[w_index]) {
            // even alternating cycle found mark the edge closing the cycle,
            // completing the scc
            e->template use<direction>();
            // if w belongs to an scc we detected earlier
            // merge components
            assert(roots.top()->get_info() < node_size);
            while (dfsnum[roots.top()->get_info()] > dfsnum[w_index]) {
              roots.pop();
            }
          }
        }
      }
    }

    if (v == roots.top()) {
      while (v != unfinished.top()) {
        // w belongs to the scc with root v
        VVGNode* w = unfinished.top();
        Edge* ie = w->inedge();
        ie->template use<direction>();
        in_unfinished[w->get_info()] = false;
        unfinished.pop();
      }
      assert(v == unfinished.top());
      in_unfinished[v_index] = false;
      roots.pop();
      unfinished.pop();
    }
  }

  template <class View, class Card, bool isView> template <BC direction>
  inline void
  VarValGraph<View, Card, isView>::strongly_connected_components(Space& home) {
    Region r(home);
    bool* inscc = r.alloc<bool>(node_size);
    bool* in_unfinished = r.alloc<bool>(node_size);
    int* dfsnum = r.alloc<int>(node_size);

    for (int i = node_size; i--; ) {
      inscc[i]         = false;
      in_unfinished[i] = false;
      dfsnum[i]        = 0;
    }

    int count = 0;
    Support::StaticStack<VVGNode*,Region> roots(r,node_size);
    Support::StaticStack<VVGNode*,Region> unfinished(r,node_size);

    for (int i = n_var; i--; )
      dfs<direction>(vars[i], inscc, in_unfinished, dfsnum,
                     roots, unfinished, count);
  }

  template <class View, class Card, bool isView>
  forceinline
  VarValGraph<View, Card, isView>::~VarValGraph(void){
    heap.rfree(mem);
  }

  template <class View, class Card, bool isView>
  forceinline void*
  VarValGraph<View, Card, isView>::operator new(size_t t){
    return heap.ralloc(t);
  }

  template <class View, class Card, bool isView>
  forceinline void
  VarValGraph<View, Card, isView>::operator delete(void* p){
    heap.rfree(p);
  }


}}}

// STATISTICS: int-prop