ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tree / coding.py @ 5cef0f13
History  View  Annotate  Download (13 KB)
1 
# * encoding: utf8 *


2 
#

3 
# coding.py  functions for encoding and decoding trees as sequences

4 
#

5 
# Copyright 20152019 NetworkX developers.

6 
#

7 
# This file is part of NetworkX.

8 
#

9 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

10 
# information.

11 
"""Functions for encoding and decoding trees.

12 

13 
Since a tree is a highly restricted form of graph, it can be represented

14 
concisely in several ways. This module includes functions for encoding

15 
and decoding trees in the form of nested tuples and Prüfer

16 
sequences. The former requires a rooted tree, whereas the latter can be

17 
applied to unrooted trees. Furthermore, there is a bijection from Prüfer

18 
sequences to labeled trees.

19 

20 
"""

21 
from collections import Counter 
22 
from itertools import chain 
23  
24 
import networkx as nx 
25 
from networkx.utils import not_implemented_for 
26  
27 
__all__ = ['from_nested_tuple', 'from_prufer_sequence', 'NotATree', 
28 
'to_nested_tuple', 'to_prufer_sequence'] 
29  
30  
31 
class NotATree(nx.NetworkXException): 
32 
"""Raised when a function expects a tree (that is, a connected

33 
undirected graph with no cycles) but gets a nontree graph as input

34 
instead.

35 

36 
"""

37  
38  
39 
@not_implemented_for('directed') 
40 
def to_nested_tuple(T, root, canonical_form=False): 
41 
"""Returns a nested tuple representation of the given tree.

42 

43 
The nested tuple representation of a tree is defined

44 
recursively. The tree with one node and no edges is represented by

45 
the empty tuple, ``()``. A tree with ``k`` subtrees is represented

46 
by a tuple of length ``k`` in which each element is the nested tuple

47 
representation of a subtree.

48 

49 
Parameters

50 


51 
T : NetworkX graph

52 
An undirected graph object representing a tree.

53 

54 
root : node

55 
The node in ``T`` to interpret as the root of the tree.

56 

57 
canonical_form : bool

58 
If ``True``, each tuple is sorted so that the function returns

59 
a canonical form for rooted trees. This means "lighter" subtrees

60 
will appear as nested tuples before "heavier" subtrees. In this

61 
way, each isomorphic rooted tree has the same nested tuple

62 
representation.

63 

64 
Returns

65 


66 
tuple

67 
A nested tuple representation of the tree.

68 

69 
Notes

70 


71 
This function is *not* the inverse of :func:`from_nested_tuple`; the

72 
only guarantee is that the rooted trees are isomorphic.

73 

74 
See also

75 


76 
from_nested_tuple

77 
to_prufer_sequence

78 

79 
Examples

80 


81 
The tree need not be a balanced binary tree::

82 

83 
>>> T = nx.Graph()

84 
>>> T.add_edges_from([(0, 1), (0, 2), (0, 3)])

85 
>>> T.add_edges_from([(1, 4), (1, 5)])

86 
>>> T.add_edges_from([(3, 6), (3, 7)])

87 
>>> root = 0

88 
>>> nx.to_nested_tuple(T, root)

89 
(((), ()), (), ((), ()))

90 

91 
Continuing the above example, if ``canonical_form`` is ``True``, the

92 
nested tuples will be sorted::

93 

94 
>>> nx.to_nested_tuple(T, root, canonical_form=True)

95 
((), ((), ()), ((), ()))

96 

97 
Even the path graph can be interpreted as a tree::

98 

99 
>>> T = nx.path_graph(4)

100 
>>> root = 0

101 
>>> nx.to_nested_tuple(T, root)

102 
((((),),),)

103 

104 
"""

105  
106 
def _make_tuple(T, root, _parent): 
107 
"""Recursively compute the nested tuple representation of the

108 
given rooted tree.

109 

110 
``_parent`` is the parent node of ``root`` in the supertree in

111 
which ``T`` is a subtree, or ``None`` if ``root`` is the root of

112 
the supertree. This argument is used to determine which

113 
neighbors of ``root`` are children and which is the parent.

114 

115 
"""

116 
# Get the neighbors of `root` that are not the parent node. We

117 
# are guaranteed that `root` is always in `T` by construction.

118 
children = set(T[root])  {_parent}

119 
if len(children) == 0: 
120 
return ()

121 
nested = (_make_tuple(T, v, root) for v in children) 
122 
if canonical_form:

123 
nested = sorted(nested)

124 
return tuple(nested) 
125  
126 
# Do some sanity checks on the input.

