graph-isomorphism {igraph} | R Documentation

## Graph Isomorphism

### Description

These functions deal with graph isomorphism.

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

1. If the two graphs do not agree in the number of vertices and the number of edges then `FALSE` is returned.
2. Otherwise if the graphs have 3 or 4 vertices, then `igraph.isomorphic.34` is called.
3. Otherwise if the graphs are directed, then `igraph.isomorphic.vf2` is called.
4. 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.
`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.
`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.

### Author(s)

Gabor Csardi csardi@rmki.kfki.hu

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

`graph.motifs`

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

[Package igraph version 0.5.2 Index]