Use this if you are using igraph from R
Decide if a graph is subgraph isomorphic to another one
subgraph_isomorphic(pattern, target, method = c("auto", "lad", "vf2"), ...) is_subgraph_isomorphic_to(pattern, target, method = c("auto", "lad", "vf2"), ...)
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. |
method |
The method to use. Possible values: ‘auto’, ‘lad’, ‘vf2’. See their details below. |
... |
Additional arguments, passed to the various methods. |
Logical scalar, TRUE
if the pattern
is
isomorphic to a (possibly induced) subgraph of target
.
This method currently selects ‘lad’, always, as it seems to be superior on most graphs.
This is the LAD algorithm by Solnon, see the reference below. It has the following extra arguments:
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 each vertex in
pattern
it gives the allowed matching vertices in
target
. Defaults to NULL
.
Logical scalar, whether to search for an induced
subgraph. It is FALSE
by default.
The processor time limit for the computation, in
seconds. It defaults to Inf
, which means no limit.
This method uses the VF2 algorithm by Cordella, Foggia et al., see references below. It supports vertex and edge colors and have the following extra arguments:
Optional integer vectors giving the
colors of the vertices for colored 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, then
supply NULL
for both of these arguments. See also examples
below.
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, then
supply NULL
for both of these arguments.
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.
Other graph isomorphism: count_isomorphisms
,
count_subgraph_isomorphisms
,
graph_from_isomorphism_class
,
isomorphic
,
isomorphism_class
,
isomorphisms
,
subgraph_isomorphisms
# A LAD example pattern <- make_graph(~ 1:2:3:4:5, 1 - 2:5, 2 - 1:5:3, 3 - 2:4, 4 - 3:5, 5 - 4:2:1) target <- make_graph(~ 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)) subgraph_isomorphisms(pattern, target) subgraph_isomorphisms(pattern, target, induced = TRUE) subgraph_isomorphisms(pattern, target, domains = domains) # Directed LAD example pattern <- make_graph(~ 1:2:3, 1 -+ 2:3) dring <- make_ring(10, directed = TRUE) subgraph_isomorphic(pattern, dring)