prefix_tree_recursive(paths)
The original recursive version of prefix_tree for comparison. It is the same algorithm but the recursion is unrolled onto a stack.
Usually the paths are described as strings or lists of integers.
A "prefix tree" represents the prefix structure of the strings. Each node represents a prefix of some string. The root represents the empty prefix with children for the single letter prefixes which in turn have children for each double letter prefix starting with the single letter corresponding to the parent node, and so on.
More generally the prefixes do not need to be strings. A prefix refers to the start of a sequence. The root has children for each one element prefix and they have children for each two element prefix that starts with the one element sequence of the parent, and so on.
Note that this implementation uses integer nodes with an attribute. Each node has an attribute "source" whose value is the original element of the path to which this node corresponds. For example, suppose :None:None:`paths` consists of one path: "can". Then the nodes :None:None:`[1, 2, 3]` which represent this path have "source" values "c", "a" and "n".
All the descendants of a node have a common prefix in the sequence/path associated with that node. From the returned tree, ehe prefix for each node can be constructed by traversing the tree up to the root and accumulating the "source" values along the way.
The root node is always :None:None:`0` and has "source" attribute :None:None:`None`. The root is the only node with in-degree zero. The nil node is always :None:None:`-1` and has "source" attribute :None:None:`"NIL"`. The nil node is the only node with out-degree zero.
The prefix tree is also known as a trie.
An iterable of paths which are themselves sequences. Matching prefixes among these sequences are identified with nodes of the prefix tree. One leaf of the tree is associated with each path. (Identical paths are associated with the same leaf of the tree.)
A directed graph representing an arborescence consisting of the prefix tree generated by :None:None:`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 :None:None:`-1`, 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.)
Recursively creates a directed prefix tree from a list of paths.
>>> paths = ["ab", "abs", "ad"] >>> T = nx.prefix_tree(paths) >>> list(T.edges) [(0, 1), (1, 2), (1, 4), (2, -1), (2, 3), (3, -1), (4, -1)]
The leaf nodes can be obtained as predecessors of the nil node.
>>> root, NIL = 0, -1 >>> list(T.predecessors(NIL)) [2, 3, 4]
See :>>> recovered = [] >>> for v in T.predecessors(NIL): ... prefix = "" ... while v != root: ... prefix = str(T.nodes[v]["source"]) + prefix ... v = next(T.predecessors(v)) # only one predecessor ... recovered.append(prefix) >>> sorted(recovered) ['ab', 'abs', 'ad']
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them