igraph (version 0.6-1)

graph.automorphisms: Number of automorphisms

Description

Calculate the number of automorphisms of a graph, i.e. the number of isomorphisms to itself.

Usage

graph.automorphisms(graph, sh="fm")

Arguments

graph
The input graph, it is treated as undirected.
sh
The splitting heuristics for the BLISS algorithm. Possible values are: f: first non-singleton cell, fl: first largest non-singleton cell, fs: first small

Value

  • A named list with the following members:
  • group_sizeThe 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_nodesThe number of nodes in the search tree.
  • nof_leaf_nodesThe number of leaf nodes in the search tree.
  • nof_bad_nodesNumber of bad nodes.
  • nof_canupdatesNumber of canrep updates.
  • max_levelMaximum level.

concept

Graph automorphism

Details

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.

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

Examples

Run this code
## 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)

Run the code above in your browser using DataCamp Workspace