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: 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
-
next
()¶ x.next() -> the next value, or raise StopIteration
-