Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / trees.py @ 5cef0f13

History | View | Annotate | Download (7.33 KB)

1
# -*- encoding: utf-8 -*-
2
#    Copyright (C) 2015-2019 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 in-degree zero in the graph,
57
        and the nil node is the only node of out-degree 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 non-nil, non-root 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 tree-like 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)