\HeaderA{graph.automorphisms}{Number of automorphisms}{graph.automorphisms}
\keyword{graphs}{graph.automorphisms}
\begin{Description}\relax
Calculate the number of automorphisms of a graph,
i.e. the number of isomorphisms to itself.
\end{Description}
\begin{Usage}
\begin{verbatim}
graph.automorphisms(graph, sh="fm")
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{graph}] The input graph, it is treated as undirected.
\item[\code{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.
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
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}.
\end{Details}
\begin{Value}
A named list with the following members:
\begin{ldescription}
\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.
\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.
\end{ldescription}
\end{Value}
\begin{Author}\relax
Tommi Juntilla \email{google@for.it} for BLISS and Gabor Csardi
\email{csardi@rmki.kfki.hu} for the igraph glue code and this manual
page.
\end{Author}
\begin{References}\relax
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.
\end{References}
\begin{SeeAlso}\relax
\code{\LinkA{canonical.permutation}{canonical.permutation}}, \code{\LinkA{permute.vertices}{permute.vertices}}
\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
## A ring has n*2 automorphisms, you can "turn" it by 0-9 vertices
## and each of these graphs can be "flipped"
g <- graph.ring(10)
graph.automorphisms(g)
\end{ExampleCode}
\end{Examples}

