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[source]¶

Bases: object

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> from sage.graphs.trees import TreeIterator
>>> 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 - Integer(1):
...             return False
...         for tree in trees:
...             if tree.is_isomorphic(t):
...                 return False
...         trees.append(t)
...     return True
>>> check_trees(Integer(10))
True

Sage

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

Python

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