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()); } }; _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
