1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
|
\name{canonical.permutation}
\alias{canonical.permutation}
\concept{Canonical permutation}
\concept{BLISS}
\title{Canonical permutation of a graph}
\description{The canonical permutation brings every isomorphic graphs
into the same (labeled) graph.}
\usage{
canonical.permutation(graph, sh="fm")
}
\arguments{
\item{graph}{The input graph, treated as undirected.}
\item{sh}{Type of the heuristics to use for the BLISS
algorithm. See details for possible values.}
}
\details{
\code{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
\url{http://www.tcs.hut.fi/Software/bliss/index.html}.
The possible values for the \code{sh} argument are:
\describe{
\item{\code{f}}{First non-singleton cell.}
\item{\code{fl}}{First largest non-singleton cell.}
\item{\code{fs}}{First smallest non-singleton cell.}
\item{\code{fm}}{First maximally non-trivially connectec
non-singleton cell.}
\item{\code{flm}}{Largest maximally non-trivially connected
non-singleton cell.}
\item{\code{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:
\item{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. }
\item{info}{Some information about the BLISS computation. A named
list with the following members:
\describe{
\item{\code{nof_nodes}}{The number of nodes in the search tree.}
\item{\code{nof_leaf_nodes}}{The number of leaf nodes in the search
tree.}
\item{\code{nof_bad_nodes}}{Number of bad nodes.}
\item{\code{nof_canupdates}}{Number of canrep updates.}
\item{\code{max_level}}{Maximum level.}
\item{\code{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.}
}
}
}
\references{
Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical
Labeling Tool for Large and Sparse Graphs, \emph{Proceedings of the
Ninth Workshop on Algorithm Engineering and Experiments and the
Fourth Workshop on Analytic Algorithms and Combinatorics.} 2007.
}
\author{Tommi Junttila for BLISS, Gabor Csardi
\email{csardi.gabor@gmail.com} for the igraph and R interfaces.}
\seealso{\code{\link{permute.vertices}} to apply a permutation to a
graph, \code{\link{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)))
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)
}
\keyword{graphs}
|