[gecode-users] Path constraint

[Philippe]

Hi,


This mail refers to the previous post :
(http://permalink.gmane.org/gmane.comp.lib.gecode.user/4754) 
Unfortunately, I can't reply to it (when i click on "reply" 
I get a html page with the text "No such file" in it).

Here is the problem : I have a adjacency matrix in which there are cycles.
These cycles prevent the existence of a path between a start node and end
node. (This happens for instance with the code below.) Is there a way to 
solve this problem without the existence of the subpath constraint (since 
not all nodes has to be visited) ? 

I know the paper "Explaining circuit propagation" but I have neither the 
time nor (probably) the level to code the "subpath" myself. 
The problem I am facing is severe since a lot of work has already be 
done and a milestones is now rapidly coming.


Any help will be greatly appreciated,
Thanks
Philippe


class TestPath : public Gecode::Space {
 
public:

      TestPath():
        _nb_nodes(4), 
        _end(_nb_nodes),                          // end mark
      _Flow(*this, _nb_nodes * _nb_nodes, 0, 1),  // Square matrix
      _s(*this, 0, _nb_nodes),                    // Domain = [0, nb_nodes]
      _e(*this, 0, _nb_nodes)                     //
   { 
        int index_end   = (_nb_nodes - 2);
        int index_start = (_nb_nodes - 1);
        Matrix<IntVarArray> flow(_Flow, _nb_nodes, _nb_nodes);

        // Start has necessary a successor
       rel(*this, sum(flow.col(index_start)) == 1);

        // Start has no predecessor
       rel(*this, sum(flow.row(index_start)) == 0);

        // End has no successor
       rel(*this, sum(flow.col(index_end)) == 0);

        for (int i = 0 ; i < _nb_nodes ; ++i)
        {
            IntVar in = expr(*this, sum(flow.row(i)));
            IntVar out = expr(*this, sum(flow.col(i)));

            rel(*this, in <= 1);
            rel(*this, out <= 1);

              // No trivial cycle
              rel(*this, flow(i, i) == 0);

              if (i != index_end && i != index_start)
              {
                  // Flow conservation
                  IntVar in = expr(*this, sum(flow.row(i)));
                  IntVar out = expr(*this, sum(flow.col(i)));
                  rel(*this, in == out);
              }
        }
        // ------------------------------------------------------------
        // Then, some other constraints  
        // will set the flow(i,j) to 0
        // ------------------------------------------------------------

        // ------------------------------------------------------------
        // Anyway, that is not sufficent since we have cycle (or invalid 
        // path),
        // for instance
        // Start->End  Node1<->Node2
        // -------------------------------------------------------------
        // what we want is a path that goes from Start to End but not 
        // necessary passing through all nodes. Is a flow sufficent ?
        // ------------------------------------------------------------
      branch(*this, _Flow, INT_VAR_SIZE_MIN(), INT_VAL_MAX());
   }

};