Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" 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. """ from __future__ import print_function
from libc.limits cimport INT_MAX from cysignals.memory cimport check_allocarray, sig_free
# from networkx import MultiGraph
from sage.graphs.base.sparse_graph cimport SparseGraph from sage.graphs.base.sparse_graph cimport SparseGraphBackend
cdef class TreeIterator: r""" 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 """
def __init__(self, int vertices): r""" Initializes an iterator over all trees with `n` vertices.
EXAMPLES::
sage: from sage.graphs.trees import TreeIterator sage: t = TreeIterator(100) # indirect doctest sage: print(t) Iterator over all trees with 100 vertices """
def __dealloc__(self): r""" EXAMPLES::
sage: from sage.graphs.trees import TreeIterator sage: t = TreeIterator(100) sage: t = None # indirect doctest """
def __str__(self): r""" EXAMPLES::
sage: from sage.graphs.trees import TreeIterator sage: t = TreeIterator(100) sage: print(t) # indirect doctest Iterator over all trees with 100 vertices """
def __iter__(self): r""" Returns an iterator over all the trees with `n` vertices.
EXAMPLES::
sage: from sage.graphs.trees import TreeIterator sage: t = TreeIterator(4) sage: list(iter(t)) [Graph on 4 vertices, Graph on 4 vertices] """
def __next__(self): r""" Returns the next tree with `n` vertices
EXAMPLES::
sage: from sage.graphs.trees import TreeIterator sage: T = TreeIterator(5) sage: [t for t in T] # indirect doctest [Graph on 5 vertices, Graph on 5 vertices, Graph on 5 vertices]
TESTS:
This used to be broken for trees with no vertices and was fixed in :trac:`13719` ::
sage: from sage.graphs.trees import TreeIterator sage: T = TreeIterator(0) sage: [t for t in T] # indirect doctest [Graph on 0 vertices] """
else:
else:
cdef int i cdef int vertex1 cdef int vertex2 cdef object G
# from networkx import MultiGraph # G = Graph(self.vertices) # cdef object XG = G._backend._nxg # # for i from 2 <= i <= self.vertices: # vertex1 = i - 1 # vertex2 = self.current_level_sequence[i - 1] - 1 # XG.add_edge(vertex1, vertex2) # # return G
# Currently, c_graph does not have all the same functionality as networkx. # Until it does, we can't generate graphs using the c_graph backend even # though it is twice as fast (for our purposes) as networkx.
cdef int generate_first_level_sequence(self): r""" Generates the level sequence representing the first tree with `n` vertices """ cdef int i cdef int k
else: else:
cdef int generate_next_level_sequence(self): r""" Generates the level sequence representing the next tree with `n` vertices """ cdef int i
else:
else:
else: else: else: else:
else: else: h2 = n if l[h2 - 1] == l[h1 - 1] - 1 and h1 == r: c = n + 1 else: c = INT_MAX
|