isomorphic

0th

Percentile

Decide if two graphs are isomorphic

Decide if two graphs are isomorphic

Usage
isomorphic(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ...)

is_isomorphic_to(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ...)

Arguments
graph1
The first graph.
graph2
The second graph.
method
The method to use. Possible values: auto, direct, vf2, bliss. See their details below.
...
Additional arguments, passed to the various methods.
Value

  • Logical scalar, TRUE if the graphs are isomorphic.

auto method

It tries to select the appropriate method based on the two graphs. This is the algorithm it uses:

  1. If the two graphs do not agree on their order and size (i.e. number of vertices and edges), then returnFALSE.
  2. If the graphs have three or four vertices, then thedirectmethod is used.
  3. If the graphs are directed, then thevf2method is used.
  4. Otherwise theblissmethod is used.

direct method

This method only works on graphs with three or four vertices, and it is based on a pre-calculated and stored table. It does not have any extra arguments.

References

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.

See Also

Other graph isomorphism: count_isomorphisms, graph.count.isomorphisms.vf2; count_subgraph_isomorphisms, graph.count.subisomorphisms.vf2; graph.get.isomorphisms.vf2, isomorphisms; graph.get.subisomorphisms.vf2, subgraph_isomorphisms; graph.isoclass, graph.isoclass.subgraph, isomorphism_class; graph.isocreate, graph_from_isomorphism_class; graph.subisomorphic.lad, graph.subisomorphic.vf2, is_subgraph_isomorphic_to, subgraph_isomorphic

Aliases
  • graph.isomorphic
  • graph.isomorphic.34
  • graph.isomorphic.bliss
  • graph.isomorphic.vf2
  • is_isomorphic_to
  • isomorphic
Examples
# create some non-isomorphic graphs
g1 <- graph_from_isomorphism_class(3, 10)
g2 <- graph_from_isomorphism_class(3, 11)
isomorphic(g1, g2)

# create two isomorphic graphs, by permuting the vertices of the first
g1 <- barabasi.game(30, m=2, directed=FALSE)
g2 <- permute(g1, sample(vcount(g1)))
# should be TRUE
isomorphic(g1, g2)
isomorphic(g1, g2, method = "bliss")
isomorphic(g1, g2, method = "vf2")

# colored graph isomorphism
g1 <- make_ring(10)
g2 <- make_ring(10)
isomorphic(g1, g2)

V(g1)$color <- rep(1:2, length = vcount(g1))
V(g2)$color <- rep(2:1, length = vcount(g2))
# consider colors by default
count_isomorphisms(g1, g2)
# ignore colors
count_isomorphisms(g1, g2, vertex.color1 = NULL,
    vertex.color2 = NULL)
Documentation reproduced from package igraph, version 1.0.0, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.