Statistics
| Branch: | Revision:

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

 1 ```""" ``` ```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 ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# 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 ``` ```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) ``` ```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): ``` ``` """Returns 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 =  + [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 = [ * 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 = [ * 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 ```