Use this if you are using igraph from R
Calculate the number of automorphisms of a graph, i.e. the number of isomorphisms to itself.
automorphisms(graph, colors, sh = "fm")
graph |
The input graph, it is treated as undirected. |
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 |
sh |
The splitting heuristics for the BLISS algorithm. Possible values
are: ‘ |
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
http://www.tcs.hut.fi/Software/bliss/index.html. If you need the
automorphisms themselves, use automorphism_group
to obtain
a compact representation of the automorphism group.
A named list with the following members:
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. |
nof_nodes |
The number of nodes in the search tree. |
nof_leaf_nodes |
The number of leaf nodes in the search tree. |
nof_bad_nodes |
Number of bad nodes. |
nof_canupdates |
Number of canrep updates. |
max_level |
Maximum level. |
Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) for BLISS and Gabor Csardi csardi.gabor@gmail.com for the igraph glue code and this manual page.
Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.
canonical_permutation
, permute
,
and automorphism_group
for a compact representation of all
automorphisms
## 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) ## A full graph has n! automorphisms; however, we restrict the vertex ## matching by colors, leading to only 4 automorphisms g <- make_full_graph(4) automorphisms(g, colors=c(1,2,1,2))