跳到内容

判断两个图是否同构

来源：R/topology.R
isomorphic.Rd

判断两个图是否同构

用法

isomorphic(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ...)

is_isomorphic_to(
  graph1,
  graph2,
  method = c("auto", "direct", "vf2", "bliss"),
  ...
)

参数

graph1

第一个图。

graph2

第二个图。

method

使用的方法。可能的值：‘auto’，‘direct’，‘vf2’，‘bliss’。请参阅下面的详细信息。

...

传递给各种方法的附加参数。

值

逻辑标量，如果图同构则为 TRUE。

‘auto’ 方法

它尝试根据两个图选择合适的方法。这是它使用的算法

  1. 如果两个图的阶和大小（即顶点和边的数量）不一致，则返回 FALSE。

  2. 如果图有三个或四个顶点，则使用 ‘direct’ 方法。

  3. 如果图是有向图，则使用 ‘vf2’ 方法。

  4. 否则使用 ‘bliss’ 方法。

‘direct’ 方法

此方法仅适用于具有三个或四个顶点的图，并且基于预先计算和存储的表。它没有任何额外的参数。

‘vf2’ 方法

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

vertex.color1, vertex.color2

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

edge.color1, edge.color2

可选的整数向量，用于给出边着色（子）图同构的边的颜色。 如果未给出，但图具有“color”边属性，则将使用它。 如果要忽略这些属性，请为这两个参数提供 NULL。

‘bliss’ 方法

使用 Junttila 和 Kaski 的 BLISS 算法，它适用于无向图。 对于两个图，调用 canonical_permutation() 然后调用 permute() 函数将它们转换为规范形式； 最后比较规范形式。 额外参数

sh

字符常量，用于 graph1 和 graph2 的 BLISS 算法中的启发式方法。 有关可能的值，请参见 canonical_permutation() 的 sh 参数。

sh 默认为 ‘fm’。

参考文献

Tommi Junttila 和 Petteri Kaski：Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics. 2007.

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.

参见

其他图同构：canonical_permutation()，count_isomorphisms()，count_subgraph_isomorphisms()，graph_from_isomorphism_class()，isomorphism_class()，isomorphisms()，subgraph_isomorphic()，subgraph_isomorphisms()

示例

# create some non-isomorphic graphs
g1 <- graph_from_isomorphism_class(3, 10)
g2 <- graph_from_isomorphism_class(3, 11)
isomorphic(g1, g2)
#> [1] FALSE

# create two isomorphic graphs, by permuting the vertices of the first
g1 <- sample_pa(30, m = 2, directed = FALSE)
g2 <- permute(g1, sample(vcount(g1)))
# should be TRUE
isomorphic(g1, g2)
#> [1] TRUE
isomorphic(g1, g2, method = "bliss")
#> [1] TRUE
isomorphic(g1, g2, method = "vf2")
#> [1] TRUE

# colored graph isomorphism
g1 <- make_ring(10)
g2 <- make_ring(10)
isomorphic(g1, g2)
#> [1] TRUE

V(g1)$color <- rep(1:2, length = vcount(g1))
V(g2)$color <- rep(2:1, length = vcount(g2))
# consider colors by default
count_isomorphisms(g1, g2)
#> [1] 10
# ignore colors
count_isomorphisms(g1, g2,
  vertex.color1 = NULL,
  vertex.color2 = NULL
)
#> [1] 20