5.171. graph_isomorphism
| DESCRIPTION | LINKS |
- Origin
- Constraint
- Arguments
- Restrictions
- 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:
if there is an arc from to in the graph , then there is also an arc from the image of to the image of in the graph ,
if there is no arc from to in the graph , then there is also no arc from the image of to the image of 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
-
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 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
- Symmetries
Items of are permutable.
Items of are permutable.
- Algorithm
A constraint approach is described inΒ [SorlinSolnon08].
- See also
related: .
- Keywords