networkx.generators.trees.prefix_tree¶

prefix_tree
(paths)[source]¶ 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
NIL
.The root node is the only node of indegree zero in the graph, and the nil node is the only node of outdegree zero. For convenience, the nil node can be accessed via the
NIL
attribute; for example:>>> from networkx.generators.trees import NIL >>> paths = ['ab', 'abs', 'ad'] >>> T, root = nx.prefix_tree(paths) >>> T.predecessors(NIL)
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
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.node[v]['source']) + s ... # Each nonnil, nonroot node has exactly one parent. ... v = next(T.predecessors(v)) ... recovered.append(s) >>> sorted(recovered) ['ab', 'abs', 'ad']