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"""Functions for encoding and decoding trees.
3Since a tree is a highly restricted form of graph, it can be represented
4concisely in several ways. This module includes functions for encoding
5and decoding trees in the form of nested tuples and Prüfer
6sequences. The former requires a rooted tree, whereas the latter can be
7applied to unrooted trees. Furthermore, there is a bijection from Prüfer
8sequences to labeled trees.
10"""
12from collections import Counter
13from itertools import chain
15import networkx as nx
16from networkx.utils import not_implemented_for
18__all__ = [
19 "from_nested_tuple",
20 "from_prufer_sequence",
21 "NotATree",
22 "to_nested_tuple",
23 "to_prufer_sequence",
24]
27class NotATree(nx.NetworkXException):
28 """Raised when a function expects a tree (that is, a connected
29 undirected graph with no cycles) but gets a non-tree graph as input
30 instead.
32 """
35@not_implemented_for("directed")
36@nx._dispatchable(graphs="T")
37def to_nested_tuple(T, root, canonical_form=False):
38 """Returns a nested tuple representation of the given tree.
40 The nested tuple representation of a tree is defined
41 recursively. The tree with one node and no edges is represented by
42 the empty tuple, ``()``. A tree with ``k`` subtrees is represented
43 by a tuple of length ``k`` in which each element is the nested tuple
44 representation of a subtree.
46 Parameters
47 ----------
48 T : NetworkX graph
49 An undirected graph object representing a tree.
51 root : node
52 The node in ``T`` to interpret as the root of the tree.
54 canonical_form : bool
55 If ``True``, each tuple is sorted so that the function returns
56 a canonical form for rooted trees. This means "lighter" subtrees
57 will appear as nested tuples before "heavier" subtrees. In this
58 way, each isomorphic rooted tree has the same nested tuple
59 representation.
61 Returns
62 -------
63 tuple
64 A nested tuple representation of the tree.
66 Notes
67 -----
68 This function is *not* the inverse of :func:`from_nested_tuple`; the
69 only guarantee is that the rooted trees are isomorphic.
71 See also
72 --------
73 from_nested_tuple
74 to_prufer_sequence
76 Examples
77 --------
78 The tree need not be a balanced binary tree::
80 >>> T = nx.Graph()
81 >>> T.add_edges_from([(0, 1), (0, 2), (0, 3)])
82 >>> T.add_edges_from([(1, 4), (1, 5)])
83 >>> T.add_edges_from([(3, 6), (3, 7)])
84 >>> root = 0
85 >>> nx.to_nested_tuple(T, root)
86 (((), ()), (), ((), ()))
88 Continuing the above example, if ``canonical_form`` is ``True``, the
89 nested tuples will be sorted::
91 >>> nx.to_nested_tuple(T, root, canonical_form=True)
92 ((), ((), ()), ((), ()))
94 Even the path graph can be interpreted as a tree::
96 >>> T = nx.path_graph(4)
97 >>> root = 0
98 >>> nx.to_nested_tuple(T, root)
99 ((((),),),)
101 """
103 def _make_tuple(T, root, _parent):
104 """Recursively compute the nested tuple representation of the
105 given rooted tree.
107 ``_parent`` is the parent node of ``root`` in the supertree in
108 which ``T`` is a subtree, or ``None`` if ``root`` is the root of
109 the supertree. This argument is used to determine which
110 neighbors of ``root`` are children and which is the parent.
112 """
113 # Get the neighbors of `root` that are not the parent node. We
114 # are guaranteed that `root` is always in `T` by construction.
115 children = set(T[root]) - {_parent}
116 if len(children) == 0:
117 return ()
118 nested = (_make_tuple(T, v, root) for v in children)
119 if canonical_form:
120 nested = sorted(nested)
121 return tuple(nested)
123 # Do some sanity checks on the input.
124 if not nx.is_tree(T):
125 raise nx.NotATree("provided graph is not a tree")
126 if root not in T:
127 raise nx.NodeNotFound(f"Graph {T} contains no node {root}")
129 return _make_tuple(T, root, None)
132@nx._dispatchable(graphs=None, returns_graph=True)
133def from_nested_tuple(sequence, sensible_relabeling=False):
134 """Returns the rooted tree corresponding to the given nested tuple.
136 The nested tuple representation of a tree is defined
137 recursively. The tree with one node and no edges is represented by
138 the empty tuple, ``()``. A tree with ``k`` subtrees is represented
139 by a tuple of length ``k`` in which each element is the nested tuple
140 representation of a subtree.
142 Parameters
143 ----------
144 sequence : tuple
145 A nested tuple representing a rooted tree.
147 sensible_relabeling : bool
148 Whether to relabel the nodes of the tree so that nodes are
149 labeled in increasing order according to their breadth-first
150 search order from the root node.
152 Returns
153 -------
154 NetworkX graph
155 The tree corresponding to the given nested tuple, whose root
156 node is node 0. If ``sensible_labeling`` is ``True``, nodes will
157 be labeled in breadth-first search order starting from the root
158 node.
160 Notes
161 -----
162 This function is *not* the inverse of :func:`to_nested_tuple`; the
163 only guarantee is that the rooted trees are isomorphic.
165 See also
166 --------
167 to_nested_tuple
168 from_prufer_sequence
170 Examples
171 --------
172 Sensible relabeling ensures that the nodes are labeled from the root
173 starting at 0::
175 >>> balanced = (((), ()), ((), ()))
176 >>> T = nx.from_nested_tuple(balanced, sensible_relabeling=True)
177 >>> edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
178 >>> all((u, v) in T.edges() or (v, u) in T.edges() for (u, v) in edges)
179 True
181 """
183 def _make_tree(sequence):
184 """Recursively creates a tree from the given sequence of nested
185 tuples.
187 This function employs the :func:`~networkx.tree.join` function
188 to recursively join subtrees into a larger tree.
190 """
191 # The empty sequence represents the empty tree, which is the
192 # (unique) graph with a single node. We mark the single node
193 # with an attribute that indicates that it is the root of the
194 # graph.
195 if len(sequence) == 0:
196 return nx.empty_graph(1)
197 # For a nonempty sequence, get the subtrees for each child
198 # sequence and join all the subtrees at their roots. After
199 # joining the subtrees, the root is node 0.
200 return nx.tree.join_trees([(_make_tree(child), 0) for child in sequence])
202 # Make the tree and remove the `is_root` node attribute added by the
203 # helper function.
204 T = _make_tree(sequence)
205 if sensible_relabeling:
206 # Relabel the nodes according to their breadth-first search
207 # order, starting from the root node (that is, the node 0).
208 bfs_nodes = chain([0], (v for u, v in nx.bfs_edges(T, 0)))
209 labels = {v: i for i, v in enumerate(bfs_nodes)}
210 # We would like to use `copy=False`, but `relabel_nodes` doesn't
211 # allow a relabel mapping that can't be topologically sorted.
212 T = nx.relabel_nodes(T, labels)
213 return T
216@not_implemented_for("directed")
217@nx._dispatchable(graphs="T")
218def to_prufer_sequence(T):
219 r"""Returns the Prüfer sequence of the given tree.
221 A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
222 *n* - 1, inclusive. The tree corresponding to a given Prüfer
223 sequence can be recovered by repeatedly joining a node in the
224 sequence with a node with the smallest potential degree according to
225 the sequence.
227 Parameters
228 ----------
229 T : NetworkX graph
230 An undirected graph object representing a tree.
232 Returns
233 -------
234 list
235 The Prüfer sequence of the given tree.
237 Raises
238 ------
239 NetworkXPointlessConcept
240 If the number of nodes in `T` is less than two.
242 NotATree
243 If `T` is not a tree.
245 KeyError
246 If the set of nodes in `T` is not {0, …, *n* - 1}.
248 Notes
249 -----
250 There is a bijection from labeled trees to Prüfer sequences. This
251 function is the inverse of the :func:`from_prufer_sequence`
252 function.
254 Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
255 of from 0 to *n* - 1. This function requires nodes to be labeled in
256 the latter form. You can use :func:`~networkx.relabel_nodes` to
257 relabel the nodes of your tree to the appropriate format.
259 This implementation is from [1]_ and has a running time of
260 $O(n)$.
262 See also
263 --------
264 to_nested_tuple
265 from_prufer_sequence
267 References
268 ----------
269 .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
270 "An optimal algorithm for Prufer codes."
271 *Journal of Software Engineering and Applications* 2.02 (2009): 111.
272 <https://doi.org/10.4236/jsea.2009.22016>
274 Examples
275 --------
276 There is a bijection between Prüfer sequences and labeled trees, so
277 this function is the inverse of the :func:`from_prufer_sequence`
278 function:
280 >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
281 >>> tree = nx.Graph(edges)
282 >>> sequence = nx.to_prufer_sequence(tree)
283 >>> sequence
284 [3, 3, 3, 4]
285 >>> tree2 = nx.from_prufer_sequence(sequence)
286 >>> list(tree2.edges()) == edges
287 True
289 """
290 # Perform some sanity checks on the input.
291 n = len(T)
292 if n < 2:
293 msg = "Prüfer sequence undefined for trees with fewer than two nodes"
294 raise nx.NetworkXPointlessConcept(msg)
295 if not nx.is_tree(T):
296 raise nx.NotATree("provided graph is not a tree")
297 if set(T) != set(range(n)):
298 raise KeyError("tree must have node labels {0, ..., n - 1}")
300 degree = dict(T.degree())
302 def parents(u):
303 return next(v for v in T[u] if degree[v] > 1)
305 index = u = next(k for k in range(n) if degree[k] == 1)
306 result = []
307 for i in range(n - 2):
308 v = parents(u)
309 result.append(v)
310 degree[v] -= 1
311 if v < index and degree[v] == 1:
312 u = v
313 else:
314 index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
315 return result
318@nx._dispatchable(graphs=None, returns_graph=True)
319def from_prufer_sequence(sequence):
320 r"""Returns the tree corresponding to the given Prüfer sequence.
322 A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
323 *n* - 1, inclusive. The tree corresponding to a given Prüfer
324 sequence can be recovered by repeatedly joining a node in the
325 sequence with a node with the smallest potential degree according to
326 the sequence.
328 Parameters
329 ----------
330 sequence : list
331 A Prüfer sequence, which is a list of *n* - 2 integers between
332 zero and *n* - 1, inclusive.
334 Returns
335 -------
336 NetworkX graph
337 The tree corresponding to the given Prüfer sequence.
339 Raises
340 ------
341 NetworkXError
342 If the Prüfer sequence is not valid.
344 Notes
345 -----
346 There is a bijection from labeled trees to Prüfer sequences. This
347 function is the inverse of the :func:`from_prufer_sequence` function.
349 Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
350 of from 0 to *n* - 1. This function requires nodes to be labeled in
351 the latter form. You can use :func:`networkx.relabel_nodes` to
352 relabel the nodes of your tree to the appropriate format.
354 This implementation is from [1]_ and has a running time of
355 $O(n)$.
357 References
358 ----------
359 .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
360 "An optimal algorithm for Prufer codes."
361 *Journal of Software Engineering and Applications* 2.02 (2009): 111.
362 <https://doi.org/10.4236/jsea.2009.22016>
364 See also
365 --------
366 from_nested_tuple
367 to_prufer_sequence
369 Examples
370 --------
371 There is a bijection between Prüfer sequences and labeled trees, so
372 this function is the inverse of the :func:`to_prufer_sequence`
373 function:
375 >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
376 >>> tree = nx.Graph(edges)
377 >>> sequence = nx.to_prufer_sequence(tree)
378 >>> sequence
379 [3, 3, 3, 4]
380 >>> tree2 = nx.from_prufer_sequence(sequence)
381 >>> list(tree2.edges()) == edges
382 True
384 """
385 n = len(sequence) + 2
386 # `degree` stores the remaining degree (plus one) for each node. The
387 # degree of a node in the decoded tree is one more than the number
388 # of times it appears in the code.
389 degree = Counter(chain(sequence, range(n)))
390 T = nx.empty_graph(n)
391 # `not_orphaned` is the set of nodes that have a parent in the
392 # tree. After the loop, there should be exactly two nodes that are
393 # not in this set.
394 not_orphaned = set()
395 index = u = next(k for k in range(n) if degree[k] == 1)
396 for v in sequence:
397 # check the validity of the prufer sequence
398 if v < 0 or v > n - 1:
399 raise nx.NetworkXError(
400 f"Invalid Prufer sequence: Values must be between 0 and {n - 1}, got {v}"
401 )
402 T.add_edge(u, v)
403 not_orphaned.add(u)
404 degree[v] -= 1
405 if v < index and degree[v] == 1:
406 u = v
407 else:
408 index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
409 # At this point, there must be exactly two orphaned nodes; join them.
410 orphans = set(T) - not_orphaned
411 u, v = orphans
412 T.add_edge(u, v)
413 return T