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) 

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

>>> 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纽约公司,纽约,纽约,美国。