Method path

gecode/int/circuit/base.hpp:235–286

  template<class View, class Offset>
  ExecStatus
  Base<View,Offset>::path(Space& home) {
    // Prunes that partial assigned paths are not completed to cycles

    int n=x.size();

    Region r;

    // The path starting at assigned x[i] ends at x[end[j]] which is
    // not assigned.
    int* end = r.alloc<int>(n);
    for (int i=0; i<n; i++)
      end[i]=-1;

    // A stack that records all indices i such that end[i] != -1
    Support::StaticStack<int,Region> tell(r,n);

    typedef typename Offset::ViewType OView;
    for (int i=0; i<y.size(); i++) {
      assert(!y[i].assigned());
      // Non-assigned views serve as starting points for assigned paths
      Int::ViewValues<OView> v(o(y[i]));
      // Try all connected values
      do {
        int j0=v.val();
        // Starting point for not yet followed assigned path found
        if (x[j0].assigned() && (end[j0] < 0)) {
          // Follow assigned path until non-assigned view:
          // all assigned view on the paths can be skipped, as
          // if x[i] is assigned to j, then x[j] will only have
          // x[i] as predecessor due to propagating distinct.
          int j = j0;
          do {
            j=o(x[j]).val();
          } while (x[j].assigned());
          // Now there cannot be a cycle from x[j] to x[v.val()]!
          // However, the tell cannot be done here as j might be
          // equal to i and might hence kill the iterator v!
          end[j0]=j; tell.push(j0);
        }
        ++v;
      } while (v());
    }

    // Now do the tells based on the end information
    while (!tell.empty()) {
      int i = tell.pop();
      assert(end[i] >= 0);
      GECODE_ME_CHECK(o(x[end[i]]).nq(home,i));
    }
    return ES_NOFIX;
  }

  template<class View, class Offset>
  forceinline size_t