Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/tree/coding.py: 21%
78 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
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"""
11from collections import Counter
12from itertools import chain
14import networkx as nx
15from networkx.utils import not_implemented_for
17__all__ = [
18 "from_nested_tuple",
19 "from_prufer_sequence",
20 "NotATree",
21 "to_nested_tuple",
22 "to_prufer_sequence",
23]
26class NotATree(nx.NetworkXException):
27 """Raised when a function expects a tree (that is, a connected
28 undirected graph with no cycles) but gets a non-tree graph as input
29 instead.
31 """
34@not_implemented_for("directed")
35@nx._dispatch(graphs="T")
36def to_nested_tuple(T, root, canonical_form=False):
37 """Returns a nested tuple representation of the given tree.
39 The nested tuple representation of a tree is defined
40 recursively. The tree with one node and no edges is represented by
41 the empty tuple, ``()``. A tree with ``k`` subtrees is represented
42 by a tuple of length ``k`` in which each element is the nested tuple
43 representation of a subtree.
45 Parameters
46 ----------
47 T : NetworkX graph
48 An undirected graph object representing a tree.
50 root : node
51 The node in ``T`` to interpret as the root of the tree.
53 canonical_form : bool
54 If ``True``, each tuple is sorted so that the function returns
55 a canonical form for rooted trees. This means "lighter" subtrees
56 will appear as nested tuples before "heavier" subtrees. In this
57 way, each isomorphic rooted tree has the same nested tuple
58 representation.
60 Returns
61 -------
62 tuple
63 A nested tuple representation of the tree.
65 Notes
66 -----
67 This function is *not* the inverse of :func:`from_nested_tuple`; the
68 only guarantee is that the rooted trees are isomorphic.
70 See also
71 --------
72 from_nested_tuple
73 to_prufer_sequence
75 Examples
76 --------
77 The tree need not be a balanced binary tree::
79 >>> T = nx.Graph()
80 >>> T.add_edges_from([(0, 1), (0, 2), (0, 3)])
81 >>> T.add_edges_from([(1, 4), (1, 5)])
82 >>> T.add_edges_from([(3, 6), (3, 7)])
83 >>> root = 0
84 >>> nx.to_nested_tuple(T, root)
85 (((), ()), (), ((), ()))
87 Continuing the above example, if ``canonical_form`` is ``True``, the
88 nested tuples will be sorted::
90 >>> nx.to_nested_tuple(T, root, canonical_form=True)
91 ((), ((), ()), ((), ()))
93 Even the path graph can be interpreted as a tree::
95 >>> T = nx.path_graph(4)
96 >>> root = 0
97 >>> nx.to_nested_tuple(T, root)
98 ((((),),),)
100 """
102 def _make_tuple(T, root, _parent):
103 """Recursively compute the nested tuple representation of the
104 given rooted tree.
106 ``_parent`` is the parent node of ``root`` in the supertree in
107 which ``T`` is a subtree, or ``None`` if ``root`` is the root of
108 the supertree. This argument is used to determine which
109 neighbors of ``root`` are children and which is the parent.
111 """
112 # Get the neighbors of `root` that are not the parent node. We
113 # are guaranteed that `root` is always in `T` by construction.
114 children = set(T[root]) - {_parent}
115 if len(children) == 0:
116 return ()
117 nested = (_make_tuple(T, v, root) for v in children)
118 if canonical_form:
119 nested = sorted(nested)
120 return tuple(nested)
122 # Do some sanity checks on the input.
123 if not nx.is_tree(T):
124 raise nx.NotATree("provided graph is not a tree")
125 if root not in T:
126 raise nx.NodeNotFound(f"Graph {T} contains no node {root}")
128 return _make_tuple(T, root, None)
131@nx._dispatch(graphs=None)
132def from_nested_tuple(sequence, sensible_relabeling=False):
133 """Returns the rooted tree corresponding to the given nested tuple.
135 The nested tuple representation of a tree is defined
136 recursively. The tree with one node and no edges is represented by
137 the empty tuple, ``()``. A tree with ``k`` subtrees is represented
138 by a tuple of length ``k`` in which each element is the nested tuple
139 representation of a subtree.
141 Parameters
142 ----------
143 sequence : tuple
144 A nested tuple representing a rooted tree.
146 sensible_relabeling : bool
147 Whether to relabel the nodes of the tree so that nodes are
148 labeled in increasing order according to their breadth-first
149 search order from the root node.
151 Returns
152 -------
153 NetworkX graph
154 The tree corresponding to the given nested tuple, whose root
155 node is node 0. If ``sensible_labeling`` is ``True``, nodes will
156 be labeled in breadth-first search order starting from the root
157 node.
159 Notes
160 -----
161 This function is *not* the inverse of :func:`to_nested_tuple`; the
162 only guarantee is that the rooted trees are isomorphic.
164 See also
165 --------
166 to_nested_tuple
167 from_prufer_sequence
169 Examples
170 --------
171 Sensible relabeling ensures that the nodes are labeled from the root
172 starting at 0::
174 >>> balanced = (((), ()), ((), ()))
175 >>> T = nx.from_nested_tuple(balanced, sensible_relabeling=True)
176 >>> edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
177 >>> all((u, v) in T.edges() or (v, u) in T.edges() for (u, v) in edges)
178 True
180 """
182 def _make_tree(sequence):
183 """Recursively creates a tree from the given sequence of nested
184 tuples.
186 This function employs the :func:`~networkx.tree.join` function
187 to recursively join subtrees into a larger tree.
189 """
190 # The empty sequence represents the empty tree, which is the
191 # (unique) graph with a single node. We mark the single node
192 # with an attribute that indicates that it is the root of the
193 # graph.
194 if len(sequence) == 0:
195 return nx.empty_graph(1)
196 # For a nonempty sequence, get the subtrees for each child
197 # sequence and join all the subtrees at their roots. After
198 # joining the subtrees, the root is node 0.
199 return nx.tree.join_trees([(_make_tree(child), 0) for child in sequence])
201 # Make the tree and remove the `is_root` node attribute added by the
202 # helper function.
203 T = _make_tree(sequence)
204 if sensible_relabeling:
205 # Relabel the nodes according to their breadth-first search
206 # order, starting from the root node (that is, the node 0).
207 bfs_nodes = chain([0], (v for u, v in nx.bfs_edges(T, 0)))
208 labels = {v: i for i, v in enumerate(bfs_nodes)}
209 # We would like to use `copy=False`, but `relabel_nodes` doesn't
210 # allow a relabel mapping that can't be topologically sorted.
211 T = nx.relabel_nodes(T, labels)
212 return T
215@not_implemented_for("directed")
216@nx._dispatch(graphs="T")
217def to_prufer_sequence(T):
218 r"""Returns the Prüfer sequence of the given tree.
220 A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
221 *n* - 1, inclusive. The tree corresponding to a given Prüfer
222 sequence can be recovered by repeatedly joining a node in the
223 sequence with a node with the smallest potential degree according to
224 the sequence.
226 Parameters
227 ----------
228 T : NetworkX graph
229 An undirected graph object representing a tree.
231 Returns
232 -------
233 list
234 The Prüfer sequence of the given tree.
236 Raises
237 ------
238 NetworkXPointlessConcept
239 If the number of nodes in `T` is less than two.
241 NotATree
242 If `T` is not a tree.
244 KeyError
245 If the set of nodes in `T` is not {0, …, *n* - 1}.
247 Notes
248 -----
249 There is a bijection from labeled trees to Prüfer sequences. This
250 function is the inverse of the :func:`from_prufer_sequence`
251 function.
253 Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
254 of from 0 to *n* - 1. This function requires nodes to be labeled in
255 the latter form. You can use :func:`~networkx.relabel_nodes` to
256 relabel the nodes of your tree to the appropriate format.
258 This implementation is from [1]_ and has a running time of
259 $O(n)$.
261 See also
262 --------
263 to_nested_tuple
264 from_prufer_sequence
266 References
267 ----------
268 .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
269 "An optimal algorithm for Prufer codes."
270 *Journal of Software Engineering and Applications* 2.02 (2009): 111.
271 <https://doi.org/10.4236/jsea.2009.22016>
273 Examples
274 --------
275 There is a bijection between Prüfer sequences and labeled trees, so
276 this function is the inverse of the :func:`from_prufer_sequence`
277 function:
279 >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
280 >>> tree = nx.Graph(edges)
281 >>> sequence = nx.to_prufer_sequence(tree)
282 >>> sequence
283 [3, 3, 3, 4]
284 >>> tree2 = nx.from_prufer_sequence(sequence)
285 >>> list(tree2.edges()) == edges
286 True
288 """
289 # Perform some sanity checks on the input.
290 n = len(T)
291 if n < 2:
292 msg = "Prüfer sequence undefined for trees with fewer than two nodes"
293 raise nx.NetworkXPointlessConcept(msg)
294 if not nx.is_tree(T):
295 raise nx.NotATree("provided graph is not a tree")
296 if set(T) != set(range(n)):
297 raise KeyError("tree must have node labels {0, ..., n - 1}")
299 degree = dict(T.degree())
301 def parents(u):
302 return next(v for v in T[u] if degree[v] > 1)
304 index = u = next(k for k in range(n) if degree[k] == 1)
305 result = []
306 for i in range(n - 2):
307 v = parents(u)
308 result.append(v)
309 degree[v] -= 1
310 if v < index and degree[v] == 1:
311 u = v
312 else:
313 index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
314 return result
317@nx._dispatch(graphs=None)
318def from_prufer_sequence(sequence):
319 r"""Returns the tree corresponding to the given Prüfer sequence.
321 A *Prüfer sequence* is a list of *n* - 2 numbers between 0 and
322 *n* - 1, inclusive. The tree corresponding to a given Prüfer
323 sequence can be recovered by repeatedly joining a node in the
324 sequence with a node with the smallest potential degree according to
325 the sequence.
327 Parameters
328 ----------
329 sequence : list
330 A Prüfer sequence, which is a list of *n* - 2 integers between
331 zero and *n* - 1, inclusive.
333 Returns
334 -------
335 NetworkX graph
336 The tree corresponding to the given Prüfer sequence.
338 Raises
339 ------
340 NetworkXError
341 If the Prüfer sequence is not valid.
343 Notes
344 -----
345 There is a bijection from labeled trees to Prüfer sequences. This
346 function is the inverse of the :func:`from_prufer_sequence` function.
348 Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead
349 of from 0 to *n* - 1. This function requires nodes to be labeled in
350 the latter form. You can use :func:`networkx.relabel_nodes` to
351 relabel the nodes of your tree to the appropriate format.
353 This implementation is from [1]_ and has a running time of
354 $O(n)$.
356 References
357 ----------
358 .. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.
359 "An optimal algorithm for Prufer codes."
360 *Journal of Software Engineering and Applications* 2.02 (2009): 111.
361 <https://doi.org/10.4236/jsea.2009.22016>
363 See also
364 --------
365 from_nested_tuple
366 to_prufer_sequence
368 Examples
369 --------
370 There is a bijection between Prüfer sequences and labeled trees, so
371 this function is the inverse of the :func:`to_prufer_sequence`
372 function:
374 >>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]
375 >>> tree = nx.Graph(edges)
376 >>> sequence = nx.to_prufer_sequence(tree)
377 >>> sequence
378 [3, 3, 3, 4]
379 >>> tree2 = nx.from_prufer_sequence(sequence)
380 >>> list(tree2.edges()) == edges
381 True
383 """
384 n = len(sequence) + 2
385 # `degree` stores the remaining degree (plus one) for each node. The
386 # degree of a node in the decoded tree is one more than the number
387 # of times it appears in the code.
388 degree = Counter(chain(sequence, range(n)))
389 T = nx.empty_graph(n)
390 # `not_orphaned` is the set of nodes that have a parent in the
391 # tree. After the loop, there should be exactly two nodes that are
392 # not in this set.
393 not_orphaned = set()
394 index = u = next(k for k in range(n) if degree[k] == 1)
395 for v in sequence:
396 # check the validity of the prufer sequence
397 if v < 0 or v > n - 1:
398 raise nx.NetworkXError(
399 f"Invalid Prufer sequence: Values must be between 0 and {n-1}, got {v}"
400 )
401 T.add_edge(u, v)
402 not_orphaned.add(u)
403 degree[v] -= 1
404 if v < index and degree[v] == 1:
405 u = v
406 else:
407 index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
408 # At this point, there must be exactly two orphaned nodes; join them.
409 orphans = set(T) - not_orphaned
410 u, v = orphans
411 T.add_edge(u, v)
412 return T