5.122. element_sparse

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ(π™Έπšƒπ™΄π™Ό,πšƒπ™°π™±π™»π™΄,π™³π™΄π™΅π™°πš„π™»πšƒ)

Usual name

πšŽπš•πšŽπš–πšŽπš—πš

Arguments
π™Έπšƒπ™΄π™ΌπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›)
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πš’πš—πš)
π™³π™΄π™΅π™°πš„π™»πšƒπš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Ό,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘β‰₯1
|π™Έπšƒπ™΄π™Ό|=1
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,[πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ])
πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘β‰₯1
πšπš’πšœπšπš’πš—πšŒπš(πšƒπ™°π™±π™»π™΄,πš’πš—πšπšŽπš‘)
Purpose

π™Έπšƒπ™΄π™Ό[1].πšŸπšŠπš•πšžπšŽ is equal to one of the entries of the table πšƒπ™°π™±π™»π™΄ or to the default value π™³π™΄π™΅π™°πš„π™»πšƒ if the entry π™Έπšƒπ™΄π™Ό[1].πš’πš—πšπšŽπš‘ does not exist in πšƒπ™°π™±π™»π™΄.

Example
πš’πš—πšπšŽπš‘-2 πšŸπšŠπš•πšžπšŽ-5,πš’πš—πšπšŽπš‘-1πšŸπšŠπš•πšžπšŽ-6,πš’πš—πšπšŽπš‘-2πšŸπšŠπš•πšžπšŽ-5,πš’πš—πšπšŽπš‘-4πšŸπšŠπš•πšžπšŽ-2,πš’πš—πšπšŽπš‘-8πšŸπšŠπš•πšžπšŽ-9,5

The πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ constraint holds since its first argument π™Έπšƒπ™΄π™Ό corresponds to the second item of the πšƒπ™°π™±π™»π™΄ collection.

Typical
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
Symmetries
  • Items of πšƒπ™°π™±π™»π™΄ are permutable.

  • All occurrences of two distinct values in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ, πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ or π™³π™΄π™΅π™°πš„π™»πšƒ can be swapped; all occurrences of a value in π™Έπšƒπ™΄π™Ό.πšŸπšŠπš•πšžπšŽ, πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ or π™³π™΄π™΅π™°πš„π™»πšƒ can be renamed to any unused value.

Usage

A sometimes more compact form of the πšŽπš•πšŽπš–πšŽπš—πš constraint: we are not obliged to specify explicitly the table entries that correspond to the specified default value. This can sometimes reduce drastically memory utilisation.

Remark

The original constraint of CHIP had an additional parameter πš‚π™Έπš‰π™΄ giving the maximum value of π™Έπšƒπ™΄π™Ό.πš’πš—πšπšŽπš‘.

Reformulation

Let 𝙸 and πš… respectively denote π™Έπšƒπ™΄π™Ό[1].πš’πš—πšπšŽπš‘ and π™Έπšƒπ™΄π™Ό[1].πšŸπšŠπš•πšžπšŽ. The πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ(π™Έπšƒπ™΄π™Ό,πšƒπ™°π™±π™»π™΄,π™³π™΄π™΅π™°πš„π™»πšƒ) constraint can be expressed in term of a reified constraint of the form:

((𝙸=πšƒπ™°π™±π™»π™΄[1].πš’πš—πšπšŽπš‘βˆ§πš…=πšƒπ™°π™±π™»π™΄[1].πšŸπšŠπš•πšžπšŽ) ∨

Β (𝙸=πšƒπ™°π™±π™»π™΄[2].πš’πš—πšπšŽπš‘βˆ§πš…=πšƒπ™°π™±π™»π™΄[2].πšŸπšŠπš•πšžπšŽ) ∨

Β ...

Β (𝙸=πšƒπ™°π™±π™»π™΄[|πšƒπ™°π™±π™»π™΄|].πš’πš—πšπšŽπš‘βˆ§πš…=πšƒπ™°π™±π™»π™΄[πšƒπ™°π™±π™»π™΄|].πšŸπšŠπš•πšžπšŽ)) ∨

((π™Έβ‰ πšƒπ™°π™±π™»π™΄[1].πš’πš—πšπšŽπš‘) ∧

Β (π™Έβ‰ πšƒπ™°π™±π™»π™΄[2].πš’πš—πšπšŽπš‘) ∧

Β ...

Β (π™Έβ‰ πšƒπ™°π™±π™»π™΄[|πšƒπ™°π™±π™»π™΄|].πš’πš—πšπšŽπš‘) ∧

Β (πš…=π™³π™΄π™΅π™°πš„π™»πšƒ)).

