确定一个图是否与另一个图的子图同构

用法

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

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

参数

pattern: 较小的图，可以是有向图或无向图。无向图被视为具有互边的有向图。
target: 较大的图，可以是有向图或无向图。无向图被视为具有互边的有向图。
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.

参见

其他图同构: canonical_permutation(), 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)
#> [[1]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 2 1 7 6 5
#> 
#> [[2]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 2 3 4 5
#> 
#> [[3]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 4 3 2 5
#> 
#> [[4]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 8 4 5 6 9
#> 
#> [[5]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 5 4 8 9 6
#> 
#> [[6]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 9 4 5 7 6
#> 
#> [[7]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 5 4 6 7
#> 
#> [[8]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 5 4 3 2
#> 
#> [[9]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 4 5 1 7 6
#> 
#> [[10]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 7 5 4 9 6
#> 
#> [[11]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 5 2 3 4
#> 
#> [[12]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 5 2 1 7
#> 
#> [[13]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 2 5 6 7 1
#> 
#> [[14]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 9 6 7 5 4
#> 
#> [[15]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 5 6 9 8 4
#> 
#> [[16]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 4 6 7 1 5
#> 
#> [[17]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 7 6 9 4 5
#> 
#> [[18]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 7 6 4 5
#> 
#> [[19]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 7 1 2 5
#> 
#> [[20]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 8 9 6 5 4
#> 
subgraph_isomorphisms(pattern, target, induced = TRUE)
#> [[1]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 2 3 4 5
#> 
#> [[2]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 4 3 2 5
#> 
#> [[3]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 6 5 2 3 4
#> 
#> [[4]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 5 4 3 2
#> 
subgraph_isomorphisms(pattern, target, domains = domains)
#> [[1]]
#> + 5/9 vertices, named, from 63b67b0:
#> [1] 1 5 4 3 2
#> 

# Directed LAD example
pattern <- make_graph(~ 1:2:3, 1 -+ 2:3)
dring <- make_ring(10, directed = TRUE)
subgraph_isomorphic(pattern, dring)
#> [1] FALSE