R igraph 手册页

canonical_permutation {igraph}

R 文档

图的规范排列

描述

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

用法

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

参数

图	输入图，视为无向图。
colors	图中各个顶点的颜色；只有颜色相同的顶点才允许在自同构中相互匹配。 如果省略，igraph 将使用顶点的color属性，或者，如果没有此类顶点属性，则它只是假设所有顶点都具有相同的颜色。 如果图具有color顶点属性但您不想使用它，请显式传递 NULL。
sh	用于 BLISS 算法的启发式类型。 有关可能的值，请参见详细信息。

详细信息

canonical_permutation计算一个排列，该排列将图带入规范形式，由 BLISS 算法定义。 所有同构图都具有相同的规范形式。

有关 BLISS 的详细信息，请参见下面的论文。 此信息以及更多信息可在 http://www.tcs.hut.fi/Software/bliss/index.html 中找到。

sh 参数的可能值为

"f"

第一个非单例单元格。

"fl"

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

"fs"

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

"fm"

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

"flm"

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

"fsm"

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

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

值

具有以下成员的列表

labeling	将输入图带入规范形式的规范排列。 一个数字向量，第一个元素是顶点 0 的新标签，第二个元素是顶点 1 的新标签，等等。
info	有关 BLISS 计算的一些信息。 一个命名的列表，包含以下成员 "nof_nodes" 搜索树中的节点数。 "nof_leaf_nodes" 搜索树中的叶节点数。 "nof_bad_nodes" 坏节点的数量。 "nof_canupdates" Canrep 更新的数量。 "max_level" 最大级别。 "group_size" 输入图的自同构群的大小，以字符串形式表示。 字符串表示是必要的，因为组大小很容易超过可以在浮点数中精确表示的值。

作者

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

参考

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.

参见

permute 用于将排列应用于图，graph.isomorphic 用于确定图同构，可能基于规范标签。

示例

## 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)

---