See also

common keyword: πšŽπš•πšŽπš–, πšŽπš•πšŽπš–πšŽπš—πšΒ (array constraint), πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽΒ (sparse table).

implies: πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ.

system of constraints: πšŽπš•πšŽπš–πšŽπš—πšπšœ_πšœπš™πšŠπš›πšœπšŽ.

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: binary constraint.

constraint network structure: centered cyclic(2) constraint network(1).

constraint type: data constraint.

filtering: arc-consistency.

modelling: array constraint, table, sparse table, sparse functional dependency, variable indexing.

Derived Collections
πšŒπš˜πš•π™³π™΄π™΅-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πš’πš—πš),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-0,πšŸπšŠπš•πšžπšŽ-π™³π™΄π™΅π™°πš„π™»πšƒ)]
πšŒπš˜πš•πšƒπ™°π™±π™»π™΄_𝙳𝙴𝙡-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-πšƒπ™°π™±π™»π™΄.πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ-πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ),πš’πšπšŽπš–(πš’πš—πšπšŽπš‘-𝙳𝙴𝙡.πš’πš—πšπšŽπš‘,πšŸπšŠπš•πšžπšŽ-𝙳𝙴𝙡.πšŸπšŠπš•πšžπšŽ)
Arc input(s)

π™Έπšƒπ™΄π™Ό πšƒπ™°π™±π™»π™΄_𝙳𝙴𝙡

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–,πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏)

Arc arity
Arc constraint(s)
β€’ πš’πšπšŽπš–.πšŸπšŠπš•πšžπšŽ=πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πšŸπšŠπš•πšžπšŽ
β€’ πš’πšπšŽπš–.πš’πš—πšπšŽπš‘=πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πš’πš—πšπšŽπš‘βˆ¨πšπšŠπš‹πš•πšŽ_𝚍𝚎𝚏.πš’πš—πšπšŽπš‘=0
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯1

Graph model

The final graph has between one and two arc constraints: it has two arcs when the default value π™³π™΄π™΅π™°πš„π™»πšƒ occurs also in the table πšƒπ™°π™±π™»π™΄; otherwise it has only one arc.

PartsΒ (A) andΒ (B) of FigureΒ 5.122.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 outline with thick lines.

Figure 5.122.1. Initial and final graph of the πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ constraint
ctrs/element_sparseActrs/element_sparseB
(a) (b)
Automaton

FigureΒ 5.122.2 depicts the automaton associated with the πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ constraint. Let π™Έπ™½π™³π™΄πš‡ and πš…π™°π™»πš„π™΄ respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the unique item of the π™Έπšƒπ™΄π™Ό collection. Let π™Έπ™½π™³π™΄πš‡ i and πš…π™°π™»πš„π™΄ i respectively be the πš’πš—πšπšŽπš‘ and the πšŸπšŠπš•πšžπšŽ attributes of the i th item of the πšƒπ™°π™±π™»π™΄ collection. To each quintuple (π™Έπ™½π™³π™΄πš‡,πš…π™°π™»πš„π™΄,π™³π™΄π™΅π™°πš„π™»πšƒ,π™Έπ™½π™³π™΄πš‡ i ,πš…π™°π™»πš„π™΄ i ) corresponds a signature variable πš‚ i as well as the following signature constraint:

(π™Έπ™½π™³π™΄πš‡β‰ π™Έπ™½π™³π™΄πš‡ i βˆ§πš…π™°π™»πš„π™΄β‰ π™³π™΄π™΅π™°πš„π™»πšƒ)⇔ πš‚ i =0 ∧(π™Έπ™½π™³π™΄πš‡=π™Έπ™½π™³π™΄πš‡ i βˆ§πš…π™°π™»πš„π™΄=πš…π™°π™»πš„π™΄ i )⇔ πš‚ i =1 ∧(π™Έπ™½π™³π™΄πš‡β‰ π™Έπ™½π™³π™΄πš‡ i βˆ§πš…π™°π™»πš„π™΄=π™³π™΄π™΅π™°πš„π™»πšƒ)⇔ πš‚ i =2.

Figure 5.122.2. Automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ constraint
ctrs/element_sparse1
Figure 5.122.3. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš•πšŽπš–πšŽπš—πš_πšœπš™πšŠπš›πšœπšŽ constraint
ctrs/element_sparse2