Generation of trees

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

AUTHORS:

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

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.
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 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
next()

x.next() -> the next value, or raise StopIteration

Previous topic

PQ-Trees

Next topic

Matching Polynomial

This Page