graph-isomorphism           package:igraph           R Documentation

_G_r_a_p_h _I_s_o_m_o_r_p_h_i_s_m

_D_e_s_c_r_i_p_t_i_o_n:

     These functions deal with graph isomorphism.

_U_s_a_g_e:

     graph.isomorphic(graph1, graph2)
     graph.isomorphic.34(graph1, graph2)
     graph.isomorphic.bliss(graph1, graph2, sh1="fm", sh2="fm")
     graph.isomorphic.vf2(graph1, graph2)

     graph.count.isomorphisms.vf2(graph1, graph2)
     graph.get.isomorphisms.vf2(graph1, graph2)

     graph.subisomorphic.vf2(graph1, graph2)
     graph.count.subisomorphisms.vf2(graph1, graph2)
     graph.get.subisomorphisms.vf2(graph1, graph2)

     graph.isoclass(graph)
     graph.isoclass.subgraph(graph, vids)
     graph.isocreate(size, number, directed=TRUE)

_A_r_g_u_m_e_n_t_s:

   graph: A graph object.

graph1,graph2: Graph objects

    size: A numeric integer giving the number of vertices in the graph
          to create. Only three or four are suppported right now.

  number: The number of the isomorphism class of the graph to be
          created.

directed: Whether to create a directed graph.

     sh1: Character constant, the heuristics to use in the BLISS
          algorithm, for 'graph1'. See the 'sh' argument of
          'canonical.permutation' for possible values.

     sh2: Character constant, the heuristics to use in the BLISS
          algorithm, for 'graph2'. See the 'sh' argument of
          'canonical.permutation' for possible values.

    vids: Numeric vector, the vertex ids of vertices to form the
          induced subgraph for determining the isomorphism class.

_D_e_t_a_i_l_s:

     'graph.isomorphic' decides whether two graphs are isomorphic. The
     input graphs must be both directed or both undirected. This
     function is a higher level interface to the other graph
     isomorphism decision functions. Currently it does the following:

        1.  If the two graphs do not agree in the number of vertices
           and the number of edges then 'FALSE' is returned.

        2.  Otherwise if the graphs have 3 or 4 vertices, then
           'igraph.isomorphic.34' is called.

        3.  Otherwise if the graphs are directed, then
           'igraph.isomorphic.vf2' is called.

        4.  Otherwise 'igraph.isomorphic.bliss' is called.

     'igraph.isomorphic.34' decides whether two graphs, both of which
     contains only 3 or 4 vertices, are isomorphic. It works based on a
     precalculated and stored table.

     'igraph.isomorphic.bliss' uses the BLISS algorithm by Junttila and
     Kaski, and it works for undirected graphs. For both graphs the
     'canonical.permutation' and then the 'permute.vertices' function
     is called to transfer them into canonical form; finally the
     canonical forms are compared.

     'graph.isomorphic.vf2' decides whethe two graphs are isomorphic,
     it implements the VF2 algorithm, by Cordella, Foggia et al., see
     references.

     'graph.count.isomorphisms.vf2' counts the different isomorphic
     mappings between 'graph1' and 'graph2'. (To count automorphisms
     you can supply the same graph twice, but it is better to call
     'graph.automorphisms'.) It uses the VF2 algorithm.

     'graph.get.isomorphisms.vf2' calculates all isomorphic mappings
     between 'graph1' and 'graph2'. It uses the VF2 algorithm.

     'graph.subisomorphic.vf2' decides whether 'graph2' is isomorphic
     to some subgraph of 'graph1'. It uses the VF2 algorithm.

     'graph.count.subisomorphisms.vf2' counts the different isomorphic
     mappings between 'graph2' and the subgraphs of 'graph1'. It uses
     the VF2 algorithm.

     'graph.get.subisomorphisms.vf2' calculates all isomorphic mappings
     between 'graph2' and the subgraphs of 'graph1'. It uses the VF2
     algorithm.

     'graph.isoclass' returns the isomorphism class of a graph, a
     non-negative integer number. Graphs (with the same number of
     vertices) having the same isomorphism class are isomorphic and
     isomorphic graphs always have the same isomorphism class.
     Currently it can handle only graphs with 3 or 4 vertices.

     'graph.isoclass.subgraph' calculates the isomorphism class of a
     subgraph of the input graph. Currently it only works for subgraphs
     with 3 or 4 vertices.

     'graph.isocreate' create a graph from the given isomorphic class.
     Currently it can handle only graphs with 3 or 4 vertices.

