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
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/topology.R
\name{automorphism_group}
\alias{automorphism_group}
\title{Generating set of the automorphism group of a graph}
\usage{
automorphism_group(
graph,
colors = NULL,
sh = c("fm", "f", "fs", "fl", "flm", "fsm"),
details = FALSE
)
}
\arguments{
\item{graph}{The input graph, it is treated as undirected.}
\item{colors}{The colors of the individual vertices of the graph; only
vertices having the same color are allowed to match each other in an
automorphism. When omitted, igraph uses the \code{color} attribute of the
vertices, or, if there is no such vertex attribute, it simply assumes that
all vertices have the same color. Pass NULL explicitly if the graph has a
\code{color} vertex attribute but you do not want to use it.}
\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.}
\item{details}{Specifies whether to provide additional details about the
BLISS internals in the result.}
}
\value{
When \code{details} is \code{FALSE}, a list of vertex permutations
that form a generating set of the automorphism group of the input graph.
When \code{details} is \code{TRUE}, a named list with two members:
\item{generators}{Returns the generators themselves} \item{info}{Additional
information about the BLISS internals. See \code{\link[=count_automorphisms]{count_automorphisms()}} for
more details.}
}
\description{
Compute the generating set of the automorphism group of a graph.
}
\details{
An automorphism of a graph is a permutation of its vertices which brings the
graph into itself. The automorphisms of a graph form a group and there exists
a subset of this group (i.e. a set of permutations) such that every other
permutation can be expressed as a combination of these permutations. These
permutations are called the generating set of the automorphism group.
This function calculates a possible generating set of the automorphism of
a graph using the BLISS algorithm. See also the BLISS homepage at
\url{http://www.tcs.hut.fi/Software/bliss/index.html}. The calculated
generating set is not necessarily minimal, and it may depend on the splitting
heuristics used by BLISS.
}
\examples{
## A ring has n*2 automorphisms, and a possible generating set is one that
## "turns" the ring by one vertex to the left or right
g <- make_ring(10)
automorphism_group(g)
}
\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]{canonical_permutation()}}, \code{\link[=permute]{permute()}},
\code{\link[=count_automorphisms]{count_automorphisms()}}
Other graph automorphism:
\code{\link{count_automorphisms}()}
}
\author{
Tommi Junttila (\url{http://users.ics.aalto.fi/tjunttil/}) for BLISS,
Gabor Csardi \email{csardi.gabor@gmail.com} for the igraph glue code and
Tamas Nepusz \email{ntamas@gmail.com} for this manual page.
}
\concept{graph automorphism}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Isomorphism.html#igraph_automorphism_group}{\code{igraph_automorphism_group()}}.}
|
