random spanning trees using the Aldous-Broder algorithm

[chapoton]

This implements the Aldous-Broder algorithm that uses a random walk to find a random spanning tree (with uniform distribution).

[chapoton]

New commits:

​3b2a308

trac #17182 random spanning trees

[ncohen]

This should probably go in graph/spanning_trees.py

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​06d6268

trac #17182 little more doc, small fixes

[ncohen]

1) Should be in spanning_trees.py

2) Fails on the empty graph

3) Infinite loop on disconnected graphs

4) found should be a set, not a list

Nathann

[ncohen]

Furthermore, all explanations of the Aldous-Broder algorithm that I find mention taking the initial vertex at random, while you always take the first one.

Nathann

[chapoton]

Any vertex does the job, see page 2 of ​https://www.cs.cmu.edu/~15859n/RelatedWork/Broder-GenRanSpanningTrees.pdf

I am working now on the move.

Should I use set, Set or frozenset ?

[ncohen]

Yo !

Any vertex does the job, see page 2 of ​https://www.cs.cmu.edu/~15859n/RelatedWork/Broder-GenRanSpanningTrees.pdf

Okay.

I am working now on the move.

Okay.

Should I use set, Set or frozenset ?

set is fine. Never use Set for anything else than teaching purposes, and frozenset makes no sense here as you want to add elements to the set.

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c382750

trac #17182 reviewer's remarks (all but one)

[chapoton]

I have a problem with the empty graph, but I do not see what is wrong with my code.

Another question : do you think I should raise an exception for the empty graph ? Does it have one spanning tree or none ? I would go for none.

I have also corrected Graph().spanning_trees(), that was failing also. It now says that the empty graph has no spanning tree, which is coherent with spanning_trees_count.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9f04077

trac #17182 solving the empty graph issue

[ncohen]

Hello,

The doc did not compile. I fixed it. A reference was defined twice (once in spanning_trees.pyx, another time in the copy of that function as it is imported in graph.py).

The 'see also' should appear a bit earlier, especially when there is a 'test' section. Otherwise nobody sees it.

I flagged the spanning tree in the doctest as #random, because the vertex ordering can depend on the architecture.

If you agree with the commit I added, please set this ticket to positive_review

Nathann

---

New commits:

​e0345a9

trac #17182: review

[chapoton]

Thank you Nathann !