Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.42 KB)

1
"""
2
Implementation of the Wright, Richmond, Odlyzko and McKay (WROM)
3
algorithm for the enumeration of all non-isomorphic free trees of a
4
given order.  Rooted trees are represented by level sequences, i.e.,
5
lists in which the i-th element specifies the distance of vertex i to
6
the root.
7

8
"""
9
#    Copyright (C) 2013 by
10
#    Aric Hagberg <hagberg@lanl.gov>
11
#    Dan Schult <dschult@colgate.edu>
12
#    Pieter Swart <swart@lanl.gov>
13
#    All rights reserved.
14
#    BSD license.
15
__author__ = "\n".join(["Aric Hagberg (hagberg@lanl.gov)",
16
                        "Mridul Seth (seth.mridul@gmail.com)"])
17

    
18
__all__ = ['nonisomorphic_trees',
19
           'number_of_nonisomorphic_trees']
20

    
21
import networkx as nx
22

    
23

    
24
def nonisomorphic_trees(order, create="graph"):
25
    """Returns a list of nonisomporphic trees
26

27
    Parameters
28
    ----------
29
    order : int
30
      order of the desired tree(s)
31

32
    create : graph or matrix (default="Graph)
33
      If graph is selected a list of trees will be returned,
34
      if matrix is selected a list of adjancency matrix will
35
      be returned
36

37
    Returns
38
    -------
39
    G : List of NetworkX Graphs
40

41
    M : List of Adjacency matrices
42

43
    References
44
    ----------
45

46
    """
47

    
48
    if order < 2:
49
        raise ValueError
50
    # start at the path graph rooted at its center
51
    layout = list(range(order // 2 + 1)) + list(range(1, (order + 1) // 2))
52

    
53
    while layout is not None:
54
        layout = _next_tree(layout)
55
        if layout is not None:
56
            if create == "graph":
57
                yield _layout_to_graph(layout)
58
            elif create == "matrix":
59
                yield _layout_to_matrix(layout)
60
            layout = _next_rooted_tree(layout)
61

    
62

    
63
def number_of_nonisomorphic_trees(order):
64
    """Returns the number of nonisomorphic trees
65

66
    Parameters
67
    ----------
68
    order : int
69
      order of the desired tree(s)
70

71
    Returns
72
    -------
73
    length : Number of nonisomorphic graphs for the given order
74

75
    References
76
    ----------
77

78
    """
79
    return sum(1 for _ in nonisomorphic_trees(order))
80

    
81

    
82
def _next_rooted_tree(predecessor, p=None):
83
    """One iteration of the Beyer-Hedetniemi algorithm."""
84

    
85
    if p is None:
86
        p = len(predecessor) - 1
87
        while predecessor[p] == 1:
88
            p -= 1
89
    if p == 0:
90
        return None
91

    
92
    q = p - 1
93
    while predecessor[q] != predecessor[p] - 1:
94
        q -= 1
95
    result = list(predecessor)
96
    for i in range(p, len(result)):
97
        result[i] = result[i - p + q]
98
    return result
99

    
100

    
101
def _next_tree(candidate):
102
    """One iteration of the Wright, Richmond, Odlyzko and McKay
103
    algorithm."""
104

    
105
    # valid representation of a free tree if:
106
    # there are at least two vertices at layer 1
107
    # (this is always the case because we start at the path graph)
108
    left, rest = _split_tree(candidate)
109

    
110
    # and the left subtree of the root
111
    # is less high than the tree with the left subtree removed
112
    left_height = max(left)
113
    rest_height = max(rest)
114
    valid = rest_height >= left_height
115

    
116
    if valid and rest_height == left_height:
117
        # and, if left and rest are of the same height,
118
        # if left does not encompass more vertices
119
        if len(left) > len(rest):
120
            valid = False
121
        # and, if they have the same number or vertices,
122
        # if left does not come after rest lexicographically
123
        elif len(left) == len(rest) and left > rest:
124
            valid = False
125

    
126
    if valid:
127
        return candidate
128
    else:
129
        # jump to the next valid free tree
130
        p = len(left)
131
        new_candidate = _next_rooted_tree(candidate, p)
132
        if candidate[p] > 2:
133
            new_left, new_rest = _split_tree(new_candidate)
134
            new_left_height = max(new_left)
135
            suffix = range(1, new_left_height + 2)
136
            new_candidate[-len(suffix):] = suffix
137
        return new_candidate
138

    
139

    
140
def _split_tree(layout):
141
    """Returns a tuple of two layouts, one containing the left
142
    subtree of the root vertex, and one containing the original tree
143
    with the left subtree removed."""
144

    
145
    one_found = False
146
    m = None
147
    for i in range(len(layout)):
148
        if layout[i] == 1:
149
            if one_found:
150
                m = i
151
                break
152
            else:
153
                one_found = True
154

    
155
    if m is None:
156
        m = len(layout)
157

    
158
    left = [layout[i] - 1 for i in range(1, m)]
159
    rest = [0] + [layout[i] for i in range(m, len(layout))]
160
    return (left, rest)
161

    
162

    
163
def _layout_to_matrix(layout):
164
    """Create the adjacency matrix for the tree specified by the
165
    given layout (level sequence)."""
166

    
167
    result = [[0] * len(layout) for i in range(len(layout))]
168
    stack = []
169
    for i in range(len(layout)):
170
        i_level = layout[i]
171
        if stack:
172
            j = stack[-1]
173
            j_level = layout[j]
174
            while j_level >= i_level:
175
                stack.pop()
176
                j = stack[-1]
177
                j_level = layout[j]
178
            result[i][j] = result[j][i] = 1
179
        stack.append(i)
180
    return result
181

    
182

    
183
def _layout_to_graph(layout):
184
    """Create a NetworkX Graph for the tree specified by the
185
    given layout(level sequence)"""
186
    result = [[0] * len(layout) for i in range(len(layout))]
187
    G = nx.Graph()
188
    stack = []
189
    for i in range(len(layout)):
190
        i_level = layout[i]
191
        if stack:
192
            j = stack[-1]
193
            j_level = layout[j]
194
            while j_level >= i_level:
195
                stack.pop()
196
                j = stack[-1]
197
                j_level = layout[j]
198
            G.add_edge(i, j)
199
        stack.append(i)
200
    return G