Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.generators.nonisomorphic_trees

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

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

__all__ = ['nonisomorphic_trees',
           'number_of_nonisomorphic_trees']

import networkx as nx


[docs]def nonisomorphic_trees(order, create="graph"): """Returns a list of nonisomporphic trees Parameters ---------- order : int order of the desired tree(s) create : graph or matrix (default="Graph) If graph is selected a list of trees will be returned, if matrix is selected a list of adjancency matrix will be returned Returns ------- G : List of NetworkX Graphs M : List of Adjacency matrices References ---------- """ if order < 2: raise ValueError # start at the path graph rooted at its center layout = list(range(order // 2 + 1)) + list(range(1, (order + 1) // 2)) while layout is not None: layout = _next_tree(layout) if layout is not None: if create == "graph": yield _layout_to_graph(layout) elif create == "matrix": yield _layout_to_matrix(layout) layout = _next_rooted_tree(layout)
[docs]def number_of_nonisomorphic_trees(order): """Returns the number of nonisomorphic trees Parameters ---------- order : int order of the desired tree(s) Returns ------- length : Number of nonisomorphic graphs for the given order References ---------- """ return sum(1 for _ in nonisomorphic_trees(order))
def _next_rooted_tree(predecessor, p=None): """One iteration of the Beyer-Hedetniemi algorithm.""" if p is None: p = len(predecessor) - 1 while predecessor[p] == 1: p -= 1 if p == 0: return None q = p - 1 while predecessor[q] != predecessor[p] - 1: q -= 1 result = list(predecessor) for i in range(p, len(result)): result[i] = result[i - p + q] return result def _next_tree(candidate): """One iteration of the Wright, Richmond, Odlyzko and McKay algorithm.""" # valid representation of a free tree if: # there are at least two vertices at layer 1 # (this is always the case because we start at the path graph) left, rest = _split_tree(candidate) # and the left subtree of the root # is less high than the tree with the left subtree removed left_height = max(left) rest_height = max(rest) valid = rest_height >= left_height if valid and rest_height == left_height: # and, if left and rest are of the same height, # if left does not encompass more vertices if len(left) > len(rest): valid = False # and, if they have the same number or vertices, # if left does not come after rest lexicographically elif len(left) == len(rest) and left > rest: valid = False if valid: return candidate else: # jump to the next valid free tree p = len(left) new_candidate = _next_rooted_tree(candidate, p) if candidate[p] > 2: new_left, new_rest = _split_tree(new_candidate) new_left_height = max(new_left) suffix = range(1, new_left_height + 2) new_candidate[-len(suffix):] = suffix return new_candidate def _split_tree(layout): """Return a tuple of two layouts, one containing the left subtree of the root vertex, and one containing the original tree with the left subtree removed.""" one_found = False m = None for i in range(len(layout)): if layout[i] == 1: if one_found: m = i break else: one_found = True if m is None: m = len(layout) left = [layout[i] - 1 for i in range(1, m)] rest = [0] + [layout[i] for i in range(m, len(layout))] return (left, rest) def _layout_to_matrix(layout): """Create the adjacency matrix for the tree specified by the given layout (level sequence).""" result = [[0] * len(layout) for i in range(len(layout))] stack = [] for i in range(len(layout)): i_level = layout[i] if stack: j = stack[-1] j_level = layout[j] while j_level >= i_level: stack.pop() j = stack[-1] j_level = layout[j] result[i][j] = result[j][i] = 1 stack.append(i) return result def _layout_to_graph(layout): """Create a NetworkX Graph for the tree specified by the given layout(level sequence)""" result = [[0] * len(layout) for i in range(len(layout))] G = nx.Graph() stack = [] for i in range(len(layout)): i_level = layout[i] if stack: j = stack[-1] j_level = layout[j] while j_level >= i_level: stack.pop() j = stack[-1] j_level = layout[j] G.add_edge(i, j) stack.append(i) return G