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
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/topology.R
\name{automorphisms}
\alias{automorphisms}
\alias{graph.automorphisms}
\title{Number of automorphisms}
\usage{
automorphisms(graph, sh = "fm")
}
\arguments{
\item{graph}{The input graph, it is treated as undirected.}
\item{sh}{The splitting heuristics for the BLISS algorithm. Possible values
are: \sQuote{\code{f}}: first non-singleton cell, \sQuote{\code{fl}}: first
largest non-singleton cell, \sQuote{\code{fs}}: first smallest non-singleton
cell, \sQuote{\code{fm}}: first maximally non-trivially connected
non-singleton cell, \sQuote{\code{flm}}: first largest maximally
non-trivially connected non-singleton cell, \sQuote{\code{fsm}}: first
smallest maximally non-trivially connected non-singleton cell.}
}
\value{
A named list with the following members: \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.} \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.}
}
\description{
Calculate the number of automorphisms of a graph, i.e. the number of
isomorphisms to itself.
}
\details{
An automorphism of a graph is a permutation of its vertices which brings the
graph into itself.
This function calculates the number of automorphism of a graph using the
BLISS algorithm. See also the BLISS homepage at
\url{http://www.tcs.hut.fi/Software/bliss/index.html}.
}
\examples{
## A ring has n*2 automorphisms, you can "turn" it by 0-9 vertices
## and each of these graphs can be "flipped"
g <- make_ring(10)
automorphisms(g)
}
\author{
Tommi Junttila (\url{http://users.ics.aalto.fi/tjunttil/}) for BLISS
and Gabor Csardi \email{csardi.gabor@gmail.com} for the igraph glue code
and this manual page.
}
\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{canonical_permutation}}, \code{\link{permute}}
}
\keyword{graphs}
|
