5.397. symmetric_alldifferent_loop
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , , , .
- Argument
- Restrictions
- Purpose
All variables associated with the attribute of the collection should be pairwise distinct. In addition enforce the following condition: if variable is assigned value then variable is assigned value . Note that and are not necessarily distinct. This can be interpreted as a graph-covering problem where one has to cover a digraph with circuits of length two or one in such a way that each vertex of belongs to a single circuit.
- Example
-
The constraint holds since:
We have two loops respectively corresponding to and .
We have one circuit of length 2 corresponding to .
FigureΒ 5.397.1 provides a second example involving a constraint.
Figure 5.397.1. (A)Β Magic square Duerer where cells that belong to a same cycle are coloured identically by a colour different from grey; each cell has an index in its upper left corner (in red) and a value (in blue). (B)Β Corresponding graph where there is an arc from node to node if and only if the value of cell is equal to the index of cell . (C)Β Collection of nodes passed to the constraint: the four self-loops of the graph correspond to the four grey cells of the magic square such that the value of the cell (in blue) is equal to the index of the cell (in red).
- All solutions
FigureΒ 5.397.2 gives all solutions to the following non ground instance of the constraint: , , , , , .
Figure 5.397.2. All solutions corresponding to the non ground example of the constraint of the All solutions slot; the attribute is displayed as indices of the attribute and self loops are coloured in red.
- Typical
- Symmetry
Items of are permutable.
- Algorithm
An arc-consistency filtering algorithm for the constraint is described inΒ [Cymer13], [CymerPhD13]. The algorithm is based on the following ideas:
First, one can map solutions of the constraint to perfect -matchings in a non-bipartite graph derived from the domain of the variables of the constraint where , for vertices which have a self-loop, and for all the remaining vertices. A perfect -matching of a graph is a subset of edges such that every vertex is incident with the number of edges in between and .
Second, Gallai-Edmonds decompositionΒ [Gallai63], [Edmonds65] allows to find out all edges that do not belong any perfect -matchings, and therefore prune the corresponding variables.
- Counting
-
Length () 2 3 4 5 6 7 8 9 10 Solutions 2 4 10 26 76 232 764 2620 9496 Number of solutions for : domains
- See also
-
implies: .
- Keywords
characteristic of a constraint: all different, disequality.
combinatorial object: permutation, involution, matching.
constraint type: graph constraint, graph partitioning constraint.
- Cond. implications
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph model
In order to express the binary constraint that links two vertices one has to make explicit the identifier of the vertices.
PartsΒ (A) andΒ (B) of FigureΒ 5.397.3 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the arcs of the final graph are stressed in bold.
Figure 5.397.3. Initial and final graph of the constraint
(a) (b) - Signature
Since all the attributes of the collection are distinct, and because of the first condition of the arc constraint, each vertex of the final graph has at most one successor. Therefore the maximum number of arcs of the final graph is equal to the maximum number of vertices of the final graph. So we can rewrite to and simplify to .