Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tree/operations.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Operations on trees.""" | |
2 from functools import partial | |
3 from itertools import chain | |
4 | |
5 import networkx as nx | |
6 from itertools import accumulate | |
7 | |
8 __all__ = ["join"] | |
9 | |
10 | |
11 def join(rooted_trees, label_attribute=None): | |
12 """Returns a new rooted tree with a root node joined with the roots | |
13 of each of the given rooted trees. | |
14 | |
15 Parameters | |
16 ---------- | |
17 rooted_trees : list | |
18 A list of pairs in which each left element is a NetworkX graph | |
19 object representing a tree and each right element is the root | |
20 node of that tree. The nodes of these trees will be relabeled to | |
21 integers. | |
22 | |
23 label_attribute : str | |
24 If provided, the old node labels will be stored in the new tree | |
25 under this node attribute. If not provided, the node attribute | |
26 ``'_old'`` will store the original label of the node in the | |
27 rooted trees given in the input. | |
28 | |
29 Returns | |
30 ------- | |
31 NetworkX graph | |
32 The rooted tree whose subtrees are the given rooted trees. The | |
33 new root node is labeled 0. Each non-root node has an attribute, | |
34 as described under the keyword argument ``label_attribute``, | |
35 that indicates the label of the original node in the input tree. | |
36 | |
37 Notes | |
38 ----- | |
39 Graph, edge, and node attributes are propagated from the given | |
40 rooted trees to the created tree. If there are any overlapping graph | |
41 attributes, those from later trees will overwrite those from earlier | |
42 trees in the tuple of positional arguments. | |
43 | |
44 Examples | |
45 -------- | |
46 Join two full balanced binary trees of height *h* to get a full | |
47 balanced binary tree of depth *h* + 1:: | |
48 | |
49 >>> h = 4 | |
50 >>> left = nx.balanced_tree(2, h) | |
51 >>> right = nx.balanced_tree(2, h) | |
52 >>> joined_tree = nx.join([(left, 0), (right, 0)]) | |
53 >>> nx.is_isomorphic(joined_tree, nx.balanced_tree(2, h + 1)) | |
54 True | |
55 | |
56 """ | |
57 if len(rooted_trees) == 0: | |
58 return nx.empty_graph(1) | |
59 | |
60 # Unzip the zipped list of (tree, root) pairs. | |
61 trees, roots = zip(*rooted_trees) | |
62 | |
63 # The join of the trees has the same type as the type of the first | |
64 # tree. | |
65 R = type(trees[0])() | |
66 | |
67 # Relabel the nodes so that their union is the integers starting at 1. | |
68 if label_attribute is None: | |
69 label_attribute = "_old" | |
70 relabel = partial( | |
71 nx.convert_node_labels_to_integers, label_attribute=label_attribute | |
72 ) | |
73 lengths = (len(tree) for tree in trees[:-1]) | |
74 first_labels = chain([0], accumulate(lengths)) | |
75 trees = [ | |
76 relabel(tree, first_label=first_label + 1) | |
77 for tree, first_label in zip(trees, first_labels) | |
78 ] | |
79 | |
80 # Get the relabeled roots. | |
81 roots = [ | |
82 next(v for v, d in tree.nodes(data=True) if d.get("_old") == root) | |
83 for tree, root in zip(trees, roots) | |
84 ] | |
85 | |
86 # Remove the old node labels. | |
87 for tree in trees: | |
88 for v in tree: | |
89 tree.nodes[v].pop("_old") | |
90 | |
91 # Add all sets of nodes and edges, with data. | |
92 nodes = (tree.nodes(data=True) for tree in trees) | |
93 edges = (tree.edges(data=True) for tree in trees) | |
94 R.add_nodes_from(chain.from_iterable(nodes)) | |
95 R.add_edges_from(chain.from_iterable(edges)) | |
96 | |
97 # Add graph attributes; later attributes take precedent over earlier | |
98 # attributes. | |
99 for tree in trees: | |
100 R.graph.update(tree.graph) | |
101 | |
102 # Finally, join the subtrees at the root. We know 0 is unused by the | |
103 # way we relabeled the subtrees. | |
104 R.add_node(0) | |
105 R.add_edges_from((0, root) for root in roots) | |
106 | |
107 return R |