# graph-isomorphism

##### Graph Isomorphism

These functions deal with graph isomorphism.

- Keywords
- graphs

##### Usage

```
graph.isoclass(graph)
graph.isomorphic(graph1, graph2)
graph.isomorphic.vf2(graph1, graph2)
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.

##### Details

`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.

`graph.isomorphic`

decides whether two graphs are isomorphic.

`graph.isomorphic.vf2`

decides whethe two graphs are isomorphic,
it implements the VF2 algorithm, see references.

`graph.isocreate`

create a graph from the given isomorphic
class.
These functions are considered as experimental, as
`graph.isomorphic`

, `graph.isoclass`

and
`graph.isocreate`

can handle only graphs with three of four
vertices.

It is quite likely that some `graph.isomorphic`

will be able to
call `graph.isomorphic.vf2`

in some later igraph version.

##### Value

`graph.isoclass`

returns a non-negative integer number.`graph.isomorphic`

and`graph.isomorphic.vf2`

return a logical constant.`graph.isocreate`

returns a graph object.

##### References

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.isomorphic(g1, g2)
# create two isomorphic graphs, by
# permuting the vertices of the first
g1 <- barabasi.game(30, m=2, directed=FALSE)
el <- get.edgelist(g1)
iso <- sample(vcount(g1))-1
el <- matrix(iso[ el+1 ], nc=2)
g2 <- graph(t(el), directed=FALSE)
graph.isomorphic.vf2(g1, g2)
```

*Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)*