# isomorphic

##### Decide if two graphs are isomorphic

Decide if two graphs are isomorphic

##### Usage

`isomorphic(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ...)`is_isomorphic_to(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"),
...)

##### Arguments

- graph1
The first graph.

- graph2
The second graph.

- method
The method to use. Possible values: ‘auto’, ‘direct’, ‘vf2’, ‘bliss’. See their details below.

- ...
Additional arguments, passed to the various methods.

##### Value

Logical scalar, `TRUE`

if the graphs are isomorphic.

##### ‘auto’ method

It tries to select the appropriate method based on the two graphs. This is the algorithm it uses:

If the two graphs do not agree on their order and size (i.e. number of vertices and edges), then return

`FALSE`

.If the graphs have three or four vertices, then the ‘direct’ method is used.

If the graphs are directed, then the ‘vf2’ method is used.

Otherwise the ‘bliss’ method is used.

##### ‘direct’ method

This method only works on graphs with three or four vertices, and it is based on a pre-calculated and stored table. It does not have any extra arguments.

##### ‘vf2’ method

This method uses the VF2 algorithm by Cordella, Foggia et al., see references below. It supports vertex and edge colors and have the following extra arguments:

- vertex.color1, vertex.color2
Optional integer vectors giving the colors of the vertices for colored graph isomorphism. If they are not given, but the graph has a “color” vertex attribute, then it will be used. If you want to ignore these attributes, then supply

`NULL`

for both of these arguments. See also examples below.- edge.color1, edge.color2
Optional integer vectors giving the colors of the edges for edge-colored (sub)graph isomorphism. If they are not given, but the graph has a “color” edge attribute, then it will be used. If you want to ignore these attributes, then supply

`NULL`

for both of these arguments.

##### ‘bliss’ method

Uses the BLISS algorithm by Junttila and Kaski, and it works for
undirected graphs. For both graphs the
`canonical_permutation`

and then the `permute`

function is called to transfer them into canonical form; finally the
canonical forms are compared.
Extra arguments:

- sh1
Character constant, the heuristics to use in the BLISS algorithm, for

`graph1`

. See the`sh`

argument of`canonical_permutation`

for possible values.- sh2
Character constant, the heuristics to use in the BLISS algorithm, for

`graph2`

. See the`sh`

argument of`canonical_permutation`

for possible values.

`sh1`

and `sh2`

default to ‘fm’.

##### References

Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical
Labeling Tool for Large and Sparse Graphs, *Proceedings of the
Ninth Workshop on Algorithm Engineering and Experiments and the Fourth
Workshop on Analytic Algorithms and Combinatorics.* 2007.

LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm
for matching large graphs, *Proc. of the 3rd IAPR TC-15 Workshop
on Graphbased Representations in Pattern Recognition*, 149--159, 2001.

##### See Also

Other graph isomorphism: `count_isomorphisms`

,
`graph.count.isomorphisms.vf2`

;
`count_subgraph_isomorphisms`

,
`graph.count.subisomorphisms.vf2`

;
`graph.get.isomorphisms.vf2`

,
`isomorphisms`

;
`graph.get.subisomorphisms.vf2`

,
`subgraph_isomorphisms`

;
`graph.isoclass`

,
`graph.isoclass.subgraph`

,
`isomorphism_class`

;
`graph.isocreate`

,
`graph_from_isomorphism_class`

;
`graph.subisomorphic.lad`

,
`graph.subisomorphic.vf2`

,
`is_subgraph_isomorphic_to`

,
`subgraph_isomorphic`

##### Examples

```
# NOT RUN {
# create some non-isomorphic graphs
g1 <- graph_from_isomorphism_class(3, 10)
g2 <- graph_from_isomorphism_class(3, 11)
isomorphic(g1, g2)
# create two isomorphic graphs, by permuting the vertices of the first
g1 <- barabasi.game(30, m=2, directed=FALSE)
g2 <- permute(g1, sample(vcount(g1)))
# should be TRUE
isomorphic(g1, g2)
isomorphic(g1, g2, method = "bliss")
isomorphic(g1, g2, method = "vf2")
# colored graph isomorphism
g1 <- make_ring(10)
g2 <- make_ring(10)
isomorphic(g1, g2)
V(g1)$color <- rep(1:2, length = vcount(g1))
V(g2)$color <- rep(2:1, length = vcount(g2))
# consider colors by default
count_isomorphisms(g1, g2)
# ignore colors
count_isomorphisms(g1, g2, vertex.color1 = NULL,
vertex.color2 = NULL)
# }
```

*Documentation reproduced from package igraph, version 1.0.1, License: GPL (>= 2)*