ioftools / networkxMiCe / networkxmaster / networkx / generators / trees.py @ 5cef0f13
History  View  Annotate  Download (7.33 KB)
1 
# * encoding: utf8 *


2 
# Copyright (C) 20152019 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 indegree zero in the graph,

57 
and the nil node is the only node of outdegree 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.node[v]['source']) + s

95 
... # Each nonnil, nonroot 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 treelike 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)
