# graph-isomorphism

0th

Percentile

##### Graph Isomorphism

These functions deal with graph isomorphism.

Keywords
graphs
##### Usage
graph.isomorphic(graph1, graph2)
graph.isomorphic.34(graph1, graph2)
graph.isomorphic.bliss(graph1, graph2, sh1="fm", sh2="fm")
graph.isomorphic.vf2(graph1, graph2, vertex.color1, vertex.color2,
edge.color1, edge.color2)graph.count.isomorphisms.vf2(graph1, graph2,
vertex.color1, vertex.color2,
edge.color1, edge.color2)
graph.get.isomorphisms.vf2(graph1, graph2,
vertex.color1, vertex.color2,
edge.color1, edge.color2)graph.subisomorphic.vf2(graph1, graph2,
vertex.color1, vertex.color2,
edge.color1, edge.color2)
graph.count.subisomorphisms.vf2(graph1, graph2,
vertex.color1, vertex.color2,
edge.color1, edge.color2)
graph.get.subisomorphisms.vf2(graph1, graph2,
vertex.color1, vertex.color2,
edge.color1, edge.color2)graph.subisomorphic.lad (pattern, target, domains = NULL,
induced = FALSE, map = TRUE, all.maps = FALSE,
time.limit = Inf)graph.isoclass(graph)
graph.isoclass.subgraph(graph, vids)
graph.isocreate(size, number, directed=TRUE)
##### Arguments
graph
A graph object.
graph1,graph2
Graph objects
vertex.color1,vertex.color2
Optional integer vectors giving the colors of the vertices for colored (sub)graph isomorphism. If they are not given, but the graph has a color vertex attribute, then it will be used. If you want to ignore these attributes, th
edge.color1,edge.color2
Optional integer vectors giving the colors of the edges for edge-colored (sub)graph isomorphism. If they are not given, but the graph has a color edge attribute, then it will be used. If you want to ignore these attributes, th
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.
pattern
The smaller graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.
target
The bigger graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.
domains
If not NULL, then it specifies matching restrictions. It must be a list of target vertex sets, given as numeric vertex ids or symbolic vertex names. The length of the list must be vcount(pattern) and for
induced
Logical scalar, whether to search for an induced subgraph. It is FALSE by default.
map
Logical scalar, whether to return a mapping between pattern and target. Defaults to TRUE.
all.maps
Logical scalar, whether to return all mappings between pattern and target. Defaults to FALSE.
time.limit
The processor time limit for the computation, in seconds. It defaults to Inf, which means no limit.
##### Details

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:

1. If the two graphs do not agree in the number of vertices and the number of edges thenFALSEis returned.
2. Otherwise if the graphs have 3 or 4 vertices, thenigraph.isomorphic.34is called.
3. Otherwise if the graphs are directed, thenigraph.isomorphic.vf2is called.
4. Otherwiseigraph.isomorphic.blissis 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.subisomorphic.lad checks whether pattern is isomorphic to a subgraph or induced subgraph of target. It can also optionally return a mapping, or all possible mappings between the two graphs. Its domains argument allows for a flexible way to restrict the matching to a subset of allowed vertices, individually for each vertex in pattern. 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.

##### Value

• 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:

• isoA logical scalar, whether the two graphs are isomorphic.
• map12A numeric vector, an mapping from graph1 to graph2 if iso is TRUE, an empty numeric vector otherwise.
• map21A numeric vector, an mapping from graph2 to graph1 if iso is TRUE, an empty numeric vector otherwise.
• info1Some information about the canonical form calculation for graph1. A named list, see the return value of canonical.permutation for details. Note that if the two graphs have different number of vertices or edges, then the BLISS algorithm is not run at all, and the contents of info1 is incorrect.
• info2Some information about the canonical form calculation for graph2. A named list, see the return value of canonical.permutation for details. Note that if the two graphs have different number of vertices or edges, then the BLISS algorithm is not run at all, and the contents of info2 is incorrect.
• graph.isomorphic.vf2 returns a names list with three elements:
• isoA logical scalar, whether the two graphs are isomorphic.
• map12A numeric vector, an mapping from graph1 to graph2 if iso is TRUE, an empty numeric vector otherwise.
• map21A numeric vector, an mapping from graph2 to graph1 if iso is TRUE, an empty numeric vector otherwise.
• graph.count.isomorphisms.vf2 returns a numeric scalar, an integer, the number of isomorphic mappings between the two input graphs.

