## 5.71. connect_points

 DESCRIPTION LINKS GRAPH
Origin

N. Beldiceanu

Constraint

$\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝}_\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\left(\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1},\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2},\mathrm{𝚂𝙸𝚉𝙴}\mathtt{3},\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿},\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}\right)$

Arguments
 $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{3}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚙-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1}>0$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2}>0$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{3}>0$ $\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}\ge 0$ $\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}\le |\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}|$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1}*\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2}*\mathrm{𝚂𝙸𝚉𝙴}\mathtt{3}=|\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂},𝚙\right)$
Purpose

On a 3-dimensional grid of variables, number of groups, where a group consists of a connected set of variables that all have a same value distinct from 0.

Example
$\left(\begin{array}{c}8,4,2,2,〈\begin{array}{c}𝚙-0,𝚙-0,\hfill \\ 𝚙-1,𝚙-1,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-1,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-1,\hfill \\ 𝚙-1,𝚙-1,\hfill \\ 𝚙-1,𝚙-1,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-1,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-2,𝚙-2,\hfill \\ 𝚙-2,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0,\hfill \\ 𝚙-0,𝚙-2,\hfill \\ 𝚙-0,𝚙-0\hfill \end{array}〉\hfill \end{array}\right)$

Figure 5.71.1 corresponds to the solution where we describe separately each layer of the grid. The $\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝}_\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}$ constraint holds since we have two groups ($\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}=2$): a first one for the variables of the $\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}$ collection assigned to value 1, and a second one for the variables assigned to value 2.

##### Figure 5.71.1. The two layers of the solution Typical
 $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1}>1$ $\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2}>1$ $\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}>0$ $\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}<|\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}|$ $|\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}|>3$
Symmetry

All occurrences of two distinct values of $\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}.𝚙$ that are both different from 0 can be swapped; all occurrences of a value of $\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}.𝚙$ that is different from 0 can be renamed to any unused value that is also different from 0.

Usage

Wiring problems [Simonis90][Zhou96].

Keywords
Arc input(s)

$\mathrm{𝙿𝙾𝙸𝙽𝚃𝚂}$

Arc generator
$\begin{array}{c}\mathrm{𝐺𝑅𝐼𝐷}\left(\left[\mathrm{𝚂𝙸𝚉𝙴}\mathtt{1},\mathrm{𝚂𝙸𝚉𝙴}\mathtt{2},\mathrm{𝚂𝙸𝚉𝙴}\mathtt{3}\right]\right)↦\hfill \\ \mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\mathtt{1},\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\mathtt{2}\right)\hfill \end{array}$

Arc arity
Arc constraint(s)
 $•\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\mathtt{1}.𝚙\ne 0$ $•\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\mathtt{1}.𝚙=\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}\mathtt{2}.𝚙$
Graph property(ies)
$\mathrm{𝐍𝐒𝐂𝐂}$$=\mathrm{𝙽𝙶𝚁𝙾𝚄𝙿}$

Graph class
$\mathrm{𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙲}$

Graph model

Figure 5.71.2 gives the initial graph constructed by the $\mathrm{𝐺𝑅𝐼𝐷}$ arc generator associated with the Example slot.

##### Figure 5.71.2. Graph generated by $\mathrm{𝐺𝑅𝐼𝐷}$([8,4,2]) 