automorphism_group: Generating set of the automorphism group of a graph

In igraph: Network Analysis and Visualization

Generating set of the automorphism group of a graph

Description

Compute the 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

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 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 color vertex attribute but you do not want to use it.
sh	The splitting heuristics for the BLISS algorithm. Possible values are: ‘f’: first non-singleton cell, ‘fl’: first largest non-singleton cell, ‘fs’: first smallest non-singleton cell, ‘fm’: first maximally non-trivially connected non-singleton cell, ‘flm’: first largest maximally non-trivially connected non-singleton cell, ‘fsm’: first smallest maximally non-trivially connected non-singleton cell.
details	Specifies whether to provide additional details about the BLISS internals in the result.

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 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.

Value

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 count_automorphisms() for more details.

Related documentation in the C library

igraph_automorphism_group().

Author(s)

Tommi Junttila (http://users.ics.aalto.fi/tjunttil/) for BLISS, Gabor Csardi [e-mail] for the igraph glue code and Tamas Nepusz [e-mail] for this manual page.

References

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.

See Also

canonical_permutation(), permute(), count_automorphisms()

Other graph automorphism: count_automorphisms()

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)

igraph documentation built on Oct. 20, 2024, 1:06 a.m.