1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/topology.R
\name{subgraph_isomorphic}
\alias{graph.subisomorphic.lad}
\alias{graph.subisomorphic.vf2}
\alias{is_subgraph_isomorphic_to}
\alias{subgraph_isomorphic}
\title{Decide if a graph is subgraph isomorphic to another one}
\usage{
subgraph_isomorphic(pattern, target, method = c("auto", "lad", "vf2"), ...)
is_subgraph_isomorphic_to(pattern, target, method = c("auto", "lad", "vf2"),
...)
}
\arguments{
\item{pattern}{The smaller graph, it might be directed or
undirected. Undirected graphs are treated as directed graphs with
mutual edges.}
\item{target}{The bigger graph, it might be directed or
undirected. Undirected graphs are treated as directed graphs with
mutual edges.}
\item{method}{The method to use. Possible values: \sQuote{auto},
\sQuote{lad}, \sQuote{vf2}. See their details below.}
\item{...}{Additional arguments, passed to the various methods.}
}
\value{
Logical scalar, \code{TRUE} if the \code{pattern} is
isomorphic to a (possibly induced) subgraph of \code{target}.
}
\description{
Decide if a graph is subgraph isomorphic to another one
}
\section{\sQuote{auto} method}{
This method currently selects \sQuote{lad}, always, as it seems
to be superior on most graphs.
}
\section{\sQuote{lad} method}{
This is the LAD algorithm by Solnon, see the reference below. It has
the following extra arguments:
\describe{
\item{domains}{If not \code{NULL}, then it specifies matching
restrictions. It must be a list of \code{target} vertex sets, given
as numeric vertex ids or symbolic vertex names. The length of the
list must be \code{vcount(pattern)} and for each vertex in
\code{pattern} it gives the allowed matching vertices in
\code{target}. Defaults to \code{NULL}.}
\item{induced}{Logical scalar, whether to search for an induced
subgraph. It is \code{FALSE} by default.}
\item{time.limit}{The processor time limit for the computation, in
seconds. It defaults to \code{Inf}, which means no limit.}
}
}
\section{\sQuote{vf2} method}{
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:
\describe{
\item{vertex.color1, vertex.color2}{Optional integer vectors giving the
colors of the vertices for colored graph isomorphism. If they
are not given, but the graph has a \dQuote{color} vertex attribute,
then it will be used. If you want to ignore these attributes, then
supply \code{NULL} for both of these arguments. See also examples
below.}
\item{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 \dQuote{color} edge attribute,
then it will be used. If you want to ignore these attributes, then
supply \code{NULL} for both of these arguments.}
}
}
\examples{
# 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)
uring <- make_ring(10)
dring <- make_ring(10, directed = TRUE)
subgraph_isomorphic(pattern, uring)
subgraph_isomorphic(pattern, dring)
}
\references{
LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm
for matching large graphs, \emph{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,
\emph{Artificial Intelligence} 174(12-13):850--864, 2010.
}
\seealso{
Other graph isomorphism: \code{\link{count_isomorphisms}},
\code{\link{graph.count.isomorphisms.vf2}};
\code{\link{count_subgraph_isomorphisms}},
\code{\link{graph.count.subisomorphisms.vf2}};
\code{\link{graph.get.isomorphisms.vf2}},
\code{\link{isomorphisms}};
\code{\link{graph.get.subisomorphisms.vf2}},
\code{\link{subgraph_isomorphisms}};
\code{\link{graph.isoclass}},
\code{\link{graph.isoclass.subgraph}},
\code{\link{isomorphism_class}};
\code{\link{graph.isocreate}},
\code{\link{graph_from_isomorphism_class}};
\code{\link{graph.isomorphic}},
\code{\link{graph.isomorphic.34}},
\code{\link{graph.isomorphic.bliss}},
\code{\link{graph.isomorphic.vf2}},
\code{\link{is_isomorphic_to}}, \code{\link{isomorphic}}
}
|
