Use this if you are using igraph from R
Compute the generating set of the automorphism group of a graph.
automorphism_group(graph, colors, sh = "fm", details = FALSE)
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: ‘ |
details |
Specifies whether to provide additional details about the BLISS internals in the result. |
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 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.
When details
is FALSE
, a list of vertex permutations
that form a generating set of the automorphism group of the input graph.
When details
is TRUE
, a named list with two members:
generators |
Returns the generators themselves |
info |
Additional
information about the BLISS internals. See |
Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) for BLISS, Gabor Csardi csardi.gabor@gmail.com for the igraph glue code and Tamas Nepusz ntamas@gmail.com for 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
,
automorphisms
## 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)