graph.get.isomorphisms.vf2 returns a list of numeric vectors. Every numeric vector is a permutation which takes graph2 into graph1.

graph.subisomorphic.vf2 returns a named list with three elements:

• isoLogical scalar, TRUE if a subgraph of graph1 is isomorphic to graph2.
• map12Numeric 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.
• map21Numeric vector, empty if iso is FALSE. Otherwise a mapping from graph2 into graph1.
• 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.subisomorphic.lad return a named list with three entries:

• isoLogical scalar, whether the algorithm found a subgraph (or induced subgraph is the induced argument in TRUE) in target that is isomorphic to pattern.
• mapIf a mapping is requested via the map argument, then a numeric vector of vertex ids from target, the matching vertices for each pattern vertex in pattern vertex id order. Otherwise NULL.
• mapsIf all mappings are requested via the all.maps argument, then all possible mappings from pattern to target, in a list of vectors, where each vector is in the same format as map just above.
• graph.isoclass and graph.isoclass.subgraph return a non-negative integer number.

graph.isocreate returns a graph object.

##### Note

Functions graph.isoclass, graph.isoclass.subgraph and graph.isocreate are considered experimental and might be reorganized/rewritten later.

##### concept

• Graph isomorphism
• Subgraph isomorphism
• VF2 algorithm
• BLISS algorithm

##### 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.

C. Solnon: AllDifferent-based Filtering for Subgraph Isomorphism, Artificial Intelligence 174(12-13):850--864, 2010.

graph.motifs

##### Aliases
• graph.isoclass
• graph.isocreate
• graph.isomorphic
• graph.isomorphic.vf2
• graph.count.isomorphisms.vf2
• graph.count.subisomorphisms.vf2
• graph.get.isomorphisms.vf2
• graph.get.subisomorphisms.vf2
• graph.isoclass.subgraph
• graph.isomorphic.34
• graph.isomorphic.bliss
• graph.subisomorphic.vf2
##### Examples
# 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 <- barabasi.game(30, m=2, directed=FALSE)
g2 <- permute.vertices(g1, sample(vcount(g1)))
# should be TRUE
graph.isomorphic(g1, g2)
graph.isomorphic.bliss(g1, g2)
graph.isomorphic.vf2(g1, g2)

# colored graph isomorphism
g1 <- graph.ring(10)
g2 <- graph.ring(10)
graph.isomorphic.vf2(g1, g2)

V(g1)$color <- rep(1:2, length=vcount(g1)) V(g2)$color <- rep(2:1, length=vcount(g2))
graph.count.isomorphisms.vf2(g1, g2)
graph.count.isomorphisms.vf2(g1, g2, vertex.color1=NULL,
vertex.color2=NULL)

V(g1)$name <- letters[1:vcount(g1)] V(g2)$name <- LETTERS[1:vcount(g2)]
graph.get.isomorphisms.vf2(g1, g2)

V(g1)$color <- 1 V(g2)$color <- 2
graph.isomorphic.vf2(g1, g2)
graph.isomorphic.vf2(g2, g2, vertex.color1=NULL,
vertex.color2=NULL)

# The LAD example
pattern <- graph.formula(1:2:3:4:5,
1 - 2:5, 2 - 1:5:3, 3 - 2:4, 4 - 3:5, 5 - 4:2:1)
target <- graph.formula(1:2:3:4:5:6:7:8:9,
1 - 2:5:7, 2 - 1:5:3, 3 - 2:4, 4 - 3:5:6:8:9,
5 - 1:2:4:6:7, 6 - 7:5:4:9, 7 - 1:5:6,
8 - 4:9, 9 - 6:4:8)
domains <- list(1 = c(1,3,9), 2 = c(5,6,7,8), 3 = c(2,4,6,7,8,9),
4 = c(1,3,9), 5 = c(2,4,8,9))
graph.subisomorphic.lad(pattern, target, induced=TRUE, all.maps=TRUE)
graph.subisomorphic.lad(pattern, target, domains=domains, all.maps=TRUE)

# Directed LAD example
pattern <- graph.formula(1:2:3, 1 -+ 2:3)
uring <- graph.ring(10)
dring <- graph.ring(10, directed=TRUE)
graph.subisomorphic.lad(pattern, dring)