Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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.
8"""
10__all__ = ["nonisomorphic_trees", "number_of_nonisomorphic_trees"]
12from functools import lru_cache
14import networkx as nx
17@nx._dispatchable(graphs=None, returns_graph=True)
18def nonisomorphic_trees(order):
19 """Generate nonisomorphic trees of specified `order`.
21 Parameters
22 ----------
23 order : int
24 order of the desired tree(s)
26 Yields
27 ------
28 `networkx.Graph` instances
29 A tree with `order` number of nodes that is not isomorphic to any other
30 yielded tree.
32 Raises
33 ------
34 ValueError
35 If `order` is negative.
37 Examples
38 --------
39 There are 11 unique (non-isomorphic) trees with 7 nodes.
41 >>> n = 7
42 >>> nit_list = list(nx.nonisomorphic_trees(n))
43 >>> len(nit_list) == nx.number_of_nonisomorphic_trees(n) == 11
44 True
46 All trees yielded by the generator have the specified order.
48 >>> all(len(G) == n for G in nx.nonisomorphic_trees(n))
49 True
51 Each tree is nonisomorphic to every other tree yielded by the generator.
52 >>> seen = []
53 >>> for G in nx.nonisomorphic_trees(n):
54 ... assert not any(nx.is_isomorphic(G, H) for H in seen)
55 ... seen.append(G)
57 See Also
58 --------
59 number_of_nonisomorphic_trees
60 """
61 if order < 0:
62 raise ValueError("order must be non-negative")
63 if order == 0:
64 # Idiom for empty generator, i.e. list(nonisomorphic_trees(0)) == []
65 return
66 yield
67 if order == 1:
68 yield nx.empty_graph(1)
69 return
70 # start at the path graph rooted at its center
71 layout = list(range(order // 2 + 1)) + list(range(1, (order + 1) // 2))
73 while layout is not None:
74 layout = _next_tree(layout)
75 if layout is not None:
76 yield _layout_to_graph(layout)
77 layout = _next_rooted_tree(layout)
80@nx._dispatchable(graphs=None)
81def number_of_nonisomorphic_trees(order):
82 """Returns the number of nonisomorphic trees of the specified `order`.
84 Based on an algorithm by Alois P. Heinz in
85 `OEIS entry A000055 <https://oeis.org/A000055>`_. Complexity is ``O(n ** 3)``.
87 Parameters
88 ----------
89 order : int
90 Order of the desired tree(s).
92 Returns
93 -------
94 int
95 Number of nonisomorphic trees with `order` number of nodes.
97 Raises
98 ------
99 ValueError
100 If `order` is negative.
102 Examples
103 --------
104 >>> nx.number_of_nonisomorphic_trees(10)
105 106
107 See Also
108 --------
109 nonisomorphic_trees
110 """
111 if order < 0:
112 raise ValueError("order must be non-negative")
113 return _unlabeled_trees(order)
116@lru_cache(None)
117def _unlabeled_trees(n):
118 """Implements OEIS A000055 (number of unlabeled trees)."""
120 value = 0
121 for k in range(n + 1):
122 value += _rooted_trees(k) * _rooted_trees(n - k)
123 if n % 2 == 0:
124 value -= _rooted_trees(n // 2)
125 return _rooted_trees(n) - value // 2
128@lru_cache(None)
129def _rooted_trees(n):
130 """Implements OEIS A000081 (number of unlabeled rooted trees)."""
132 if n < 2:
133 return n
134 value = 0
135 for j in range(1, n):
136 for d in range(1, n):
137 if j % d == 0:
138 value += d * _rooted_trees(d) * _rooted_trees(n - j)
139 return value // (n - 1)
142def _next_rooted_tree(predecessor, p=None):
143 """One iteration of the Beyer-Hedetniemi algorithm."""
145 if p is None:
146 p = len(predecessor) - 1
147 while predecessor[p] == 1:
148 p -= 1
149 if p == 0:
150 return None
152 q = p - 1
153 while predecessor[q] != predecessor[p] - 1:
154 q -= 1
155 result = list(predecessor)
156 for i in range(p, len(result)):
157 result[i] = result[i - p + q]
158 return result
161def _next_tree(candidate):
162 """One iteration of the Wright, Richmond, Odlyzko and McKay
163 algorithm."""
165 # valid representation of a free tree if:
166 # there are at least two vertices at layer 1
167 # (this is always the case because we start at the path graph)
168 left, rest = _split_tree(candidate)
170 # and the left subtree of the root
171 # is less high than the tree with the left subtree removed
172 left_height = max(left)
173 rest_height = max(rest)
174 valid = rest_height >= left_height
176 if valid and rest_height == left_height:
177 # and, if left and rest are of the same height,
178 # if left does not encompass more vertices
179 if len(left) > len(rest):
180 valid = False
181 # and, if they have the same number or vertices,
182 # if left does not come after rest lexicographically
183 elif len(left) == len(rest) and left > rest:
184 valid = False
186 if valid:
187 return candidate
188 else:
189 # jump to the next valid free tree
190 p = len(left)
191 new_candidate = _next_rooted_tree(candidate, p)
192 if candidate[p] > 2:
193 new_left, new_rest = _split_tree(new_candidate)
194 new_left_height = max(new_left)
195 suffix = range(1, new_left_height + 2)
196 new_candidate[-len(suffix) :] = suffix
197 return new_candidate
200def _split_tree(layout):
201 """Returns a tuple of two layouts, one containing the left
202 subtree of the root vertex, and one containing the original tree
203 with the left subtree removed."""
205 one_found = False
206 m = None
207 for i in range(len(layout)):
208 if layout[i] == 1:
209 if one_found:
210 m = i
211 break
212 else:
213 one_found = True
215 if m is None:
216 m = len(layout)
218 left = [layout[i] - 1 for i in range(1, m)]
219 rest = [0] + [layout[i] for i in range(m, len(layout))]
220 return (left, rest)
223def _layout_to_matrix(layout):
224 """Create the adjacency matrix for the tree specified by the
225 given layout (level sequence)."""
227 result = [[0] * len(layout) for i in range(len(layout))]
228 stack = []
229 for i in range(len(layout)):
230 i_level = layout[i]
231 if stack:
232 j = stack[-1]
233 j_level = layout[j]
234 while j_level >= i_level:
235 stack.pop()
236 j = stack[-1]
237 j_level = layout[j]
238 result[i][j] = result[j][i] = 1
239 stack.append(i)
240 return result
243def _layout_to_graph(layout):
244 """Create a NetworkX Graph for the tree specified by the
245 given layout(level sequence)"""
246 G = nx.Graph()
247 stack = []
248 for i in range(len(layout)):
249 i_level = layout[i]
250 if stack:
251 j = stack[-1]
252 j_level = layout[j]
253 while j_level >= i_level:
254 stack.pop()
255 j = stack[-1]
256 j_level = layout[j]
257 G.add_edge(i, j)
258 stack.append(i)
259 return G