graphisomorphism {igraph}  R Documentation 
These functions deal with graph isomorphism.
graph.isomorphic(graph1, graph2) graph.isomorphic.34(graph1, graph2) graph.isomorphic.bliss(graph1, graph2, sh1="fm", sh2="fm") graph.isomorphic.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.count.isomorphisms.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.get.isomorphisms.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.subisomorphic.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.count.subisomorphisms.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.get.subisomorphisms.vf2(graph1, graph2, vertex.color1, vertex.color2, edge.color1, edge.color2) graph.isoclass(graph) graph.isoclass.subgraph(graph, vids) graph.isocreate(size, number, directed=TRUE)
graph 
A graph object. 
graph1,graph2 
Graph objects 
vertex.color1,vertex.color2 
Optional integer vectors giving the colors of the
vertices for colored (sub)graph isomorphism. If they are not given,
but the graph has a “color” vertex attribute, then it will be
used. If you want to ignore these attributes, then supply

edge.color1,edge.color2 
Optional integer vectors giving the colors of the edges
for edgecolored (sub)graph isomorphism. If they are not given,
but the graph has a “color” edge attribute, then it will be
used. If you want to ignore these attributes, then supply

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 
sh2 
Character constant, the heuristics to use in the BLISS
algorithm, for 
vids 
Numeric vector, the vertex ids of vertices to form the induced subgraph for determining the isomorphism class. 
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:
If the two graphs do not agree in the number of vertices and
the number of edges then FALSE
is returned.
Otherwise if the graphs have 3 or 4 vertices, then
igraph.isomorphic.34
is called.
Otherwise if the graphs are directed, then
igraph.isomorphic.vf2
is called.
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
nonnegative 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.
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 
map21 
A numeric vector, an mapping from 
info1 
Some information about the canonical form calculation
for 
info2 
Some information about the canonical form calculation
for 
graph.isomorphic.vf2
returns a names list with three elements:
iso 
A logical scalar, whether the two graphs are isomorphic. 
map12 
A numeric vector, an mapping from 
map21 
A numeric vector, an mapping from 
graph.count.isomorphisms.vf2
returns a numeric scalar, an
integer, the number of isomorphic mappings between the two input
graphs.
graph.get.isomorphisms.vf2
returns a list of numeric
vectors. Every numeric vector is a permutation which takes
graph2
into graph1
.
graph.subisomorphic.vf2
returns a named list with three
elements:
iso 
Logical scalar, 
map12 
Numeric vector, empty if 
map21 
Numeric vector, empty if 
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
nonnegative integer number.
graph.isocreate
returns a graph object.
Functions graph.isoclass
, graph.isoclass.subgraph
and
graph.isocreate
are considered experimental and might be
reorganized/rewritten later.
Gabor Csardi csardi.gabor@gmail.com
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 TC15 Workshop on Graphbased Representations in Pattern Recognition, 149–159, 2001.
# create some nonisomorphic 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 < barabasi.game(30, m=2, directed=FALSE) g2 < permute.vertices(g1, sample(vcount(g1))) # should be TRUE graph.isomorphic(g1, g2) graph.isomorphic.bliss(g1, g2) graph.isomorphic.vf2(g1, g2) # colored graph isomorphism g1 < graph.ring(10) g2 < graph.ring(10) graph.isomorphic.vf2(g1, g2) V(g1)$color < rep(1:2, length=vcount(g1)) V(g2)$color < rep(1:2, length=vcount(g2)) graph.count.isomorphisms.vf2(g1, g2) graph.count.isomorphisms.vf2(g1, g2, vertex.color1=NULL, vertex.color2=NULL) V(g1)$color < 1 V(g2)$color < 2 graph.isomorphic.vf2(g1, g2) graph.isomorphic.vf2(g2, g2, vertex.color1=NULL, vertex.color2=NULL)