canonical.permutation {igraph} | R Documentation |
The canonical permutation brings every isomorphic graphs into the same (labeled) graphs.
canonical.permutation(graph, sh="fm")
graph |
The input graph, treated as undirected. |
sh |
Type of the heuristics to use for the BLISS algorithm. See details for possible values. |
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:
See the paper in references for details about these.
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:
|
Tommi Junttila for BLISS, Gabor Csardi csardi@rmki.kfki.hu for the igraph and R interfaces.
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.
permute.vertices
to apply a permutation to a
graph, graph.isomorphic
for deciding graph isomorphism,
possibly based on canonical labels.
## 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)