Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/utils/rcm.py: 27%

1""" 

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

3""" 

4 

5from collections import deque 

6from operator import itemgetter 

7 

8import networkx as nx 

9 

10from ..utils import arbitrary_element 

11 

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

13 

14 

15def cuthill_mckee_ordering(G, heuristic=None): 

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

17 a sparse matrix. 

18 

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

20 

21 Parameters 

22 ---------- 

23 G : graph 

24 A NetworkX graph 

25 

26 heuristic : function, optional 

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

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

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

30 

31 Returns 

32 ------- 

33 nodes : generator 

34 Generator of nodes in Cuthill-McKee ordering. 

35 

36 Examples 

37 -------- 

38 >>> from networkx.utils import cuthill_mckee_ordering 

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

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

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

42 

43 Smallest degree node as heuristic function: 

44 

45 >>> def smallest_degree(G): 

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

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

48 

49 

50 See Also 

51 -------- 

52 reverse_cuthill_mckee_ordering 

53 

54 Notes 

55 ----- 

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

57 

58 

59 References 

60 ---------- 

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

62 Reducing the bandwidth of sparse symmetric matrices, 

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

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

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

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

67 """ 

68 for c in nx.connected_components(G): 

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

70 

71 

72def reverse_cuthill_mckee_ordering(G, heuristic=None): 

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

74 a sparse matrix. 

75 

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

77 [1]_. 

78 

79 Parameters 

80 ---------- 

81 G : graph 

82 A NetworkX graph 

83 

84 heuristic : function, optional 

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

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

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

88 

89 Returns 

90 ------- 

91 nodes : generator 

92 Generator of nodes in reverse Cuthill-McKee ordering. 

93 

94 Examples 

95 -------- 

96 >>> from networkx.utils import reverse_cuthill_mckee_ordering 

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

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

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

100 

101 Smallest degree node as heuristic function: 

102 

103 >>> def smallest_degree(G): 

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

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

106 

107 

108 See Also 

109 -------- 

110 cuthill_mckee_ordering 

111 

112 Notes 

113 ----- 

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

115 

116 References 

117 ---------- 

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

119 Reducing the bandwidth of sparse symmetric matrices, 

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

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

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

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

124 """ 

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

126 

127 

128def connected_cuthill_mckee_ordering(G, heuristic=None): 

129 # the cuthill mckee algorithm for connected graphs 

130 if heuristic is None: 

131 start = pseudo_peripheral_node(G) 

132 else: 

133 start = heuristic(G) 

134 visited = {start} 

135 queue = deque([start]) 

136 while queue: 

137 parent = queue.popleft() 

138 yield parent 

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

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

141 visited.update(children) 

142 queue.extend(children) 

143 

144 

145def pseudo_peripheral_node(G): 

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

147 # to use as good starting node 

148 u = arbitrary_element(G) 

149 lp = 0 

150 v = u 

151 while True: 

152 spl = nx.shortest_path_length(G, v) 

153 l = max(spl.values()) 

154 if l <= lp: 

155 break 

156 lp = l 

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

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

159 return v