graph-isomorphism

0th

Percentile

Graph Isomorphism

These functions deal with graph isomorphism.

Keywords
graphs
Usage
graph.isoclass(graph)
graph.isomorphic(graph1, graph2)
graph.isomorphic.vf2(graph1, graph2)
graph.isocreate(size, number, directed=TRUE)
Arguments
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.
Details

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.

Value

  • graph.isoclass returns a non-negative integer number.

    graph.isomorphic and graph.isomorphic.vf2 return a logical constant.

    graph.isocreate returns a graph object.

References

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.

See Also

graph.motifs

Aliases
  • graph.isoclass
  • graph.isocreate
  • graph.isomorphic
  • graph.isomorphic.vf2
Examples
# 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)
Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)

Community examples

Looks like there are no examples yet.