Package dsc_suite :: Package tools :: Module graphtheory :: Class TernaryTrees
[hide private]
[frames] | no frames]

Class TernaryTrees

source code

object --+
         |
        TernaryTrees

basic TT functionality

This class implements basic ternary functionality, such as ternary tree numbering and generation.

Instance Methods [hide private]

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __init__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Static Methods [hide private]
 
get_num_ternary_trees(n)
Calculate number of possible ternary trees.
source code
 
get_random_ternary_tree(N)
Generate a random ternary tree.
source code
 
transform_panholzer_to_topology(T, root) source code
 
__transform_panholzer_to_topology_recursive(T, node, topology, dfs_order, parent=None) source code
Class Variables [hide private]
  LEFT = 0
  MIDDLE = 1
  RIGHT = 2
  PARENT = 3
  INTERNAL = 4
  DEPTH = 5
Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

get_num_ternary_trees(n)
Static Method

source code 

Calculate number of possible ternary trees.

n ... number of nodes

Binomial(3n,n)/(2n+1) (enumerates ternary trees and also non-crossing trees) http://www.research.att.com/~njas/sequences/A001764

get_random_ternary_tree(N)
Static Method

source code 

Generate a random ternary tree. Evenly distributed.

N ... number of (internal) nodes

Generate an evenly distributed random ternary tree. Approach taken from [Panholzer2002]. Returned format is a complete ternary tree with internal and external nodes. To get a random ternary tree only the internal nodes are to use.

Returns ternary tree in a list format where each entry represents a node. The index of the root node is also returned. T = [[LEFT, MIDDLE, RIGHT, PARENT, INTERNAL, DEPTH], ...]

returns T, root

NOTE: Depth information was intended to speed up the descendant test. The depth assignment is erroneous. Some parent-child nodes have the same depth. -> Don't use until resolved.