R igraph 手册页

subgraph_isomorphic {igraph}

R 文档

判断一个图是否与另一个图的子图同构

描述

判断一个图是否与另一个图的子图同构

用法

subgraph_isomorphic(pattern, target, method = c("auto", "lad", "vf2"), ...)

is_subgraph_isomorphic_to(
  pattern,
  target,
  method = c("auto", "lad", "vf2"),
  ...
)

参数

pattern	较小的图，可以是有向图或无向图。无向图被视为具有互逆边的有向图。
目标	较大的图，可以是有向图或无向图。无向图被视为具有互逆边的有向图。
method	使用的方法。可能的值：‘auto’、‘lad’、‘vf2’。详见下文。
...	传递给各种方法的其他参数。

值

逻辑标量，如果pattern与target的（可能诱导的）子图同构，则为TRUE。

‘auto’ 方法

此方法当前始终选择‘lad’，因为它在大多数图上似乎都更优。

‘lad’ 方法

这是 Solnon 的 LAD 算法，请参阅下面的参考资料。它有以下额外的参数

domains

如果不是NULL，则指定匹配限制。它必须是target顶点集的列表，以数字顶点 ID 或符号顶点名称给出。列表的长度必须为vcount(pattern)，并且对于pattern中的每个顶点，它给出target中允许匹配的顶点。默认为NULL。

induced

逻辑标量，是否搜索诱导子图。默认为FALSE。

time.limit

计算的处理器时间限制，以秒为单位。默认为Inf，表示没有限制。

‘vf2’ 方法

此方法使用 Cordella、Foggia 等人的 VF2 算法，请参阅下面的参考资料。它支持顶点和边的颜色，并具有以下额外的参数

vertex.color1, vertex.color2

可选的整数向量，给出彩色图同构的顶点颜色。如果没有给出，但图有一个“color”顶点属性，那么它将被使用。如果您想忽略这些属性，请为这两个参数提供NULL。另请参见下面的示例。

edge.color1, edge.color2

可选的整数向量，给出边彩色（子）图同构的边颜色。如果没有给出，但图有一个“color”边属性，那么它将被使用。如果您想忽略这些属性，请为这两个参数提供NULL。

参考

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.

参见

其他图同构：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)

---