5.170. inverse

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πš’πš—πšŸπšŽπš›πšœπšŽ(π™½π™Ύπ™³π™΄πš‚)

Synonyms

πšŠπšœπšœπš’πšπš—πš–πšŽπš—πš, πšŒπš‘πšŠπš—πš—πšŽπš•, πš’πš—πšŸπšŽπš›πšœπšŽ_πšŒπš‘πšŠπš—πš—πšŽπš•πš’πš—πš.

Argument
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›,πš™πš›πšŽπš-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌,πš™πš›πšŽπš])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
π™½π™Ύπ™³π™΄πš‚.πš™πš›πšŽπšβ‰₯1
π™½π™Ύπ™³π™΄πš‚.πš™πš›πšŽπšβ‰€|π™½π™Ύπ™³π™΄πš‚|
Purpose

Enforce each vertex of a digraph to have exactly one predecessor and one successor. In addition the following two statements are equivalent:

  1. The successor of the i th node is the j th node.

  2. The predecessor of the j th node is the i th node.

Example
πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-2πš™πš›πšŽπš-2,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-1πš™πš›πšŽπš-1,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-5πš™πš›πšŽπš-4,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-3πš™πš›πšŽπš-5,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-4πš™πš›πšŽπš-3

The πš’πš—πšŸπšŽπš›πšœπšŽ constraint holds since:

  • π™½π™Ύπ™³π™΄πš‚[1].𝚜𝚞𝚌𝚌=2β‡”π™½π™Ύπ™³π™΄πš‚[2].πš™πš›πšŽπš=1,

  • π™½π™Ύπ™³π™΄πš‚[2].𝚜𝚞𝚌𝚌=1β‡”π™½π™Ύπ™³π™΄πš‚[1].πš™πš›πšŽπš=2,

  • π™½π™Ύπ™³π™΄πš‚[3].𝚜𝚞𝚌𝚌=5β‡”π™½π™Ύπ™³π™΄πš‚[5].πš™πš›πšŽπš=3,

  • π™½π™Ύπ™³π™΄πš‚[4].𝚜𝚞𝚌𝚌=3β‡”π™½π™Ύπ™³π™΄πš‚[3].πš™πš›πšŽπš=4,

  • π™½π™Ύπ™³π™΄πš‚[5].𝚜𝚞𝚌𝚌=4β‡”π™½π™Ύπ™³π™΄πš‚[4].πš™πš›πšŽπš=5.

Typical
|π™½π™Ύπ™³π™΄πš‚|>1
Symmetries
  • Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

  • Attributes of π™½π™Ύπ™³π™΄πš‚ are permutable w.r.t. permutation (πš’πš—πšπšŽπš‘) (𝚜𝚞𝚌𝚌,πš™πš›πšŽπš) (permutation applied to all items).

Usage

This constraint is used in order to make the link between the successor and the predecessor variables. This is sometimes required by specific heuristics that use both predecessor and successor variables. In some problems, the successor and predecessor variables are respectively interpreted as column an row variables (i.e.,Β we have a bijection between the successor variables and their values). This is for instance the case in the n-queens problem (i.e.,Β place n queens on a n by n chessboard in such a way that no two queens are on the same row, the same column or the same diagonal) when we use the following model: to each column of the chessboard we associate a variable that gives the row where the corresponding queen is located. Symmetrically, to each row of the chessboard we create a variable that indicates the column where the associated queen is placed. Having these two sets of variables, we can now write a heuristics that selects the column or the row for which we have the fewest number of alternatives for placing a queen.

Remark

