graph.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2003
 *
 *  Last modified:
 *     $Date: 2011-09-07 16:15:16 +0200 (Wed, 07 Sep 2011) $ by $Author: schulte $
 *     $Revision: 12394 $
 *
 *  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.
 *
 */

#include <climits>

namespace Gecode { namespace Int { namespace ViewValGraph {

  template<class View>
  forceinline
  Graph<View>::Graph(void)
    : view(NULL), val(NULL), n_view(0), n_val(0), count(1U) {}

  template<class View>
  forceinline bool
  Graph<View>::initialized(void) const {
    return view != NULL;
  }

  template<class View>
  forceinline void
  Graph<View>::init(Space& home, ViewNode<View>* x) {
    Edge<View>** edge_p = x->val_edges_ref();
    ViewValues<View> xi(x->view());
    ValNode<View>** v = &val;
    while (xi() && (*v != NULL)) {
      if ((*v)->val() == xi.val()) {
        // Value node does already exist, create new edge
        *edge_p = new (home) Edge<View>(*v,x);
        edge_p = (*edge_p)->next_edge_ref();
        v = (*v)->next_val_ref();
        ++xi;
      } else if ((*v)->val() < xi.val()) {
        // Skip to next value node
        v = (*v)->next_val_ref();
      } else {
        // Value node does not yet exist, create and link it
        ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
        *v = nv; v = nv->next_val_ref();
        *edge_p = new (home) Edge<View>(nv,x);
        edge_p = (*edge_p)->next_edge_ref();
        ++xi; n_val++;
      }
    }
    // Create missing value nodes
    while (xi()) {
      ValNode<View>* nv = new (home) ValNode<View>(xi.val(),*v);
      *v = nv; v = nv->next_val_ref();
      *edge_p = new (home) Edge<View>(nv,x);
      edge_p = (*edge_p)->next_edge_ref();
      ++xi; n_val++;
    }
    *edge_p = NULL;
  }

  template<class View>
  forceinline bool
  Graph<View>::match(ViewNodeStack& m, ViewNode<View>* x) {
    count++;
  start:
    // Try to find matching edge cheaply: is there a free edge around?
    {
      Edge<View>* e = x->val_edges();
      // This holds true as domains are never empty
      assert(e != NULL);
      do {
        if (!e->val(x)->matching()) {
          e->revert(x); e->val(x)->matching(e);
          // Found a matching, revert all edges on stack
          while (!m.empty()) {
            x = m.pop(); e = x->iter;
            e->val(x)->matching()->revert(e->val(x));
            e->revert(x); e->val(x)->matching(e);
          }
          return true;
        }
        e = e->next_edge();
      } while (e != NULL);
    }
    // No, find matching edge by augmenting path method
    Edge<View>* e = x->val_edges();
    do {
      if (e->val(x)->matching()->view(e->val(x))->min < count) {
        e->val(x)->matching()->view(e->val(x))->min = count;
        m.push(x); x->iter = e;
        x = e->val(x)->matching()->view(e->val(x));
        goto start;
      }
    next:
      e = e->next_edge();
    } while (e != NULL);
    if (!m.empty()) {
      x = m.pop(); e = x->iter; goto next;
    }
    // All nodes and edges unsuccessfully tried
    return false;
  }

  template<class View>
  forceinline void
  Graph<View>::purge(void) {
    if (count > (UINT_MAX >> 1)) {
      count = 1;
      for (int i=n_view; i--; )
        view[i]->min = 0;
      for (ValNode<View>* v = val; v != NULL; v = v->next_val())
        v->min = 0;
    }
  }

  template<class View>
  forceinline void
  Graph<View>::scc(Space& home) {
    Region r(home);

    Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view);
    Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view);
      
    count++;
    unsigned int cnt0 = count;
    unsigned int cnt1 = count;
    
    for (int i = n_view; i--; )
      /*
       * The following test is subtle: for scc, the test should be:
       *   view[i]->min < count
       * However, if view[i] < count-1, then the node has already been
       * reached on a path and all edges connected to the node have been
       * marked anyway! So just ignore this node altogether for scc.
       */ 
      if (view[i]->min < count-1) {
        Node<View>* w = view[i];
      start:
        w->low = w->min = cnt0++;
        scc.push(w);
        Edge<View>* e = w->edge_fst();
        while (e != w->edge_lst()) {
          if (e->dst(w)->min < count) {
            visit.push(w); w->iter = e;
            w=e->dst(w);
            goto start;
          }
        next:
          if (e->dst(w)->low < w->min)
            w->min = e->dst(w)->low;
          e = e->next();
        }
        if (w->min < w->low) {
          w->low = w->min;
        } else {
          Node<View>* v;
          do {
            v = scc.pop();
            v->comp = cnt1;
            v->low  = UINT_MAX;
          } while (v != w);
          cnt1++;
        }
        if (!visit.empty()) {
          w=visit.pop(); e=w->iter; goto next;
        }
      }
    count = cnt0+1;
  }


}}}

// STATISTICS: int-prop