计算一个图与另一个图的子图之间的同构映射数量

用法

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

参数

pattern: 较小的图，可以是有向图或无向图。无向图被视为具有互边的有向图。
target: 较大的图，可以是有向图或无向图。无向图被视为具有互边的有向图。
method: 使用的方法。可能的值：‘lad’、‘vf2’。请参阅下面的详细信息。
...: 传递给各种方法的附加参数。

值

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

‘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()、graph_from_isomorphism_class()、isomorphic()、isomorphism_class()、isomorphisms()、subgraph_isomorphic()、subgraph_isomorphisms()