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 chapoton

  • Branch set to u/chapoton/17182
  • Commit set to 3b2a308e2943c4f13c07e4e8d9da12e2ff2b3805
  • Status changed from new to needs_review

New commits:

3b2a308trac #17182 random spanning trees

comment:2 Changed 6 years ago by ncohen

This should probably go in graph/spanning_trees.py

Nathann

comment:3 Changed 6 years ago by git

  • Commit changed from 3b2a308e2943c4f13c07e4e8d9da12e2ff2b3805 to 06d62687aeca758eced0d3605c767cfac5dd985d

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

06d6268trac #17182 little more doc, small fixes

comment:4 Changed 6 years ago by ncohen

  • 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 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

comment:6 follow-up: Changed 6 years ago by 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 ?

comment:7 in reply to: ↑ 6 Changed 6 years ago by 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

comment:8 Changed 6 years ago by git

  • Commit changed from 06d62687aeca758eced0d3605c767cfac5dd985d to c382750f9cd0d08f492d9aed2f35b2410d1f5f24

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

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

comment:9 Changed 6 years ago by 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.

comment:10 Changed 6 years ago by git

  • Commit changed from c382750f9cd0d08f492d9aed2f35b2410d1f5f24 to 9f04077fa49968c80334d1c2fc58ce46d93febfd

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

9f04077trac #17182 solving the empty graph issue

comment:11 Changed 6 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:12 Changed 6 years ago by ncohen

  • 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:

e0345a9trac #17182: review

comment:13 Changed 6 years ago by chapoton

  • Status changed from needs_review to positive_review

Thank you Nathann !

comment:14 Changed 6 years ago by vbraun

  • Branch changed from public/17182 to e0345a9ec9b5e64e1d9f0d66eff279bfd5ea61d2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.