# graph-isomorphism

##### Graph Isomorphism

These functions deal with graph isomorphism.

- Keywords
- graphs

##### Usage

```
graph.isomorphic(graph1, graph2)
graph.isomorphic.34(graph1, graph2)
graph.isomorphic.bliss(graph1, graph2, sh1="fm", sh2="fm")
graph.isomorphic.vf2(graph1, graph2)
```graph.count.isomorphisms.vf2(graph1, graph2)
graph.get.isomorphisms.vf2(graph1, graph2)

graph.subisomorphic.vf2(graph1, graph2)
graph.count.subisomorphisms.vf2(graph1, graph2)
graph.get.subisomorphisms.vf2(graph1, graph2)

graph.isoclass(graph)
graph.isoclass.subgraph(graph, vids)
graph.isocreate(size, number, directed=TRUE)

##### Arguments

- graph
- A graph object.
- graph1,graph2
- Graph objects
- size
- A numeric integer giving the number of vertices in the graph to create. Only three or four are suppported right now.
- number
- The number of the isomorphism class of the graph to be created.
- directed
- Whether to create a directed graph.
- 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. - vids
- Numeric vector, the vertex ids of vertices to form the induced subgraph for determining the isomorphism class.

##### Details

`graph.isomorphic`

decides whether two graphs are isomorphic.
The input graphs must be both directed or both undirected.
This function is a higher level interface to the other graph
isomorphism decision functions. Currently it does the following:

- If the two graphs do not agree in the number of vertices and
the number of edges then
`FALSE`

is returned. - Otherwise if the graphs have 3 or 4 vertices, then
`igraph.isomorphic.34`

is called. - Otherwise if the graphs are directed, then
`igraph.isomorphic.vf2`

is called. - Otherwise
`igraph.isomorphic.bliss`

is called.

`igraph.isomorphic.34`

decides whether two graphs, both of which
contains only 3 or 4 vertices, are isomorphic. It works based on a
precalculated and stored table.

`igraph.isomorphic.bliss`

uses the BLISS algorithm by Junttila
and Kaski, and it works for undirected graphs. For both graphs the
`canonical.permutation`

and then the
`permute.vertices`

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

`graph.isomorphic.vf2`

decides whethe two graphs are isomorphic,
it implements the VF2 algorithm, by Cordella, Foggia et al., see
references.

`graph.count.isomorphisms.vf2`

counts the different isomorphic
mappings between `graph1`

and `graph2`

. (To count
automorphisms you can supply the same graph twice, but it is better to
call `graph.automorphisms`

.) It uses the VF2 algorithm.

`graph.get.isomorphisms.vf2`

calculates all isomorphic mappings
between `graph1`

and `graph2`

. It uses the VF2 algorithm.

`graph.subisomorphic.vf2`

decides whether `graph2`

is
isomorphic to some subgraph of `graph1`

. It uses the VF2 algorithm.

`graph.count.subisomorphisms.vf2`

counts the different isomorphic
mappings between `graph2`

and the subgraphs of `graph1`

. It
uses the VF2 algorithm.

`graph.get.subisomorphisms.vf2`

calculates all isomorphic
mappings between `graph2`

and the subgraphs of `graph1`

. It
uses the VF2 algorithm.
`graph.isoclass`

returns the isomorphism class of a graph, a
non-negative integer number. Graphs (with the same number of vertices)
having the same isomorphism class are isomorphic and isomorphic graphs
always have the same isomorphism class. Currently it can handle only
graphs with 3 or 4 vertices.

`graph.isoclass.subgraph`

calculates the isomorphism class of a
subgraph of the input graph. Currently it only works for subgraphs
with 3 or 4 vertices.
`graph.isocreate`

create a graph from the given isomorphic
class. Currently it can handle only graphs with 3 or 4 vertices.

##### Value

`graph.isomorphic`

and`graph.isomorphic.34`

return a logical scalar,`TRUE`

if the input graphs are isomorphic,`FALSE`

otherwise.`graph.isomorphic.bliss`

returns a named list with elements:iso A logical scalar, whether the two graphs are isomorphic. map12 A numeric vector, an mapping from `graph1`

to`graph2`

if`iso`

is`TRUE`

, an empty numeric vector otherwise.map21 A numeric vector, an mapping from `graph2`

to`graph1`

if`iso`

is`TRUE`

, an empty numeric vector otherwise.info1 Some information about the canonical form calculation for `graph1`

. A named list, see the return value of`canonical.permutation`

for details.info2 Some information about the canonical form calculation for `graph2`

. A named list, see the return value of`canonical.permutation`

for details.`graph.isomorphic.vf2`

returns a names list with three elements:iso A logical scalar, whether the two graphs are isomorphic. map12 A numeric vector, an mapping from `graph1`

to`graph2`

if`iso`

is`TRUE`

, an empty numeric vector otherwise.map21 A numeric vector, an mapping from `graph2`

to`graph1`

if`iso`

is`TRUE`

, an empty numeric vector otherwise.`graph.count.isomorphisms.vf2`

returns a numeric scalar, an integer, the number of isomorphic mappings between the two input graphs.`graph.get.isomorphisms.vf2`

returns a list of numeric vectors. Every numeric vector is a permutation which takes`graph2`

into`graph1`

.`graph.subisomorphic.vf2`

returns a named list with three elements:iso Logical scalar, `TRUE`

if a subgraph of`graph1`

is isomorphic to`graph2`

.map12 Numeric vector, empty if `iso`

is`FALSE`

. Otherwise a mapping from a subgraph of`graph1`

to`graph2`

. -1 denotes the vertices which are not part of the mapping.map21 Numeric vector, empty if `iso`

is`FALSE`

. Otherwise a mapping from`graph2`

into`graph1`

.`graph.count.subisomorphisms.vf2`

returns a numeric scalar, an integer.`graph.get.subisomorphisms.vf2`

returns a list of numeric vectors, each numeric vector is an isomorphic mapping from`graph2`

to a subgraph of`graph1`

.`graph.isoclass`

and`graph.isoclass.subgraph`

return a non-negative integer number.`graph.isocreate`

returns a graph object.

##### Note

Functions `graph.isoclass`

, `graph.isoclass.subgraph`

and
`graph.isocreate`

are considered experimental and might be
reorganized/rewritten later.

##### concept

- Graph isomorphism
- Subgraph isomorphism
- VF2 algorithm
- BLISS algorithm

##### 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

##### Examples

```
# create some non-isomorphic graphs
g1 <- graph.isocreate(3, 10)
g2 <- graph.isocreate(3, 11)
graph.isoclass(g1)
graph.isoclass(g2)
graph.isomorphic(g1, g2)
# create two isomorphic graphs, by
# permuting the vertices of the first
g1 <- simplify(barabasi.game(30, m=2, directed=FALSE))
g2 <- permute.vertices(g1, sample(vcount(g1))-1)
# should be TRUE
graph.isomorphic(g1, g2)
graph.isomorphic.bliss(g1, g2)
graph.isomorphic.vf2(g1, g2)
```

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