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