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)
graph1
. See the sh
argument of
canonical.permutation
for possible values.graph2
. See the sh
argument of
canonical.permutation
for possible values.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:
graph1
to
graph2
if iso
is TRUE
, an empty numeric
vector otherwise.graph2
to
graph1
if iso
is TRUE
, an empty numeric
vector otherwise.graph1
. A named list, see the return value of
canonical.permutation
for details.graph2
. A named list, see the return value of
canonical.permutation
for details.graph.isocreate
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:
FALSE
is returned.igraph.isomorphic.34
is called.igraph.isomorphic.vf2
is called.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.
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.
graph.motifs
# 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)
Run the code above in your browser using DataLab