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
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/topology.R
\name{canonical_permutation}
\alias{canonical.permutation}
\alias{canonical_permutation}
\title{Canonical permutation of a 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.}
}
\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{"nof_nodes"}{The number of nodes in the search tree.}
\item{"nof_leaf_nodes"}{The number of leaf nodes in the search tree.}
\item{"nof_bad_nodes"}{Number of bad nodes.}
\item{"nof_canupdates"}{Number of canrep updates.}
\item{"max_level"}{Maximum level.} \item{"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.} } }
}
\description{
The canonical permutation brings every isomorphic graphs into the same
(labeled) graph.
}
\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{"f"}{First non-singleton cell.} \item{"fl"}{First largest
non-singleton cell.} \item{"fs"}{First smallest non-singleton cell.}
\item{"fm"}{First maximally non-trivially connectec non-singleton
cell.} \item{"flm"}{Largest maximally non-trivially connected
non-singleton cell.} \item{"fsm"}{Smallest maximally non-trivially
connected non-singleton cell.} } See the paper in references for details
about these.
}
\examples{
## Calculate the canonical form of a random graph
g1 <- sample_gnm(10, 20)
cp1 <- canonical_permutation(g1)
cf1 <- permute(g1, cp1$labeling)
## Do the same with a random permutation of it
g2 <- permute(g1, sample(vcount(g1)))
cp2 <- canonical_permutation(g2)
cf2 <- permute(g2, cp2$labeling)
## Check that they are the same
el1 <- as_edgelist(cf1)
el2 <- as_edgelist(cf2)
el1 <- el1[ order(el1[,1], el1[,2]), ]
el2 <- el2[ order(el2[,1], el2[,2]), ]
all(el1 == el2)
}
\author{
Tommi Junttila for BLISS, Gabor Csardi
\email{csardi.gabor@gmail.com} for the igraph and R interfaces.
}
\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.
}
\seealso{
\code{\link{permute}} to apply a permutation to a graph,
\code{\link{graph.isomorphic}} for deciding graph isomorphism, possibly
based on canonical labels.
}
\keyword{graphs}
|
