The algorithm iterates until no more such changes are possible. A unary operation, inverse, is also used in the algorithm. We designed and experimentally evaluated techniques for improving the efficiency of a path consistency algorithm. Intersection was made efficient by implementing the labels as bit vectors. The intersection of two labels is then simply the logical AND of two integers.
Composition is harder to make efficient.
We experimentally compared two practical methods for composition that have been proposed in the literature. The composition of two labels is computed by a nested loop that forms the union of the pairwise composition of the basic relations in the labels. In our experiments, the implementations of the two methods differed only in how composition was computed. We also experimentally evaluated methods for reducing the number of composition operations that need to be performed. One idea we examined for improving the efficiency is to avoid the computation when it can be predicted that the result will not constrain the label on the edge that completes the triangle.