networkx.utils.rcm.cuthill_mckee_ordering

cuthill_mckee_ordering(G, heuristic=None)[源代码]

生成图形节点的顺序(排列)以生成稀疏矩阵。

使用Cuthill McKee启发式(基于广度优先搜索) [1].

参数:
  • G图表 )--网络图
  • 启发式的功能,可选 )--函数为RCM算法选择起始节点。如果没有,则使用伪外围设备对中的节点。可以提供一个用户定义函数,该函数接受一个图形对象并返回一个节点。
返回:

结点 --Cuthill McKee订单中的节点生成器。

返回类型:

generator

实际案例

>>> from networkx.utils import cuthill_mckee_ordering
>>> G = nx.path_graph(4)
>>> rcm = list(cuthill_mckee_ordering(G))
>>> A = nx.adjacency_matrix(G, nodelist=rcm) # doctest: +SKIP

最小度节点作为启发式函数:

>>> def smallest_degree(G):
...     return min(G, key=G.degree)
>>> rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree))

笔记

带宽缩减为np完全的最优解 [2].

工具书类

[1]E.Cuthill和J.McKee。减少稀疏对称矩阵的带宽。第二十四NAT。Conf.ACM,第157-172页,1969年。http://doi.acm.org/10.1145/800195.805928
[2]史蒂文斯·斯基纳。1997。算法设计手册。Springer Verlag纽约公司,纽约,纽约,美国。