127 
if not nx.is_tree(T): 
128 
raise nx.NotATree('provided graph is not a tree') 
129 
if root not in T: 
130 
raise nx.NodeNotFound('Graph {} contains no node {}'.format(T, root)) 
131  
132 
return _make_tuple(T, root, None) 
133  
134  
135 
def from_nested_tuple(sequence, sensible_relabeling=False): 
136 
"""Returns the rooted tree corresponding to the given nested tuple.

137 

138 
The nested tuple representation of a tree is defined

139 
recursively. The tree with one node and no edges is represented by

140 
the empty tuple, ``()``. A tree with ``k`` subtrees is represented

141 
by a tuple of length ``k`` in which each element is the nested tuple

142 
representation of a subtree.

143 

144 
Parameters

145 


146 
sequence : tuple

147 
A nested tuple representing a rooted tree.

148 

149 
sensible_relabeling : bool

150 
Whether to relabel the nodes of the tree so that nodes are

151 
labeled in increasing order according to their breadthfirst

152 
search order from the root node.

153 

154 
Returns

155 


156 
NetworkX graph

157 
The tree corresponding to the given nested tuple, whose root

158 
node is node 0. If ``sensible_labeling`` is ``True``, nodes will

159 
be labeled in breadthfirst search order starting from the root

160 
node.

161 

162 
Notes

163 


164 
This function is *not* the inverse of :func:`to_nested_tuple`; the

165 
only guarantee is that the rooted trees are isomorphic.

166 

167 
See also

168 


169 
to_nested_tuple

170 
from_prufer_sequence

171 

172 
Examples

173 


174 
Sensible relabeling ensures that the nodes are labeled from the root

175 
starting at 0::

176 

177 
>>> balanced = (((), ()), ((), ()))

178 
>>> T = nx.from_nested_tuple(balanced, sensible_relabeling=True)

179 
>>> edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]

180 
>>> all((u, v) in T.edges() or (v, u) in T.edges() for (u, v) in edges)

181 
True

182 

183 
"""

184  
185 
def _make_tree(sequence): 
186 
"""Recursively creates a tree from the given sequence of nested

187 
tuples.

188 

189 
This function employs the :func:`~networkx.tree.join` function

190 
to recursively join subtrees into a larger tree.

191 

192 
"""

193 
# The empty sequence represents the empty tree, which is the

194 
# (unique) graph with a single node. We mark the single node

195 
# with an attribute that indicates that it is the root of the

196 
# graph.

197 
if len(sequence) == 0: 
198 
return nx.empty_graph(1) 
199 
# For a nonempty sequence, get the subtrees for each child

200 
# sequence and join all the subtrees at their roots. After

201 
# joining the subtrees, the root is node 0.

202 
return nx.tree.join([(_make_tree(child), 0) for child in sequence]) 
203  
204 
# Make the tree and remove the `is_root` node attribute added by the

205 
# helper function.

206 
T = _make_tree(sequence) 
207 
if sensible_relabeling:

208 
# Relabel the nodes according to their breadthfirst search

209 
# order, starting from the root node (that is, the node 0).

210 
bfs_nodes = chain([0], (v for u, v in nx.bfs_edges(T, 0))) 
211 
labels = {v: i for i, v in enumerate(bfs_nodes)} 
212 
# We would like to use `copy=False`, but `relabel_nodes` doesn't

213 
# allow a relabel mapping that can't be topologically sorted.

214 
T = nx.relabel_nodes(T, labels) 
215 
return T

216  
217  
218 
@not_implemented_for('directed') 
219 
def to_prufer_sequence(T): 
220 
r"""Returns the Prüfer sequence of the given tree.

221 

222 
A *Prüfer sequence* is a list of *n*  2 numbers between 0 and

223 
*n*  1, inclusive. The tree corresponding to a given Prüfer

224 
sequence can be recovered by repeatedly joining a node in the

225 
sequence with a node with the smallest potential degree according to

226 
the sequence.

227 

228 
Parameters

229 


230 
T : NetworkX graph

231 
An undirected graph object representing a tree.

232 

233 
Returns

234 


235 
list

236 
The Prüfer sequence of the given tree.

237 

238 
Raises

239 


240 
NetworkXPointlessConcept

241 
If the number of nodes in `T` is less than two.

242 

243 
NotATree

244 
If `T` is not a tree.

245 

246 
KeyError

247 
If the set of nodes in `T` is not {0, …, *n*  1}.

248 

249 
Notes

250 


251 
There is a bijection from labeled trees to Prüfer sequences. This

252 
function is the inverse of the :func:`from_prufer_sequence`

253 
function.

254 

255 
Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead

256 
of from 0 to *n*  1. This function requires nodes to be labeled in

257 
the latter form. You can use :func:`~networkx.relabel_nodes` to

258 
relabel the nodes of your tree to the appropriate format.

259 

260 
This implementation is from [1]_ and has a running time of

261 
$O(n \log n)$.

262 

263 
See also

264 


265 
to_nested_tuple

266 
from_prufer_sequence

267 

268 
References

269 


270 
.. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.

271 
"An optimal algorithm for Prufer codes."

272 
*Journal of Software Engineering and Applications* 2.02 (2009): 111.

273 
<https://doi.org/10.4236/jsea.2009.22016>

274 

275 
Examples

276 


277 
There is a bijection between Prüfer sequences and labeled trees, so

278 
this function is the inverse of the :func:`from_prufer_sequence`

279 
function:

280 

281 
>>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]

282 
>>> tree = nx.Graph(edges)

283 
>>> sequence = nx.to_prufer_sequence(tree)

284 
>>> sequence

285 
[3, 3, 3, 4]

286 
>>> tree2 = nx.from_prufer_sequence(sequence)

287 
>>> list(tree2.edges()) == edges

288 
True

289 

290 
"""

