This function creates and returns a path constraint. Like other Solver constraints, this one must be posted in order to be taken into account.

What IlcPathLength Does Not Do

The constraint that this function returns does not determine whether there is a path between nodes in a graph; rather, it constrains accumulations (such as flow) along a path. The filtering algorithm associated with this constraint works on the accumulation variables in the array lengths.

If you are looking for a Hamiltonian path, for example, (that is, one in which each node is visited exactly once), consider using instead the constraint IlcAllDiff on the variables in the array next.

What IlcPathLength Does

If we are given

• a set of n nodes, known as N,
• a maximum number of paths among those nodes, maxNbPaths,
• a set of maxNbPaths nodes, known as S, for starting nodes,
• a set of maxNbPaths nodes, known as E, for ending nodes,

then a path constraint insures that there exist at most maxNbPaths paths starting from a node in S, visiting nodes in N, and ending at a node in E. Furthermore, each node will be visited only once, has only one predecessor and only one successor, and each node belongs to a path that starts from a node in S and ends at a node in E.

In particular, in the function IlcPathLength, in the arrays next and lengths,

• the indices in [0, n-1] correspond to the nodes of N,
• the indices in [n, n+maxNbPaths-1] correspond to the nodes of E,
• and the indices in [n+maxNbPaths, n+2*maxNbPaths-1] correspond to the nodes of S.

In other words, the size of next and lengths is n+2*maxNbPaths.

next[i] is the node following node i on the current path. lengths[i] is the accumulated cost from the beginning of the path to node i. The argument transit indicates the transition function.

When you post this constraint, it insures that for all indices i in the range [0, n-1] or in [n+maxNbPaths, n+2*maxNbPaths-1], if next[i]==j and j is in [0, n+maxNbPaths-1], then lengths[i] + transit.transit(i,j) <= lengths[j].

When i is in the range [n, n+maxNbPaths-1], next[i] has no meaning because the nodes in E do not have successors, of course. In this case, the constraint deals with them by setting next[i] to i+maxNbPaths (that is, nodes of S).

The argument event can take one of two values: IlcWhenValue or IlcWhenDomain (values of the enumeration IlcWhenEvent). The behavior of the constraint depends on the chosen value.

• IlcWhenValue means that the constraint is associated with the value propagation event of each one of the constrained variables of next.
• IlcWhenDomain means that the constraint is associated with the domain propagation event of each one of the constrained variables of next. This choice causes more domain reduction than the preceding choice and in consequence takes longer to run.

If you set the number of paths to zero (maxNbPaths = 0), then you can have as many paths as needed, in case you do not know the number in advance. In such a case, a node i is at the end of a path if next[i]>=next.getSize(). Solver recognizes the starting node of such a path by the fact that there is no node j such that next[j]==i.