| graph-isomorphism {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) 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)
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. |
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.
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. |
normal-bracket152bracket-normal
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.
Functions graph.isoclass, graph.isoclass.subgraph and
graph.isocreate are considered experimental and might be
reorganized/rewritten later.
Gabor Csardi csardi@rmki.kfki.hu
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.
# 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)