graph-isomorphism {igraph} | R Documentation |
These functions deal with graph isomorphism.
graph.isoclass(graph) graph.isomorphic(graph1, graph2) graph.isomorphic.vf2(graph1, graph2) 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. |
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.
graph.isomorphic
decides whether two graphs are isomorphic.
graph.isomorphic.vf2
decides whethe two graphs are isomorphic,
it implements the VF2 algorithm, see references.
graph.isocreate
create a graph from the given isomorphic
class.
These functions are considered as experimental, as
graph.isomorphic
, graph.isoclass
and
graph.isocreate
can handle only graphs with three of four
vertices.
It is quite likely that some graph.isomorphic
will be able to
call graph.isomorphic.vf2
in some later igraph version.
graph.isoclass
returns a non-negative integer number.
graph.isomorphic
and graph.isomorphic.vf2
return a logical constant.
graph.isocreate
returns a graph object.
Gabor Csardi csardi@rmki.kfki.hu
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.isomorphic(g1, g2) # create two isomorphic graphs, by # permuting the vertices of the first g1 <- barabasi.game(30, m=2, directed=FALSE) el <- get.edgelist(g1) iso <- sample(vcount(g1))-1 el <- matrix(iso[ el+1 ], nc=2) g2 <- graph(t(el), directed=FALSE) graph.isomorphic.vf2(g1, g2)