R igraph 手册页

isomorphic {igraph}

R 文档

判断两个图是否同构

描述

判断两个图是否同构

用法

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 and 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.

参见

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

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

# colored graph isomorphism
g1 <- make_ring(10)
g2 <- make_ring(10)
isomorphic(g1, g2)

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)
# ignore colors
count_isomorphisms(g1, g2, vertex.color1 = NULL,
    vertex.color2 = NULL)

---