跳到内容

图的规范置换

来源：R/topology.R
canonical_permutation.Rd

规范置换将每个同构图转换为相同的（标记）图。

用法

canonical_permutation(
  graph,
  colors = NULL,
  sh = c("fm", "f", "fs", "fl", "flm", "fsm")
)

参数

graph

输入图，视为无向图。

colors

图中各个顶点的颜色；只有具有相同颜色的顶点才允许在自同构中相互匹配。如果省略，igraph 会使用顶点的 color 属性，或者，如果不存在这样的顶点属性，它会简单地假设所有顶点都具有相同的颜色。如果图具有 color 顶点属性但您不想使用它，请显式传递 NULL。

sh

用于 BLISS 算法的启发式类型。有关可能的值，请参见详细信息。

值

具有以下成员的列表

labeling

将输入图转换为规范形式的规范置换。一个数值向量，第一个元素是顶点 0 的新标签，第二个元素是顶点 1 的新标签，依此类推。

info

有关 BLISS 计算的一些信息。一个命名列表，包含以下成员

"nof_nodes"

搜索树中的节点数。

"nof_leaf_nodes"

搜索树中的叶节点数。

"nof_bad_nodes"

坏节点数。

"nof_canupdates"

canrep 更新的数量。

"max_level"

最大级别。

"group_size"

输入图的自同构群的大小，以字符串形式表示。字符串表示是必要的，因为群的大小很容易超过可以用浮点数精确表示的值。

详细信息

canonical_permutation() 计算一个置换，该置换将图转换为 BLISS 算法定义的规范形式。所有同构图都具有相同的规范形式。

有关 BLISS 的详细信息，请参见下面的论文。更多信息请访问 http://www.tcs.hut.fi/Software/bliss/index.html。

sh 参数的可能值为

"f"

第一个非单例单元。

"fl"

第一个最大的非单例单元。

"fs"

第一个最小的非单例单元。

"fm"

第一个最大非平凡连接的非单例单元。

"flm"

最大的最大非平凡连接的非单例单元。

"fsm"

最小的最大非平凡连接的非单例单元。

有关这些的详细信息，请参见参考文献中的论文。

参考文献

Tommi Junttila 和 Petteri Kaski：Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs，第九届算法工程与实验研讨会和第四届分析算法与组合学研讨会论文集。 2007.

参见

permute() 将置换应用于图，isomorphic() 用于确定图同构，可能基于规范标签。

其他图同构：count_isomorphisms(), count_subgraph_isomorphisms(), graph_from_isomorphism_class(), isomorphic(), isomorphism_class(), isomorphisms(), subgraph_isomorphic(), subgraph_isomorphisms()

作者

Tommi Junttila 用于 BLISS，Gabor Csardi csardi.gabor@gmail.com 用于 igraph 和 R 接口。

canonical_permutation().

示例


## Calculate the canonical form of a random graph
g1 <- sample_gnm(10, 20)
cp1 <- canonical_permutation(g1)
cf1 <- permute(g1, cp1$labeling)

## Do the same with a random permutation of it
g2 <- permute(g1, sample(vcount(g1)))
cp2 <- canonical_permutation(g2)
cf2 <- permute(g2, cp2$labeling)

## Check that they are the same
el1 <- as_edgelist(cf1)
el2 <- as_edgelist(cf2)
el1 <- el1[order(el1[, 1], el1[, 2]), ]
el2 <- el2[order(el2[, 1], el2[, 2]), ]
all(el1 == el2)
#> [1] TRUE