## 5.171. graph_isomorphism

Origin
Constraint

$\mathrm{𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}\right)$

Arguments
 $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚜𝚒𝚗𝚝}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚜𝚒𝚗𝚝}\right)$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚖𝚊𝚐𝚎}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|=|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽},\left[\mathrm{𝚒𝚖𝚊𝚐𝚎}\right]\right)$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}.\mathrm{𝚒𝚖𝚊𝚐𝚎}\ge 1$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}.\mathrm{𝚒𝚖𝚊𝚐𝚎}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽},\mathrm{𝚒𝚖𝚊𝚐𝚎}\right)$ $|\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}|=|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$
Purpose

Given two directed graphs $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ enforce a one to one correspondence, defined by the function $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}$, between the vertices of the graph $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and the vertices of the graph $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ so that:

1. if there is an arc from $u$ to $v$ in the graph $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$, then there is also an arc from the image of $u$ to the image of $v$ in the graph $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$,

2. if there is no arc from $u$ to $v$ in the graph $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$, then there is also no arc from the image of $u$ to the image of $v$ in the graph $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$.

Both, the $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ are fixed, and the vertices of both graphs are respectively defined by the two collections of vertices $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$.

Example
$\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{2,4\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,3,4\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-3\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\varnothing ,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-4\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\varnothing \hfill \end{array}〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\varnothing ,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,3,4\right\},\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-3\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\varnothing ,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-4\hfill & \mathrm{𝚜𝚞𝚌𝚌}-\left\{1,2\right\}\hfill \end{array}〉,\hfill \\ 〈4,2,3,1〉\hfill \end{array}\right)$

Figure 5.171.1 gives the pattern (see Part (A)) and target graph (see Part (B)) of the Example slot as well as the one to one correspondence (see Part (C)) between the pattern graph and the target graph. The $\mathrm{𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ constraint since the pattern and target graphs have the same number of vertices and arcs and since:

• To the arc from vertex 1 to vertex 4 in the pattern graph corresponds the arc from vertex 4 to 1 in the target graph.

• To the arc from vertex 1 to vertex 2 in the pattern graph corresponds the arc from vertex 4 to 2 in the target graph.

• To the arc from vertex 2 to vertex 1 in the pattern graph corresponds the arc from vertex 2 to 4 in the target graph.

• To the arc from vertex 2 to vertex 4 in the pattern graph corresponds the arc from vertex 2 to 1 in the target graph.

• To the arc from vertex 2 to vertex 3 in the pattern graph corresponds the arc from vertex 2 to 3 in the target graph.

##### Figure 5.171.1. Illustration of the Example slot: (A) The pattern graph, (B) the target graph and (C) the correspondence, denoted by thick dashed arcs, between the vertices of the pattern graph and the vertices of the target graph Typical
$|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|>1$
Symmetries
• Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ are permutable.

• Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ are permutable.

Algorithm

A constraint approach is described in [SorlinSolnon08].