5.111. distance_change

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŒπš‘πšŠπš—πšπšŽ.

Constraint

πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ(π™³π™Έπš‚πšƒ,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,π™²πšƒπš)

Synonym

πšπš’πšœπšπšŠπš—πšŒπšŽ.

Arguments
π™³π™Έπš‚πšƒπšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™²πšƒπšπšŠπšπš˜πš–
Restrictions
π™³π™Έπš‚πšƒβ‰₯0
π™³π™Έπš‚πšƒ<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
π™²πšƒπšβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

π™³π™Έπš‚πšƒ is equal to the number of times one of the following two conditions is true (1≀i<n):

  • πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[i].πšŸπšŠπš› π™²πšƒπš πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[i+1].πšŸπšŠπš› holds and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[i].πšŸπšŠπš› π™²πšƒπš πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[i+1].πšŸπšŠπš› does not hold,

  • πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[i].πšŸπšŠπš› π™²πšƒπš πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[i+1].πšŸπšŠπš› holds and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[i].πšŸπšŠπš› π™²πšƒπš πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[i+1].πšŸπšŠπš› does not hold.

Example
1,3,3,1,2,2,4,4,3,3,3,β‰ 

The πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ constraint holds since the following condition (π™³π™Έπš‚πšƒ=1) is verified: πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[3].πšŸπšŠπš›=1β‰ πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[4].πšŸπšŠπš›=2 βˆ§πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2[3].πšŸπšŠπš›=3=πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1[4].πšŸπšŠπš›=3 .

Typical
π™³π™Έπš‚πšƒ>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>1
Symmetries
  • Arguments are permutable w.r.t. permutation (π™³π™Έπš‚πšƒ) (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) (π™²πšƒπš).

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.

Usage

Measure the distance between two sequences according to the πšŒπš‘πšŠπš—πšπšŽ constraint.

Remark

We measure that distance with respect to a given constraint and not according to the fact that the variables are assigned distinct values.

See also

common keyword: πšπš’πšœπšπšŠπš—πšŒπšŽ_πš‹πšŽπšπš πšŽπšŽπš—Β (proximity constraint).

root concept: πšŒπš‘πšŠπš—πšπšŽ.

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint network structure: sliding cyclic(2) constraint network(2).

constraint type: proximity constraint.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1/ πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› π™²πšƒπš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πƒπˆπ’π“π€ππ‚π„=π™³π™Έπš‚πšƒ

Graph model

Within the Arc input(s) slot, the character / indicates that we generate two distinct graphs. The graph property π™³π™Έπš‚πšƒπ™°π™½π™²π™΄ measures the distance between two digraphs G 1 and G 2 . This distance is defined as the sum of the following quantities:

  • The number of arcs of G 1 that do not belong to G 2 ,

  • The number of arcs of G 2 that do not belong to G 1 .

PartΒ (A) of FigureΒ 5.111.1 gives the final graph associated with the sequence πšŸπšŠπš›-3,πšŸπšŠπš›-3,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-2 (i.e.,Β the second argument of the constraint of the Example slot), while partΒ (B) shows the final graph corresponding to πšŸπšŠπš›-4,πšŸπšŠπš›-4,πšŸπšŠπš›-3,πšŸπšŠπš›-3,πšŸπšŠπš›-3 (i.e.,Β the third argument of the constraint of the Example slot). Since arc 3β†’4 belongs to the first final graph but not to the second one, the distance between the two final graphs is equal to 1.

Figure 5.111.1. Final graphs of the πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/distance_changeActrs/distance_changeB
(a) (b)
Automaton

FigureΒ 5.111.2 depicts the automaton associated with the πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ constraint. Let (πš…π™°πš1 i ,πš…π™°πš1 i+1 ) and (πš…π™°πš2 i ,πš…π™°πš2 i+1 ) respectively be the i th pairs of consecutive variables of the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2. To each quadruple (πš…π™°πš1 i ,πš…π™°πš1 i+1 ,πš…π™°πš2 i ,πš…π™°πš2 i+1 ) corresponds a 0-1 signature variable πš‚ i . The following signature constraint links these variables:

((πš…π™°πš1 i =πš…π™°πš1 i+1 )∧(πš…π™°πš2 i β‰ πš…π™°πš2 i+1 )) ∨

((πš…π™°πš1 i β‰ πš…π™°πš1 i+1 )∧(πš…π™°πš2 i =πš…π™°πš2 i+1 ))β‡”πš‚ i .

Figure 5.111.2. Automaton of the πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/distance_change1
Figure 5.111.3. Hypergraph of the reformulation corresponding to the automaton of the πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/distance_change2