canonical.permutation         package:igraph         R Documentation

_C_a_n_o_n_i_c_a_l _p_e_r_m_u_t_a_t_i_o_n _o_f _a _g_r_a_p_h

_D_e_s_c_r_i_p_t_i_o_n:

     The canonical permutation brings every isomorphic graphs into the
     same (labeled) graphs.

_U_s_a_g_e:

     canonical.permutation(graph, sh="fm")

_A_r_g_u_m_e_n_t_s:

   graph: The input graph, treated as undirected.

      sh: Type of the heuristics to use for the BLISS algorithm. See
          details for possible values.

_D_e_t_a_i_l_s:

     'canonical.permutation' computes a permutation which brings the
     graph into canonical form, as defined by the BLISS algorithm. All
     isomorphic graphs have the same canonical form.

     See the paper below for the details about BLISS. This and more
     information is available at <URL:
     http://www.tcs.hut.fi/Software/bliss/index.html>.

     The possible values for the 'sh' argument are:

   _f First non-singleton cell.

   _f_l First largest non-singleton cell.

   _f_s First smallest non-singleton cell.

   _f_m First maximally non-trivially connectec non-singleton cell.

   _f_l_m Largest maximally non-trivially connected non-singleton cell.

   _f_s_m Smallest maximally non-trivially connected non-singleton cell.

     See the paper in references for details about these.

_V_a_l_u_e:

     A list with the following members: 

labeling: The canonical parmutation which takes the input graph into
          canonical form. A numeric vector, the first element is the
          new label of vertex 0, the second element for vertex 1, etc. 

    info: Some information about the BLISS computation. A named list
          with the following members:

        _n_o_f__n_o_d_e_s The number of nodes in the search tree.

        _n_o_f__l_e_a_f__n_o_d_e_s The number of leaf nodes in the search tree.

        _n_o_f__b_a_d__n_o_d_e_s Number of bad nodes.

        _n_o_f__c_a_n_u_p_d_a_t_e_s Number of canrep updates.

        _m_a_x__l_e_v_e_l Maximum level.

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

_A_u_t_h_o_r(_s):

     Tommi Junttila for BLISS, Gabor Csardi csardi@rmki.kfki.hu for the
     igraph and R interfaces.

_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:

     'permute.vertices' to apply a permutation to a graph,
     'graph.isomorphic' for deciding graph isomorphism, possibly based
     on canonical labels.

_E_x_a_m_p_l_e_s:

     ## Calculate the canonical form of a random graph
     g1 <- erdos.renyi.game(10, 20, type="gnm")
     cp1 <- canonical.permutation(g1)
     cf1 <- permute.vertices(g1, cp1$labeling)

     ## Do the same with a random permutation of it
     g2 <- permute.vertices(g1, sample(vcount(g1))-1)
     cp2 <- canonical.permutation(g2)
     cf2 <- permute.vertices(g2, cp2$labeling)

     ## Check that they are the same
     el1 <- get.edgelist(cf1)
     el2 <- get.edgelist(cf2)
     el1 <- el1[ order(el1[,1], el1[,2]), ]
     el2 <- el2[ order(el2[,1], el2[,2]), ]
     all(el1 == el2)

