Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / tree / coding.py @ 5cef0f13

History | View | Annotate | Download (13 KB)

1
# -*- encoding: utf-8 -*-
2
#
3
# coding.py - functions for encoding and decoding trees as sequences
4
#
5
# Copyright 2015-2019 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 non-tree 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 breadth-first
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 breadth-first 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 breadth-first 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