Global Constraint Catalog: Cdistance

5.131. distance_change

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Derived from $𝚌𝚑𝚊𝚗𝚐𝚎$ .

Constraint

$𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎 (𝙳𝙸𝚂𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝙲𝚃𝚁)$

Synonym

$𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎$ .

Arguments

$𝙳𝙸𝚂𝚃$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝙲𝚃𝚁$	$𝚊𝚝𝚘𝚖$

Restrictions

𝙳𝙸𝚂𝚃 \geq 0

𝙳𝙸𝚂𝚃 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝚟𝚊𝚛)

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

𝙲𝚃𝚁 \in [=, \neq, <, \geq, >, \leq]

Purpose

$𝙳𝙸𝚂𝚃$ is equal to the number of times one of the following two conditions is true $(1 \leq 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〉, \neq)

The $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint holds since the following condition ( $𝙳𝙸𝚂𝚃 = 1$ ) is verified: $\{\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [3] . 𝚟𝚊𝚛 = 1 \neq 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [4] . 𝚟𝚊𝚛 = 2 \land \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 [3] . 𝚟𝚊𝚛 = 3 = 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [4] . 𝚟𝚊𝚛 = 3 \end{matrix}$ .

Typical

𝙳𝙸𝚂𝚃 > 0

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | > 1

𝙲𝚃𝚁 \in [=, \neq]

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$ .

Arg. properties

Functional dependency: $𝙳𝙸𝚂𝚃$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ and $𝙲𝚃𝚁$ .

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.

root concept: $𝚌𝚑𝚊𝚗𝚐𝚎$ .

Keywords

characteristic of a constraint: automaton, automaton with counters.

constraint arguments: pure functional dependency.

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

constraint type: proximity constraint.

modelling: functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ / $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 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.131.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 \to 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.131.1. Final graphs of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint


(a)	(b)

Automaton

Figure 5.131.2 depicts the automaton associated with the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint. Let $(𝚅𝙰𝚁 1_{i}, 𝚅𝙰𝚁 1_{i + 1})$ and $(𝚅𝙰𝚁 2_{i}, 𝚅𝙰𝚁 2_{i + 1})$ respectively be the $i^{t h}$ 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 $S_{i}$ . The following signature constraint links these variables:

$((𝚅𝙰𝚁 1_{i} = 𝚅𝙰𝚁 1_{i + 1}) \land (𝚅𝙰𝚁 2_{i} \neq 𝚅𝙰𝚁 2_{i + 1})) \lor$

$((𝚅𝙰𝚁 1_{i} \neq 𝚅𝙰𝚁 1_{i + 1}) \land (𝚅𝙰𝚁 2_{i} = 𝚅𝙰𝚁 2_{i + 1})) \Leftrightarrow S_{i}$ .

Figure 5.131.2. Automaton of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.131.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.131. distance_change

Figure 5.131.1. Final graphs of the 𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.131.2. Automaton of the 𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.131.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎 constraint

Figure 5.131.1. Final graphs of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.131.2. Automaton of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint

Figure 5.131.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚌𝚑𝚊𝚗𝚐𝚎$ constraint