Global Constraint Catalog: Cdistance

5.130. distance_between

DESCRIPTION

LINKS

GRAPH

Origin

N. Beldiceanu

Constraint

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

Synonym

$𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎$ .

Arguments

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

Restrictions

𝙳𝙸𝚂𝚃 \geq 0

𝙳𝙸𝚂𝚃 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | * | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 | - | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

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

Purpose

Let $U_{i}$ and $V_{i}$ be respectively the $i^{t h}$ and $j^{t h}$ variables $(i \neq j)$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ . In a similar way, let $X_{i}$ and $Y_{i}$ be respectively the $i^{t h}$ and $j^{t h}$ variables $(i \neq j)$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ . $𝙳𝙸𝚂𝚃$ is equal to the number of times one of the following mutually incompatible conditions are true:

$U_{i} 𝙲𝚃𝚁 V_{i}$ holds and $X_{i} 𝙲𝚃𝚁 Y_{i}$ does not hold,
$X_{i} 𝙲𝚃𝚁 Y_{i}$ holds and $U_{i} 𝙲𝚃𝚁 V_{i}$ does not hold.

Example

(2, 〈3, 4, 6, 2, 4〉, 〈2, 6, 9, 3, 6〉, <)

The $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint holds since the following $𝙳𝙸𝚂𝚃 = 2$ conditions are verified:

$\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [4] . 𝚟𝚊𝚛 = 2 < 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [1] . 𝚟𝚊𝚛 = 3 \land \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 [4] . 𝚟𝚊𝚛 = 3 \geq 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 [1] . 𝚟𝚊𝚛 = 2 \end{matrix}$
$\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 [1] . 𝚟𝚊𝚛 = 2 < 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 [4] . 𝚟𝚊𝚛 = 3 \land \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [1] . 𝚟𝚊𝚛 = 3 \geq 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 [4] . 𝚟𝚊𝚛 = 2 \end{matrix}$

Typical

𝙳𝙸𝚂𝚃 > 0

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

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

𝙲𝚃𝚁 \in [=, \neq]

Symmetries

Arguments are permutable w.r.t. permutation $(𝙳𝙸𝚂𝚃)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝙲𝚃𝚁)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable (same permutation used).
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 in term of the number of constraint changes. This should be put in contrast to the number of value changes that is sometimes superficial.

Keywords

constraint arguments: pure functional dependency.

constraint type: proximity constraint.

modelling: functional dependency.

Arc input(s)

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

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

(\neq) \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.130.1 gives the final graph associated with the sequence $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -4, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -4 (i.e., the second argument of the constraint of the Example slot), while part (B) shows the final graph corresponding to $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -9, $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -6 (i.e., the third argument of the constraint of the Example slot). The two arc constraints that differ from one graph to the other are marked by a dotted line. The $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint holds since between sequence $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -4, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -4 and sequence $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -9, $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -6 there are $𝙳𝙸𝚂𝚃 = 2$ changes that respectively correspond to:

Within the final graph associated with sequence $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -4, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -4 the arc $4 \to 1$ (i.e., values $2 \to 3$ ) does not occur in the final graph associated with $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -9, $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -6,
Within the final graph associated with sequence $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -9, $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -6 the arc $1 \to 4$ (i.e., values $2 \to 3$ ) does not occur in the final graph associated with $𝚟𝚊𝚛$ -3, $𝚟𝚊𝚛$ -4, $𝚟𝚊𝚛$ -6, $𝚟𝚊𝚛$ -2, $𝚟𝚊𝚛$ -4.

Figure 5.130.1. Final graphs of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.130. distance_between

Figure 5.130.1. Final graphs of the 𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚋𝚎𝚝𝚠𝚎𝚎𝚗 constraint

Figure 5.130.1. Final graphs of the $𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎_𝚋𝚎𝚝𝚠𝚎𝚎𝚗$ constraint