Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/utils/rcm.py: 26%

1""" 

2Cuthill-McKee ordering of graph nodes to produce sparse matrices 

3""" 

4from collections import deque 

5from operator import itemgetter 

6 

7import networkx as nx 

8 

9from ..utils import arbitrary_element 

10 

11__all__ = ["cuthill_mckee_ordering", "reverse_cuthill_mckee_ordering"] 

12 

13 

14def cuthill_mckee_ordering(G, heuristic=None): 

15 """Generate an ordering (permutation) of the graph nodes to make 

16 a sparse matrix. 

17 

18 Uses the Cuthill-McKee heuristic (based on breadth-first search) [1]_. 

19 

20 Parameters 

21 ---------- 

22 G : graph 

23 A NetworkX graph 

24 

25 heuristic : function, optional 

26 Function to choose starting node for RCM algorithm. If None 

27 a node from a pseudo-peripheral pair is used. A user-defined function 

28 can be supplied that takes a graph object and returns a single node. 

29 

30 Returns 

31 ------- 

32 nodes : generator 

33 Generator of nodes in Cuthill-McKee ordering. 

34 

35 Examples 

36 -------- 

37 >>> from networkx.utils import cuthill_mckee_ordering 

38 >>> G = nx.path_graph(4) 

39 >>> rcm = list(cuthill_mckee_ordering(G)) 

40 >>> A = nx.adjacency_matrix(G, nodelist=rcm) 

41 

42 Smallest degree node as heuristic function: 

43 

44 >>> def smallest_degree(G): 

45 ... return min(G, key=G.degree) 

46 >>> rcm = list(cuthill_mckee_ordering(G, heuristic=smallest_degree)) 

47 

48 

49 See Also 

50 -------- 

51 reverse_cuthill_mckee_ordering 

52 

53 Notes 

54 ----- 

55 The optimal solution the bandwidth reduction is NP-complete [2]_. 

56 

57 

58 References 

59 ---------- 

60 .. [1] E. Cuthill and J. McKee. 

61 Reducing the bandwidth of sparse symmetric matrices, 

62 In Proc. 24th Nat. Conf. ACM, pages 157-172, 1969. 

63 http://doi.acm.org/10.1145/800195.805928 

64 .. [2] Steven S. Skiena. 1997. The Algorithm Design Manual. 

65 Springer-Verlag New York, Inc., New York, NY, USA. 

66 """ 

67 for c in nx.connected_components(G): 

68 yield from connected_cuthill_mckee_ordering(G.subgraph(c), heuristic) 

69 

70 

71def reverse_cuthill_mckee_ordering(G, heuristic=None): 

72 """Generate an ordering (permutation) of the graph nodes to make 

73 a sparse matrix. 

74 

75 Uses the reverse Cuthill-McKee heuristic (based on breadth-first search) 

76 [1]_. 

77 

78 Parameters 

79 ---------- 

80 G : graph 

81 A NetworkX graph 

82 

83 heuristic : function, optional 

84 Function to choose starting node for RCM algorithm. If None 

85 a node from a pseudo-peripheral pair is used. A user-defined function 

86 can be supplied that takes a graph object and returns a single node. 

87 

88 Returns 

89 ------- 

90 nodes : generator 

91 Generator of nodes in reverse Cuthill-McKee ordering. 

92 

93 Examples 

94 -------- 

95 >>> from networkx.utils import reverse_cuthill_mckee_ordering 

96 >>> G = nx.path_graph(4) 

97 >>> rcm = list(reverse_cuthill_mckee_ordering(G)) 

98 >>> A = nx.adjacency_matrix(G, nodelist=rcm) 

99 

100 Smallest degree node as heuristic function: 

101 

102 >>> def smallest_degree(G): 

103 ... return min(G, key=G.degree) 

104 >>> rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree)) 

105 

106 

107 See Also 

108 -------- 

109 cuthill_mckee_ordering 

110 

111 Notes 

112 ----- 

113 The optimal solution the bandwidth reduction is NP-complete [2]_. 

114 

115 References 

116 ---------- 

117 .. [1] E. Cuthill and J. McKee. 

118 Reducing the bandwidth of sparse symmetric matrices, 

119 In Proc. 24th Nat. Conf. ACM, pages 157-72, 1969. 

120 http://doi.acm.org/10.1145/800195.805928 

121 .. [2] Steven S. Skiena. 1997. The Algorithm Design Manual. 

122 Springer-Verlag New York, Inc., New York, NY, USA. 

123 """ 

124 return reversed(list(cuthill_mckee_ordering(G, heuristic=heuristic))) 

125 

126 

127def connected_cuthill_mckee_ordering(G, heuristic=None): 

128 # the cuthill mckee algorithm for connected graphs 

129 if heuristic is None: 

130 start = pseudo_peripheral_node(G) 

131 else: 

132 start = heuristic(G) 

133 visited = {start} 

134 queue = deque([start]) 

135 while queue: 

136 parent = queue.popleft() 

137 yield parent 

138 nd = sorted(G.degree(set(G[parent]) - visited), key=itemgetter(1)) 

139 children = [n for n, d in nd] 

140 visited.update(children) 

141 queue.extend(children) 

142 

143 

144def pseudo_peripheral_node(G): 

145 # helper for cuthill-mckee to find a node in a "pseudo peripheral pair" 

146 # to use as good starting node 

147 u = arbitrary_element(G) 

148 lp = 0 

149 v = u 

150 while True: 

151 spl = dict(nx.shortest_path_length(G, v)) 

152 l = max(spl.values()) 

153 if l <= lp: 

154 break 

155 lp = l 

156 farthest = (n for n, dist in spl.items() if dist == l) 

157 v, deg = min(G.degree(farthest), key=itemgetter(1)) 

158 return v