Opened 6 years ago
Closed 6 years ago
#17182 closed enhancement (fixed)
random spanning trees using the Aldous-Broder algorithm
Reported by: | chapoton | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.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) | Commit: | e0345a9ec9b5e64e1d9f0d66eff279bfd5ea61d2 |
Dependencies: | Stopgaps: |
Description
This implements the Aldous-Broder algorithm that uses a random walk to find a random spanning tree (with uniform distribution).
Change History (14)
comment:1 Changed 6 years ago by
- Branch set to u/chapoton/17182
- Commit set to 3b2a308e2943c4f13c07e4e8d9da12e2ff2b3805
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
This should probably go in graph/spanning_trees.py
Nathann
comment:3 Changed 6 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 6 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 6 years ago by
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
comment:6 follow-up: ↓ 7 Changed 6 years ago by
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
?
comment:7 in reply to: ↑ 6 Changed 6 years ago by
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
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 6 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 6 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 6 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 6 years ago by
- Status changed from needs_work to needs_review
comment:12 Changed 6 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 6 years ago by
- Status changed from needs_review to positive_review
Thank you Nathann !
comment:14 Changed 6 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