Opened 7 years ago
Closed 7 years ago
#17182 closed enhancement (fixed)
random spanning trees using the AldousBroder algorithm
Reported by:  chapoton  Owned by:  

Priority:  minor  Milestone:  sage6.4 
Component:  graph theory  Keywords:  random tree 
Cc:  ncohen  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  e0345a9 (Commits, GitHub, GitLab)  Commit:  e0345a9ec9b5e64e1d9f0d66eff279bfd5ea61d2 
Dependencies:  Stopgaps: 
Description
This implements the AldousBroder algorithm that uses a random walk to find a random spanning tree (with uniform distribution).
Change History (14)
comment:1 Changed 7 years ago by
 Branch set to u/chapoton/17182
 Commit set to 3b2a308e2943c4f13c07e4e8d9da12e2ff2b3805
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
This should probably go in graph/spanning_trees.py
Nathann
comment:3 Changed 7 years ago by
 Commit changed from 3b2a308e2943c4f13c07e4e8d9da12e2ff2b3805 to 06d62687aeca758eced0d3605c767cfac5dd985d
Branch pushed to git repo; I updated commit sha1. New commits:
06d6268  trac #17182 little more doc, small fixes

comment:4 Changed 7 years ago by
 Status changed from needs_review to needs_work
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
comment:5 Changed 7 years ago by
Furthermore, all explanations of the AldousBroder
algorithm that I find mention taking the initial vertex at random, while you always take the first one.
Nathann
comment:6 followup: ↓ 7 Changed 7 years ago by
Any vertex does the job, see page 2 of https://www.cs.cmu.edu/~15859n/RelatedWork/BroderGenRanSpanningTrees.pdf
I am working now on the move.
Should I use set
, Set
or frozenset
?
comment:7 in reply to: ↑ 6 Changed 7 years ago by
Yo !
Any vertex does the job, see page 2 of https://www.cs.cmu.edu/~15859n/RelatedWork/BroderGenRanSpanningTrees.pdf
Okay.
I am working now on the move.
Okay.
Should I use
set
,Set
orfrozenset
?
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
comment:8 Changed 7 years ago by
 Commit changed from 06d62687aeca758eced0d3605c767cfac5dd985d to c382750f9cd0d08f492d9aed2f35b2410d1f5f24
Branch pushed to git repo; I updated commit sha1. New commits:
c382750  trac #17182 reviewer's remarks (all but one)

comment:9 Changed 7 years ago by
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.
comment:10 Changed 7 years ago by
 Commit changed from c382750f9cd0d08f492d9aed2f35b2410d1f5f24 to 9f04077fa49968c80334d1c2fc58ce46d93febfd
Branch pushed to git repo; I updated commit sha1. New commits:
9f04077  trac #17182 solving the empty graph issue

comment:11 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:12 Changed 7 years ago by
 Branch changed from u/chapoton/17182 to public/17182
 Commit changed from 9f04077fa49968c80334d1c2fc58ce46d93febfd to e0345a9ec9b5e64e1d9f0d66eff279bfd5ea61d2
 Reviewers set to Nathann Cohen
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

comment:13 Changed 7 years ago by
 Status changed from needs_review to positive_review
Thank you Nathann !
comment:14 Changed 7 years ago by
 Branch changed from public/17182 to e0345a9ec9b5e64e1d9f0d66eff279bfd5ea61d2
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #17182 random spanning trees