Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/trees.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- encoding: utf-8 -*-
2 # Copyright (C) 2015-2019 by
3 # Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>
4 # NetworkX developers
5 # All rights reserved.
6 # BSD license.
7 #
8 # Authors: Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>
9 """Functions for generating trees."""
10 from collections import defaultdict
11
12 import networkx as nx
13 from networkx.utils import generate_unique_node
14 from networkx.utils import py_random_state
15
16 __all__ = ['prefix_tree', 'random_tree']
17
18 #: The nil node, the only leaf node in a prefix tree.
19 #:
20 #: Each predecessor of the nil node corresponds to the end of a path
21 #: used to generate the prefix tree.
22 NIL = 'NIL'
23
24
25 def prefix_tree(paths):
26 """Creates a directed prefix tree from the given list of iterables.
27
28 Parameters
29 ----------
30 paths: iterable of lists
31 An iterable over "paths", which are themselves lists of
32 nodes. Common prefixes among these paths are converted into
33 common initial segments in the generated tree.
34
35 Most commonly, this may be an iterable over lists of integers,
36 or an iterable over Python strings.
37
38 Returns
39 -------
40 T: DiGraph
41 A directed graph representing an arborescence consisting of the
42 prefix tree generated by `paths`. Nodes are directed "downward",
43 from parent to child. A special "synthetic" root node is added
44 to be the parent of the first node in each path. A special
45 "synthetic" leaf node, the "nil" node, is added to be the child
46 of all nodes representing the last element in a path. (The
47 addition of this nil node technically makes this not an
48 arborescence but a directed acyclic graph; removing the nil node
49 makes it an arborescence.)
50
51 Each node has an attribute 'source' whose value is the original
52 element of the path to which this node corresponds. The 'source'
53 of the root node is None, and the 'source' of the nil node is
54 :data:`.NIL`.
55
56 The root node is the only node of in-degree zero in the graph,
57 and the nil node is the only node of out-degree zero. For
58 convenience, the nil node can be accessed via the :data:`.NIL`
59 attribute; for example::
60
61 >>> from networkx.generators.trees import NIL
62 >>> paths = ['ab', 'abs', 'ad']
63 >>> T, root = nx.prefix_tree(paths)
64 >>> T.predecessors(NIL) # doctest: +SKIP
65
66 root : string
67 The randomly generated uuid of the root node.
68
69 Notes
70 -----
71 The prefix tree is also known as a *trie*.
72
73 Examples
74 --------
75 Create a prefix tree from a list of strings with some common
76 prefixes::
77
78 >>> strings = ['ab', 'abs', 'ad']
79 >>> T, root = nx.prefix_tree(strings)
80
81 Continuing the above example, to recover the original paths that
82 generated the prefix tree, traverse up the tree from the
83 :data:`.NIL` node to the root::
84
85 >>> from networkx.generators.trees import NIL
86 >>>
87 >>> strings = ['ab', 'abs', 'ad']
88 >>> T, root = nx.prefix_tree(strings)
89 >>> recovered = []
90 >>> for v in T.predecessors(NIL):
91 ... s = ''
92 ... while v != root:
93 ... # Prepend the character `v` to the accumulator `s`.
94 ... s = str(T.nodes[v]['source']) + s
95 ... # Each non-nil, non-root node has exactly one parent.
96 ... v = next(T.predecessors(v))
97 ... recovered.append(s)
98 >>> sorted(recovered)
99 ['ab', 'abs', 'ad']
100
101 """
102 def _helper(paths, root, B):
103 """Recursively create a trie from the given list of paths.
104
105 `paths` is a list of paths, each of which is itself a list of
106 nodes, relative to the given `root` (but not including it). This
107 list of paths will be interpreted as a tree-like structure, in
108 which two paths that share a prefix represent two branches of
109 the tree with the same initial segment.
110
111 `root` is the parent of the node at index 0 in each path.
112
113 `B` is the "accumulator", the :class:`networkx.DiGraph`
114 representing the branching to which the new nodes and edges will
115 be added.
116
117 """
118 # Create a mapping from each head node to the list of tail paths
119 # remaining beneath that node.
120 children = defaultdict(list)
121 for path in paths:
122 # If the path is the empty list, that represents the empty
123 # string, so we add an edge to the NIL node.
124 if not path:
125 B.add_edge(root, NIL)
126 continue
127 # TODO In Python 3, this should be `child, *rest = path`.
128 child, rest = path[0], path[1:]
129 # `child` may exist as the head of more than one path in `paths`.
130 children[child].append(rest)
131 # Add a node for each child found above and add edges from the
132 # root to each child. In this loop, `head` is the child and
133 # `tails` is the list of remaining paths under that child.
134 for head, tails in children.items():
135 # We need to relabel each child with a unique name. To do
136 # this we simply change each key in the dictionary to be a
137 # (key, uuid) pair.
138 new_head = generate_unique_node()
139 # Ensure the new child knows the name of the old child so
140 # that the user can recover the mapping to the original
141 # nodes.
142 B.add_node(new_head, source=head)
143 B.add_edge(root, new_head)
144 _helper(tails, new_head, B)
145
146 # Initialize the prefix tree with a root node and a nil node.
147 T = nx.DiGraph()
148 root = generate_unique_node()
149 T.add_node(root, source=None)
150 T.add_node(NIL, source=NIL)
151 # Populate the tree.
152 _helper(paths, root, T)
153 return T, root
154
155
156 # From the Wikipedia article on Prüfer sequences:
157 #
158 # > Generating uniformly distributed random Prüfer sequences and
159 # > converting them into the corresponding trees is a straightforward
160 # > method of generating uniformly distributed random labelled trees.
161 #
162 @py_random_state(1)
163 def random_tree(n, seed=None):
164 """Returns a uniformly random tree on `n` nodes.
165
166 Parameters
167 ----------
168 n : int
169 A positive integer representing the number of nodes in the tree.
170 seed : integer, random_state, or None (default)
171 Indicator of random number generation state.
172 See :ref:`Randomness<randomness>`.
173
174 Returns
175 -------
176 NetworkX graph
177 A tree, given as an undirected graph, whose nodes are numbers in
178 the set {0, …, *n* - 1}.
179
180 Raises
181 ------
182 NetworkXPointlessConcept
183 If `n` is zero (because the null graph is not a tree).
184
185 Notes
186 -----
187 The current implementation of this function generates a uniformly
188 random Prüfer sequence then converts that to a tree via the
189 :func:`~networkx.from_prufer_sequence` function. Since there is a
190 bijection between Prüfer sequences of length *n* - 2 and trees on
191 *n* nodes, the tree is chosen uniformly at random from the set of
192 all trees on *n* nodes.
193
194 """
195 if n == 0:
196 raise nx.NetworkXPointlessConcept('the null graph is not a tree')
197 # Cannot create a Prüfer sequence unless `n` is at least two.
198 if n == 1:
199 return nx.empty_graph(1)
200 sequence = [seed.choice(range(n)) for i in range(n - 2)]
201 return nx.from_prufer_sequence(sequence)