In the original πš’πš—πšŸπšŽπš›πšœπšŽ constraint of CHIP the πš’πš—πšπšŽπš‘ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list, the first position being 1. This is also the case for SICStus Prolog, JaCoP and Gecode where the variables are respectively indexed from 1, 0 and 0. Within SICStus Prolog and JaCoP (http://www.jacop.eu/), the πš’πš—πšŸπšŽπš›πšœπšŽ constraint is called πšŠπšœπšœπš’πšπš—πš–πšŽπš—πš. Within Gecode, it is called πšŒπš‘πšŠπš—πš—πšŽπš• (http://www.gecode.org/).

Algorithm

We can reuse the filtering algorithm associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, both for the successor and the predecessor variables. In addition, each time value j is removed from the i th successor variable, we have to remove value i from the j th predecessor variable. Similarly, each time value i is removed from the j th successor variable, we have also to remove value j from the i th predecessor variable.

Systems

inverseChanneling in Choco, channel in Gecode, assignment in SICStus.

See also

common keyword: πšŒπš’πšŒπš•πšŽ, πšœπš’πš–πš–πšŽπšπš›πš’πšŒ_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation).

generalisation: πš’πš—πšŸπšŽπš›πšœπšŽ_𝚘𝚏𝚏𝚜𝚎𝚝 (do not assume anymore that the smallest value of the πš™πš›πšŽπš or 𝚜𝚞𝚌𝚌 attributes is equal to 1), πš’πš—πšŸπšŽπš›πšœπšŽ_𝚜𝚎𝚝 (πšπš˜πš–πšŠπš’πš— πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by 𝚜𝚎𝚝 πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ), πš’πš—πšŸπšŽπš›πšœπšŽ_πš πš’πšπš‘πš’πš—_πš›πšŠπš—πšπšŽΒ (partial mapping between two collections of distinct size).

Keywords

characteristic of a constraint: automaton, automaton with array of counters.

combinatorial object: permutation.

constraint type: graph constraint.

filtering: arc-consistency.

heuristics: heuristics.

modelling: channelling constraint, permutation channel, dual model.

modelling exercises: n-Amazon, zebra puzzle.

puzzles: n-Amazon, n-queen, zebra puzzle.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
β€’ πš—πš˜πšπšŽπšœ2.πš™πš›πšŽπš=πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘
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. This is why the πš’πš—πšŸπšŽπš›πšœπšŽ constraint considers objects that have three attributes:

  • One fixed attribute πš’πš—πšπšŽπš‘ that is the identifier of the vertex,

  • One variable attribute 𝚜𝚞𝚌𝚌 that is the successor of the vertex,

  • One variable attribute πš™πš›πšŽπš that is the predecessor of the vertex.

PartsΒ (A) andΒ (B) of FigureΒ 5.170.1 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.170.1. Initial and final graph of the πš’πš—πšŸπšŽπš›πšœπšŽ constraint
ctrs/inverseActrs/inverseB
(a) (b)
Signature

Since all the πš’πš—πšπšŽπš‘ attributes of the π™½π™Ύπ™³π™΄πš‚ collection are distinct and because of the first condition πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘ of the arc constraint all the vertices of the final graph have at most one predecessor.

Since all the πš’πš—πšπšŽπš‘ attributes of the π™½π™Ύπ™³π™΄πš‚ collection are distinct and because of the second condition πš—πš˜πšπšŽπšœ2.πš™πš›πšŽπš=πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘ of the arc constraint all the vertices of the final graph have at most one successor.

From the two previous remarks it follows that the final graph is made up from disjoint paths and disjoint circuits. Therefore the maximum number of arcs of the final graph is equal to its maximum number of vertices π™½π™Ύπ™³π™΄πš‚. So we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™½π™Ύπ™³π™΄πš‚| to 𝐍𝐀𝐑𝐂β‰₯|π™½π™Ύπ™³π™΄πš‚| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.170.2 depicts the automaton associated with the πš’πš—πšŸπšŽπš›πšœπšŽ constraint. To each item of the collection π™½π™Ύπ™³π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 1.

Figure 5.170.2. Automaton of the πš’πš—πšŸπšŽπš›πšœπšŽ constraint
ctrs/inverse1