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 [WROM1986].

AUTHORS:

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

class sage.graphs.trees.TreeIterator

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 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)
True

sage: from sage.graphs.trees import TreeIterator
sage: count = 0
sage: for t in TreeIterator(15):
....:     count += 1
sage: count
7741