_V_a_l_u_e:

     'graph.isomorphic' and 'graph.isomorphic.34' return a logical
     scalar, 'TRUE' if the input graphs are isomorphic, 'FALSE'
     otherwise.

     'graph.isomorphic.bliss' returns a named list with elements: 

     iso: A logical scalar, whether the two graphs are isomorphic.

   map12: A numeric vector, an mapping from 'graph1' to 'graph2' if
          'iso' is 'TRUE', an empty numeric vector otherwise.

   map21: A numeric vector, an mapping from 'graph2' to 'graph1' if
          'iso' is 'TRUE', an empty numeric vector otherwise.

   info1: Some information about the canonical form calculation for
          'graph1'. A named list, see the return value of
          'canonical.permutation' for details. 

   info2: Some information about the canonical form calculation for
          'graph2'. A named list, see the return value of
          'canonical.permutation' for details. 

     iso: A logical scalar, whether the two graphs are isomorphic.

   map12: A numeric vector, an mapping from 'graph1' to 'graph2' if
          'iso' is 'TRUE', an empty numeric vector otherwise.

   map21: A numeric vector, an mapping from 'graph2' to 'graph1' if
          'iso' is 'TRUE', an empty numeric vector otherwise.

     iso: Logical scalar, 'TRUE' if a subgraph of 'graph1' is
          isomorphic to 'graph2'.

   map12: Numeric vector, empty if 'iso' is 'FALSE'. Otherwise a
          mapping from a subgraph of 'graph1' to 'graph2'. -1 denotes
          the vertices which are not part of the mapping.

   map21: Numeric vector, empty if 'iso' is 'FALSE'. Otherwise a
          mapping from 'graph2' into 'graph1'.


     'graph.count.subisomorphisms.vf2' returns a numeric scalar, an
     integer.

     'graph.get.subisomorphisms.vf2' returns a list of numeric vectors,
     each numeric vector is an isomorphic mapping from 'graph2' to a
     subgraph of 'graph1'.

     'graph.isoclass' and 'graph.isoclass.subgraph' return a
     non-negative integer number. 

     'graph.isocreate' returns a graph object.

_N_o_t_e:

     Functions 'graph.isoclass', 'graph.isoclass.subgraph' and
     'graph.isocreate' are considered experimental and might be
     reorganized/rewritten later.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

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

     LP Cordella,  P Foggia, C Sansone, and M Vento: An improved
     algorithm for matching large graphs, _Proc. of the 3rd IAPR TC-15
     Workshop on Graphbased Representations in Pattern Recognition_,
     149-159, 2001.

_S_e_e _A_l_s_o:

     'graph.motifs'

_E_x_a_m_p_l_e_s:

     # create some non-isomorphic graphs
     g1 <- graph.isocreate(3, 10)
     g2 <- graph.isocreate(3, 11)
     graph.isoclass(g1)
     graph.isoclass(g2)
     graph.isomorphic(g1, g2)

     # create two isomorphic graphs, by
     # permuting the vertices of the first 
     g1 <- simplify(barabasi.game(30, m=2, directed=FALSE))
     g2 <- permute.vertices(g1, sample(vcount(g1))-1)
     # should be TRUE
     graph.isomorphic(g1, g2)
     graph.isomorphic.bliss(g1, g2)
     graph.isomorphic.vf2(g1, g2)

