Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/nonisomorphic_trees.py: 11%

1""" 

2Implementation of the Wright, Richmond, Odlyzko and McKay (WROM) 

3algorithm for the enumeration of all non-isomorphic free trees of a 

4given order. Rooted trees are represented by level sequences, i.e., 

5lists in which the i-th element specifies the distance of vertex i to 

6the root. 

7 

8""" 

9 

10__all__ = ["nonisomorphic_trees", "number_of_nonisomorphic_trees"] 

11 

12import networkx as nx 

13 

14 

15@nx._dispatch(graphs=None) 

16def nonisomorphic_trees(order, create="graph"): 

17 """Returns a list of nonisomorphic trees 

18 

19 Parameters 

20 ---------- 

21 order : int 

22 order of the desired tree(s) 

23 

24 create : graph or matrix (default="Graph) 

25 If graph is selected a list of trees will be returned, 

26 if matrix is selected a list of adjacency matrix will 

27 be returned 

28 

29 Returns 

30 ------- 

31 G : List of NetworkX Graphs 

32 

33 M : List of Adjacency matrices 

34 

35 References 

36 ---------- 

37 

38 """ 

39 

40 if order < 2: 

41 raise ValueError 

42 # start at the path graph rooted at its center 

43 layout = list(range(order // 2 + 1)) + list(range(1, (order + 1) // 2)) 

44 

45 while layout is not None: 

46 layout = _next_tree(layout) 

47 if layout is not None: 

48 if create == "graph": 

49 yield _layout_to_graph(layout) 

50 elif create == "matrix": 

51 yield _layout_to_matrix(layout) 

52 layout = _next_rooted_tree(layout) 

53 

54 

55@nx._dispatch(graphs=None) 

56def number_of_nonisomorphic_trees(order): 

57 """Returns the number of nonisomorphic trees 

58 

59 Parameters 

60 ---------- 

61 order : int 

62 order of the desired tree(s) 

63 

64 Returns 

65 ------- 

66 length : Number of nonisomorphic graphs for the given order 

67 

68 References 

69 ---------- 

70 

71 """ 

72 return sum(1 for _ in nonisomorphic_trees(order)) 

73 

74 

75def _next_rooted_tree(predecessor, p=None): 

76 """One iteration of the Beyer-Hedetniemi algorithm.""" 

77 

78 if p is None: 

79 p = len(predecessor) - 1 

80 while predecessor[p] == 1: 

81 p -= 1 

82 if p == 0: 

83 return None 

84 

85 q = p - 1 

86 while predecessor[q] != predecessor[p] - 1: 

87 q -= 1 

88 result = list(predecessor) 

89 for i in range(p, len(result)): 

90 result[i] = result[i - p + q] 

91 return result 

92 

93 

94def _next_tree(candidate): 

95 """One iteration of the Wright, Richmond, Odlyzko and McKay 

96 algorithm.""" 

97 

98 # valid representation of a free tree if: 

99 # there are at least two vertices at layer 1 

100 # (this is always the case because we start at the path graph) 

101 left, rest = _split_tree(candidate) 

102 

103 # and the left subtree of the root 

104 # is less high than the tree with the left subtree removed 

105 left_height = max(left) 

106 rest_height = max(rest) 

107 valid = rest_height >= left_height 

108 

109 if valid and rest_height == left_height: 

110 # and, if left and rest are of the same height, 

111 # if left does not encompass more vertices 

112 if len(left) > len(rest): 

113 valid = False 

114 # and, if they have the same number or vertices, 

115 # if left does not come after rest lexicographically 

116 elif len(left) == len(rest) and left > rest: 

117 valid = False 

118 

119 if valid: 

120 return candidate 

121 else: 

122 # jump to the next valid free tree 

123 p = len(left) 

124 new_candidate = _next_rooted_tree(candidate, p) 

125 if candidate[p] > 2: 

126 new_left, new_rest = _split_tree(new_candidate) 

127 new_left_height = max(new_left) 

128 suffix = range(1, new_left_height + 2) 

129 new_candidate[-len(suffix) :] = suffix 

130 return new_candidate 

131 

132 

133def _split_tree(layout): 

134 """Returns a tuple of two layouts, one containing the left 

135 subtree of the root vertex, and one containing the original tree 

136 with the left subtree removed.""" 

137 

138 one_found = False 

139 m = None 

140 for i in range(len(layout)): 

141 if layout[i] == 1: 

142 if one_found: 

143 m = i 

144 break 

145 else: 

146 one_found = True 

147 

148 if m is None: 

149 m = len(layout) 

150 

151 left = [layout[i] - 1 for i in range(1, m)] 

152 rest = [0] + [layout[i] for i in range(m, len(layout))] 

153 return (left, rest) 

154 

155 

156def _layout_to_matrix(layout): 

157 """Create the adjacency matrix for the tree specified by the 

158 given layout (level sequence).""" 

159 

160 result = [[0] * len(layout) for i in range(len(layout))] 

161 stack = [] 

162 for i in range(len(layout)): 

163 i_level = layout[i] 

164 if stack: 

165 j = stack[-1] 

166 j_level = layout[j] 

167 while j_level >= i_level: 

168 stack.pop() 

169 j = stack[-1] 

170 j_level = layout[j] 

171 result[i][j] = result[j][i] = 1 

172 stack.append(i) 

173 return result 

174 

175 

176def _layout_to_graph(layout): 

177 """Create a NetworkX Graph for the tree specified by the 

178 given layout(level sequence)""" 

179 G = nx.Graph() 

180 stack = [] 

181 for i in range(len(layout)): 

182 i_level = layout[i] 

183 if stack: 

184 j = stack[-1] 

185 j_level = layout[j] 

186 while j_level >= i_level: 

187 stack.pop() 

188 j = stack[-1] 

189 j_level = layout[j] 

190 G.add_edge(i, j) 

191 stack.append(i) 

192 return G