graph.automorphisms          package:igraph          R Documentation

_N_u_m_b_e_r _o_f _a_u_t_o_m_o_r_p_h_i_s_m_s

_D_e_s_c_r_i_p_t_i_o_n:

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

_U_s_a_g_e:

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

_A_r_g_u_m_e_n_t_s:

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

_D_e_t_a_i_l_s:

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

_V_a_l_u_e:

     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.

_A_u_t_h_o_r(_s):

     Tommi Juntilla google@for.it for BLISS and Gabor Csardi
     csardi@rmki.kfki.hu for the igraph glue code and this manual page.

_R_e_f_e_r_e_n_c_e_s:

     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.

_S_e_e _A_l_s_o:

     'canonical.permutation', 'permute.vertices'

_E_x_a_m_p_l_e_s:

     ## 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)

