Faster random tree generator

[dcoudert]

We use a heap to replace a loop searching for the vertex with smallest index and count 0 with a pop operation. The change is safe as it does not modify the order in which vertices are considered. This way, the generator is no longer quadratic.

Before (with #33579)

sage: %time T = graphs.RandomTree(10, seed=0)
CPU times: user 380 µs, sys: 84 µs, total: 464 µs
Wall time: 448 µs
sage: %time T = graphs.RandomTree(100, seed=0)
CPU times: user 1.44 ms, sys: 118 µs, total: 1.56 ms
Wall time: 1.57 ms
sage: %time T = graphs.RandomTree(1000, seed=0)
CPU times: user 46.1 ms, sys: 2.34 ms, total: 48.5 ms
Wall time: 47.1 ms
sage: %time T = graphs.RandomTree(10000, seed=0)
CPU times: user 2.75 s, sys: 14.8 ms, total: 2.77 s
Wall time: 2.78 s

After

sage: %time T = graphs.RandomTree(10, seed=0)
CPU times: user 363 µs, sys: 60 µs, total: 423 µs
Wall time: 407 µs
sage: %time T = graphs.RandomTree(100, seed=0)
CPU times: user 1.19 ms, sys: 629 µs, total: 1.82 ms
Wall time: 1.26 ms
sage: %time T = graphs.RandomTree(1000, seed=0)
CPU times: user 6.52 ms, sys: 156 µs, total: 6.68 ms
Wall time: 6.68 ms
sage: %time T = graphs.RandomTree(10000, seed=0)
CPU times: user 59.3 ms, sys: 3.63 ms, total: 63 ms
Wall time: 62 ms

Depends on #33579

CC: @tscrim

Component: graph theory

Author: David Coudert

Branch/Commit: ada25e3

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33743

[dcoudert]

Commit: ada25e3

[dcoudert]

New commits:

a7e1e54	trac #33579: ensure random graph generators use parameter seed
26fe186	trac #33579: fix some doctests
f0e7684	trac #33579: Merged with 9.6.beta7
2f3f304	trac #33579: fix doctests in sagebook
6cbdf91	trac #33579: fix doctest for 32-bit
fff1d8b	trac #33743: merged #33579 with 9.6.rc1
ada25e3	trac #33743: faster random tree generator

[dcoudert]

Branch: public/graphs/33743_random_tree

[dcoudert]

Dependencies: #33579

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:2

Just goes to show that using the right data structures is important.

[vbraun]

Changed branch from public/graphs/33743_random_tree to ada25e3