Generation of trees
This is an implementation of the algorithm for generating trees with vertices
(up to isomorphism) in constant time per tree described in [WRIGHT-ETAL].
AUTHORS:
REFERENCES:
[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.
Bases: object
This class iterates over all trees with n vertices (up to isomorphism).
EXAMPLES:
sage: from sage.graphs.trees import TreeIterator
sage: def check_trees(n):
... trees = []
... for t in TreeIterator(n):
... if t.is_tree() == False:
... 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) == True:
... return False
... trees.append(t)
... return True
sage: print check_trees(10)
True
sage: from sage.graphs.trees import TreeIterator
sage: count = 0
sage: for t in TreeIterator(15):
... count += 1
sage: print count
7741
x.next() -> the next value, or raise StopIteration