291 
# Perform some sanity checks on the input.

292 
n = len(T)

293 
if n < 2: 
294 
msg = 'Prüfer sequence undefined for trees with fewer than two nodes'

295 
raise nx.NetworkXPointlessConcept(msg)

296 
if not nx.is_tree(T): 
297 
raise nx.NotATree('provided graph is not a tree') 
298 
if set(T) != set(range(n)): 
299 
raise KeyError('tree must have node labels {0, ..., n  1}') 
300  
301 
degree = dict(T.degree())

302  
303 
def parents(u): 
304 
return next(v for v in T[u] if degree[v] > 1) 
305  
306 
index = u = min(k for k in range(n) if degree[k] == 1) 
307 
result = [] 
308 
for i in range(n  2): 
309 
v = parents(u) 
310 
result.append(v) 
311 
degree[v] = 1

312 
if v < index and degree[v] == 1: 
313 
u = v 
314 
else:

315 
index = u = min(k for k in range(index + 1, n) if degree[k] == 1) 
316 
return result

317  
318  
319 
def from_prufer_sequence(sequence): 
320 
r"""Returns the tree corresponding to the given Prüfer sequence.

321 

322 
A *Prüfer sequence* is a list of *n*  2 numbers between 0 and

323 
*n*  1, inclusive. The tree corresponding to a given Prüfer

324 
sequence can be recovered by repeatedly joining a node in the

325 
sequence with a node with the smallest potential degree according to

326 
the sequence.

327 

328 
Parameters

329 


330 
sequence : list

331 
A Prüfer sequence, which is a list of *n*  2 integers between

332 
zero and *n*  1, inclusive.

333 

334 
Returns

335 


336 
NetworkX graph

337 
The tree corresponding to the given Prüfer sequence.

338 

339 
Notes

340 


341 
There is a bijection from labeled trees to Prüfer sequences. This

342 
function is the inverse of the :func:`from_prufer_sequence` function.

343 

344 
Sometimes Prüfer sequences use nodes labeled from 1 to *n* instead

345 
of from 0 to *n*  1. This function requires nodes to be labeled in

346 
the latter form. You can use :func:`networkx.relabel_nodes` to

347 
relabel the nodes of your tree to the appropriate format.

348 

349 
This implementation is from [1]_ and has a running time of

350 
$O(n \log n)$.

351 

352 
References

353 


354 
.. [1] Wang, Xiaodong, Lei Wang, and Yingjie Wu.

355 
"An optimal algorithm for Prufer codes."

356 
*Journal of Software Engineering and Applications* 2.02 (2009): 111.

357 
<https://doi.org/10.4236/jsea.2009.22016>

358 

359 
See also

360 


361 
from_nested_tuple

362 
to_prufer_sequence

363 

364 
Examples

365 


366 
There is a bijection between Prüfer sequences and labeled trees, so

367 
this function is the inverse of the :func:`to_prufer_sequence`

368 
function:

369 

370 
>>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)]

371 
>>> tree = nx.Graph(edges)

372 
>>> sequence = nx.to_prufer_sequence(tree)

373 
>>> sequence

374 
[3, 3, 3, 4]

375 
>>> tree2 = nx.from_prufer_sequence(sequence)

376 
>>> list(tree2.edges()) == edges

377 
True

378 

379 
"""

380 
n = len(sequence) + 2 
381 
# `degree` stores the remaining degree (plus one) for each node. The

382 
# degree of a node in the decoded tree is one more than the number

383 
# of times it appears in the code.

384 
degree = Counter(chain(sequence, range(n)))

385 
T = nx.empty_graph(n) 
386 
# `not_orphaned` is the set of nodes that have a parent in the

387 
# tree. After the loop, there should be exactly two nodes that are

388 
# not in this set.

389 
not_orphaned = set()

390 
index = u = min(k for k in range(n) if degree[k] == 1) 
391 
for v in sequence: 
392 
T.add_edge(u, v) 
393 
not_orphaned.add(u) 
394 
degree[v] = 1

395 
if v < index and degree[v] == 1: 
396 
u = v 
397 
else:

398 
index = u = min(k for k in range(index + 1, n) if degree[k] == 1) 
399 
# At this point, there must be exactly two orphaned nodes; join them.

400 
orphans = set(T)  not_orphaned

401 
u, v = orphans 
402 
T.add_edge(u, v) 
403 
return T
