Generation of trees

This is an implementation of the algorithm for generating trees with \(n\) vertices (up to isomorphism) in constant time per tree described in [WRIGHT-ETAL].


  • Ryan Dingman (2009-04-16): initial version


[WRIGHT-ETAL]Wright, Robert Alan; Richmond, Bruce; Odlyzko, Andrew; McKay, Brendan D. Constant time generation of free trees. SIAM J. Comput. 15 (1986), no. 2, 540–548.
class sage.graphs.trees.TreeIterator

Bases: object

This class iterates over all trees with n vertices (up to isomorphism).


sage: from sage.graphs.trees import TreeIterator
sage: def check_trees(n):
....:     trees = []
....:     for t in TreeIterator(n):
....:         if not t.is_tree():
....:             return False
....:         if t.num_verts() != n:
....:             return False
....:         if t.num_edges() != n - 1:
....:             return False
....:         for tree in trees:
....:             if tree.is_isomorphic(t):
....:                 return False
....:         trees.append(t)
....:     return True
sage: check_trees(10)
sage: from sage.graphs.trees import TreeIterator
sage: count = 0
sage: for t in TreeIterator(15):
....:     count += 1
sage: count
next() -> the next value, or raise StopIteration