Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/tree/operations.py: 26%
27 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Operations on trees."""
2from functools import partial
3from itertools import accumulate, chain
5import networkx as nx
7__all__ = ["join", "join_trees"]
10def join(rooted_trees, label_attribute=None):
11 """A deprecated name for `join_trees`
13 Returns a new rooted tree with a root node joined with the roots
14 of each of the given rooted trees.
16 .. deprecated:: 3.2
18 `join` is deprecated in NetworkX v3.2 and will be removed in v3.4.
19 It has been renamed join_trees with the same syntax/interface.
21 """
22 import warnings
24 warnings.warn(
25 "The function `join` is deprecated and is renamed `join_trees`.\n"
26 "The ``join`` function itself will be removed in v3.4",
27 DeprecationWarning,
28 stacklevel=2,
29 )
31 return join_trees(rooted_trees, label_attribute=label_attribute)
34# Argument types don't match dispatching, but allow manual selection of backend
35@nx._dispatch(graphs=None)
36def join_trees(rooted_trees, *, label_attribute=None, first_label=0):
37 """Returns a new rooted tree made by joining `rooted_trees`
39 Constructs a new tree by joining each tree in `rooted_trees`.
40 A new root node is added and connected to each of the roots
41 of the input trees. While copying the nodes from the trees,
42 relabeling to integers occurs. If the `label_attribute` is provided,
43 the old node labels will be stored in the new tree under this attribute.
45 Parameters
46 ----------
47 rooted_trees : list
48 A list of pairs in which each left element is a NetworkX graph
49 object representing a tree and each right element is the root
50 node of that tree. The nodes of these trees will be relabeled to
51 integers.
53 label_attribute : str
54 If provided, the old node labels will be stored in the new tree
55 under this node attribute. If not provided, the original labels
56 of the nodes in the input trees are not stored.
58 first_label : int, optional (default=0)
59 Specifies the label for the new root node. If provided, the root node of the joined tree
60 will have this label. If not provided, the root node will default to a label of 0.
62 Returns
63 -------
64 NetworkX graph
65 The rooted tree resulting from joining the provided `rooted_trees`. The new tree has a root node
66 labeled as specified by `first_label` (defaulting to 0 if not provided). Subtrees from the input
67 `rooted_trees` are attached to this new root node. Each non-root node, if the `label_attribute`
68 is provided, has an attribute that indicates the original label of the node in the input tree.
70 Notes
71 -----
72 Trees are stored in NetworkX as NetworkX Graphs. There is no specific
73 enforcement of the fact that these are trees. Testing for each tree
74 can be done using :func:`networkx.is_tree`.
76 Graph, edge, and node attributes are propagated from the given
77 rooted trees to the created tree. If there are any overlapping graph
78 attributes, those from later trees will overwrite those from earlier
79 trees in the tuple of positional arguments.
81 Examples
82 --------
83 Join two full balanced binary trees of height *h* to get a full
84 balanced binary tree of depth *h* + 1::
86 >>> h = 4
87 >>> left = nx.balanced_tree(2, h)
88 >>> right = nx.balanced_tree(2, h)
89 >>> joined_tree = nx.join([(left, 0), (right, 0)])
90 >>> nx.is_isomorphic(joined_tree, nx.balanced_tree(2, h + 1))
91 True
93 """
94 if not rooted_trees:
95 return nx.empty_graph(1)
97 # Unzip the zipped list of (tree, root) pairs.
98 trees, roots = zip(*rooted_trees)
100 # The join of the trees has the same type as the type of the first tree.
101 R = type(trees[0])()
103 lengths = (len(tree) for tree in trees[:-1])
104 first_labels = list(accumulate(lengths, initial=first_label + 1))
106 new_roots = []
107 for tree, root, first_node in zip(trees, roots, first_labels):
108 new_root = first_node + list(tree.nodes()).index(root)
109 new_roots.append(new_root)
111 # Relabel the nodes so that their union is the integers starting at first_label.
112 relabel = partial(
113 nx.convert_node_labels_to_integers, label_attribute=label_attribute
114 )
115 new_trees = [
116 relabel(tree, first_label=first_label)
117 for tree, first_label in zip(trees, first_labels)
118 ]
120 # Add all sets of nodes and edges, attributes
121 for tree in new_trees:
122 R.update(tree)
124 # Finally, join the subtrees at the root. We know first_label is unused by the way we relabeled the subtrees.
125 R.add_node(first_label)
126 R.add_edges_from((first_label, root) for root in new_roots)
128 return R