cuthill_mckee_ordering

cuthill_mckee_ordering(G, heuristic=None)

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

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

参数

G图表

网络X图表

heuristic函数，可选

函数选择RCM算法的起始节点。如果没有，则使用伪外围设备对中的节点。可以提供一个用户定义的函数，该函数接受图形对象并返回单个节点。

返回

nodes发电机

Cuthill-McKee排序中的节点生成器。

参见

reverse_cuthill_mckee_ordering

笔记

带宽缩减的最优解是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纽约公司，纽约，纽约，美国。

实例

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

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

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