Mercurial > repos > shellac > sam_consensus_v3
diff env/lib/python3.9/site-packages/networkx/generators/trees.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/env/lib/python3.9/site-packages/networkx/generators/trees.py Mon Mar 22 18:12:50 2021 +0000 @@ -0,0 +1,194 @@ +"""Functions for generating trees.""" +from collections import defaultdict + +import networkx as nx +from networkx.utils import generate_unique_node +from networkx.utils import py_random_state + +__all__ = ["prefix_tree", "random_tree"] + +#: The nil node, the only leaf node in a prefix tree. +#: +#: Each predecessor of the nil node corresponds to the end of a path +#: used to generate the prefix tree. +NIL = "NIL" + + +def prefix_tree(paths): + """Creates a directed prefix tree from the given list of iterables. + + Parameters + ---------- + paths: iterable of lists + An iterable over "paths", which are themselves lists of + nodes. Common prefixes among these paths are converted into + common initial segments in the generated tree. + + Most commonly, this may be an iterable over lists of integers, + or an iterable over Python strings. + + Returns + ------- + T: DiGraph + A directed graph representing an arborescence consisting of the + prefix tree generated by `paths`. Nodes are directed "downward", + from parent to child. A special "synthetic" root node is added + to be the parent of the first node in each path. A special + "synthetic" leaf node, the "nil" node, is added to be the child + of all nodes representing the last element in a path. (The + addition of this nil node technically makes this not an + arborescence but a directed acyclic graph; removing the nil node + makes it an arborescence.) + + Each node has an attribute 'source' whose value is the original + element of the path to which this node corresponds. The 'source' + of the root node is None, and the 'source' of the nil node is + :data:`.NIL`. + + The root node is the only node of in-degree zero in the graph, + and the nil node is the only node of out-degree zero. For + convenience, the nil node can be accessed via the :data:`.NIL` + attribute; for example:: + + >>> from networkx.generators.trees import NIL + >>> paths = ["ab", "abs", "ad"] + >>> T, root = nx.prefix_tree(paths) + >>> T.predecessors(NIL) + <dict_keyiterator object at 0x...> + + root : string + The randomly generated uuid of the root node. + + Notes + ----- + The prefix tree is also known as a *trie*. + + Examples + -------- + Create a prefix tree from a list of strings with some common + prefixes:: + + >>> strings = ["ab", "abs", "ad"] + >>> T, root = nx.prefix_tree(strings) + + Continuing the above example, to recover the original paths that + generated the prefix tree, traverse up the tree from the + :data:`.NIL` node to the root:: + + >>> from networkx.generators.trees import NIL + >>> + >>> strings = ["ab", "abs", "ad"] + >>> T, root = nx.prefix_tree(strings) + >>> recovered = [] + >>> for v in T.predecessors(NIL): + ... s = "" + ... while v != root: + ... # Prepend the character `v` to the accumulator `s`. + ... s = str(T.nodes[v]["source"]) + s + ... # Each non-nil, non-root node has exactly one parent. + ... v = next(T.predecessors(v)) + ... recovered.append(s) + >>> sorted(recovered) + ['ab', 'abs', 'ad'] + + """ + + def _helper(paths, root, B): + """Recursively create a trie from the given list of paths. + + `paths` is a list of paths, each of which is itself a list of + nodes, relative to the given `root` (but not including it). This + list of paths will be interpreted as a tree-like structure, in + which two paths that share a prefix represent two branches of + the tree with the same initial segment. + + `root` is the parent of the node at index 0 in each path. + + `B` is the "accumulator", the :class:`networkx.DiGraph` + representing the branching to which the new nodes and edges will + be added. + + """ + # Create a mapping from each head node to the list of tail paths + # remaining beneath that node. + children = defaultdict(list) + for path in paths: + # If the path is the empty list, that represents the empty + # string, so we add an edge to the NIL node. + if not path: + B.add_edge(root, NIL) + continue + child, *rest = path + # `child` may exist as the head of more than one path in `paths`. + children[child].append(rest) + # Add a node for each child found above and add edges from the + # root to each child. In this loop, `head` is the child and + # `tails` is the list of remaining paths under that child. + for head, tails in children.items(): + # We need to relabel each child with a unique name. To do + # this we simply change each key in the dictionary to be a + # (key, uuid) pair. + new_head = generate_unique_node() + # Ensure the new child knows the name of the old child so + # that the user can recover the mapping to the original + # nodes. + B.add_node(new_head, source=head) + B.add_edge(root, new_head) + _helper(tails, new_head, B) + + # Initialize the prefix tree with a root node and a nil node. + T = nx.DiGraph() + root = generate_unique_node() + T.add_node(root, source=None) + T.add_node(NIL, source=NIL) + # Populate the tree. + _helper(paths, root, T) + return T, root + + +# From the Wikipedia article on Prüfer sequences: +# +# > Generating uniformly distributed random Prüfer sequences and +# > converting them into the corresponding trees is a straightforward +# > method of generating uniformly distributed random labelled trees. +# +@py_random_state(1) +def random_tree(n, seed=None): + """Returns a uniformly random tree on `n` nodes. + + Parameters + ---------- + n : int + A positive integer representing the number of nodes in the tree. + seed : integer, random_state, or None (default) + Indicator of random number generation state. + See :ref:`Randomness<randomness>`. + + Returns + ------- + NetworkX graph + A tree, given as an undirected graph, whose nodes are numbers in + the set {0, …, *n* - 1}. + + Raises + ------ + NetworkXPointlessConcept + If `n` is zero (because the null graph is not a tree). + + Notes + ----- + The current implementation of this function generates a uniformly + random Prüfer sequence then converts that to a tree via the + :func:`~networkx.from_prufer_sequence` function. Since there is a + bijection between Prüfer sequences of length *n* - 2 and trees on + *n* nodes, the tree is chosen uniformly at random from the set of + all trees on *n* nodes. + + """ + if n == 0: + raise nx.NetworkXPointlessConcept("the null graph is not a tree") + # Cannot create a Prüfer sequence unless `n` is at least two. + if n == 1: + return nx.empty_graph(1) + sequence = [seed.choice(range(n)) for i in range(n - 2)] + return nx.from_prufer_sequence(sequence)