canonical.permutation {igraph} | R Documentation

## Canonical permutation of a graph

### Description

The canonical permutation brings every isomorphic graphs into the same (labeled) graphs.

### Usage

    canonical.permutation(graph, sh="fm")

### Arguments

`graph` | The input graph, treated as undirected.
`sh` | Type of the heuristics to use for the BLISS algorithm. See details for possible values.

### Details

`canonical.permutation` computes a permutation which brings the graph into canonical form, as defined by the BLISS algorithm. All isomorphic graphs have the same canonical form.

See the paper below for the details about BLISS. This and more information is available at http://www.tcs.hut.fi/Software/bliss/index.html.

The possible values for the `sh` argument are:

f
  First non-singleton cell.
fl
  First largest non-singleton cell.
fs
  First smallest non-singleton cell.
fm
  First maximally non-trivially connectec non-singleton cell.
flm
  Largest maximally non-trivially connected non-singleton cell.
fsm
  Smallest maximally non-trivially connected non-singleton cell.

See the paper in references for details about these.

### Value

A list with the following members:

`labeling` | The canonical parmutation which takes the input graph into canonical form. A numeric vector, the first element is the new label of vertex 0, the second element for vertex 1, etc.

`info`

Some information about the BLISS computation. A named list with the following members:

nof_nodes
  The number of nodes in the search tree.
nof_leaf_nodes
  The number of leaf nodes in the search tree.
nof_bad_nodes
  Number of bad nodes.
nof_canupdates
  Number of canrep updates.
max_level
  Maximum level.
group_size
  The size of the automorphism group of the input graph, as a string. This number is exact if igraph was compiled with the GMP library, and approximate otherwise.

### Author(s)

Tommi Junttila for BLISS, Gabor Csardi csardi@rmki.kfki.hu for the igraph and R interfaces.

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

### See Also

`permute.vertices` to apply a permutation to a graph, `graph.isomorphic` for deciding graph isomorphism, possibly based on canonical labels.

### Examples

    ## Calculate the canonical form of a random graph
    g1 <- erdos.renyi.game(10, 20, type="gnm")
    cp1 <- canonical.permutation(g1)
    cf1 <- permute.vertices(g1, cp1$labeling)

    ## Do the same with a random permutation of it
    g2 <- permute.vertices(g1, sample(vcount(g1))-1)
    cp2 <- canonical.permutation(g2)
    cf2 <- permute.vertices(g2, cp2$labeling)

    ## Check that they are the same
    el1 <- get.edgelist(cf1)
    el2 <- get.edgelist(cf2)
    el1 <- el1[ order(el1[,1], el1[,2]), ]
    el2 <- el2[ order(el2[,1], el2[,2]), ]
    all(el1 == el2)

[Package igraph version 0.5.2 Index]