5.146. graph_isomorphism

DESCRIPTIONLINKS
Origin

[Gregor79]

Constraint

πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš–(π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½,π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ,π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½)

Arguments
π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšœπš’πš—πš)
π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒπšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,𝚜𝚞𝚌𝚌-πšœπš’πš—πš)
π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš–πšŠπšπšŽ-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½|
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ,[πš’πš—πšπšŽπš‘,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ|
|π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ|=|π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½|
πš›πšŽπššπšžπš’πš›πšŽπš(π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½,[πš’πš–πšŠπšπšŽ])
π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½.πš’πš–πšŠπšπšŽβ‰₯1
π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½.πš’πš–πšŠπšπšŽβ‰€|π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ|
πšπš’πšœπšπš’πš—πšŒπš(π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½,πš’πš–πšŠπšπšŽ)
|π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½|=|π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½|
Purpose

Given two directed graphs π™Ώπ™°πšƒπšƒπ™΄πšπ™½ and πšƒπ™°πšπ™Άπ™΄πšƒ enforce a one to one correspondence, defined by the function π™΅πš„π™½π™²πšƒπ™Έπ™Ύπ™½, between the vertices of the graph π™Ώπ™°πšƒπšƒπ™΄πšπ™½ and the vertices of the graph πšƒπ™°πšπ™Άπ™΄πšƒ so that:

  1. if there is an arc from u to v in the graph π™Ώπ™°πšƒπšƒπ™΄πšπ™½, then there is also an arc from the image of u to the image of v in the graph πšƒπ™°πšπ™Άπ™΄πšƒ,

  2. if there is no arc from u to v in the graph π™Ώπ™°πšƒπšƒπ™΄πšπ™½, then there is also no arc from the image of u to the image of v in the graph πšƒπ™°πšπ™Άπ™΄πšƒ.

Both, the π™Ώπ™°πšƒπšƒπ™΄πšπ™½ and πšƒπ™°πšπ™Άπ™΄πšƒ are fixed, and the vertices of both graphs are respectively defined by the two collections of vertices π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½ and π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ.

Example
πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-{2,4},πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-{1,3,4},πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-{1,3,4},πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-βˆ…,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-{1,2},4,2,3,1

FigureΒ 5.146.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 πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš– 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.146.1. (A)Β The pattern graph, (B)Β the target graph and (C)Β the correspondence between the vertices of the pattern graph and the vertices of the target graph
ctrs/graph_isomorphism1
Typical
|π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½|>1
Symmetries
  • Items of π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½ are permutable.

  • Items of π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ are permutable.

Algorithm

A constraint approach is described inΒ [SorlinSolnon08].

See also

related: πšœπšžπš‹πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš–.

Keywords

constraint arguments: constraint involving set variables.

constraint type: predefined constraint, graph constraint.