5.324. subgraph_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 an induced subgraph of πšƒπ™°πšπ™Άπ™΄πšƒ so that, 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 induced subgraph of πšƒπ™°πšπ™Άπ™΄πšƒ. The vertices of both graphs are respectively defined by the two collections of vertices π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½ and π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ. Within collection π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½ the set of successors of each node is fixed, while this is not the case for the collection π™½π™Ύπ™³π™΄πš‚_πšƒπ™°πšπ™Άπ™΄πšƒ. This stems from the fact that the πšƒπ™°πšπ™Άπ™΄πšƒ graph is not fixed (i.e.,Β the lower and upper bounds of the target graph are specified when we post the πšœπšžπš‹πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš– constraint, while the induced subgraph of a solution to the πšœπšžπš‹πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš– constraint corresponds to a graph for which the upper and lower bounds are identical).

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

FigureΒ 5.324.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 induced subgraph of the target graph. The πšœπšžπš‹πšπš›πšŠπš™πš‘_πš’πšœπš˜πš–πš˜πš›πš™πš‘πš’πšœπš– constraint since:

  • To the arc from vertex 1 to vertex 4 in the pattern graph corresponds the arc from vertex 4 to 5 in the induced subgraph of 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 induced subgraph of 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 induced subgraph of the target graph.

  • To the arc from vertex 2 to vertex 4 in the pattern graph corresponds the arc from vertex 2 to 5 in the induced subgraph of 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 induced subgraph of the target graph.

Figure 5.324.1. (A)Β The pattern graph, (B)Β the initial target graph – plain arcs must belong to the induced subgraph, while dotted arcs may or may not belong to the induced subgraph – and (C)Β the correspondence between the vertices of the pattern graph and the vertices of the induced subgraph of the target graph
ctrs/subgraph_isomorphism1
Symmetries
  • Items of π™½π™Ύπ™³π™΄πš‚_π™Ώπ™°πšƒπšƒπ™΄πšπ™½ are permutable.

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

Usage

Within the context of constraint programming the constraint was used for finding symmetriesΒ [Puget03], [Puget05a], [Puget05b].

Algorithm

[Ullmann76], [Regin95], [LarrosaValiente02], [ZampelliDevilleSolnonSorlinDupont07].

See also

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

Keywords

constraint arguments: constraint involving set variables.

constraint type: predefined constraint, graph constraint.

symmetry: symmetry.