random_spanning_tree ignores weights

[pelegm]

!Aldous/Broder on a weighted graph should perform a random walk on that graph which considers the weights, and this is not the case at the moment.

Options:

1. make the walk consider the weights
2. add a warning for weighted graphs

Component: graph theory

Keywords: random_spanning_tree, aldous/broder, weighted_graphs

Author: David Coudert

Branch/Commit: 16816c8

Reviewer: Frédéric Chapoton

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

[pelegm]

comment:1

I don't have a development environment on my computer at the moment, but the difference should be in the following line:

new_s = neighbours[randint(0, len(neighbours) - 1)]

Instead, new_s should be chosen with weights considered (if and only if the graph is weighted). The sage function choice does not support weights, but numpy's choice does:

https://stackoverflow.com/a/26196078/1565828

[dcoudert]

Author: David Coudert

[dcoudert]

Branch: public/graphs/30566_random_spanning_tree

[dcoudert]

Commit: 67c8cbb

[dcoudert]

comment:3

With this branch, the walk considers the weights.

---

New commits:

67c8cbb

trac #30566: random spanning tree by weights

[mkoeppe]

comment:4

Moving to 9.4, as 9.3 has been released.

[mkoeppe]

comment:5

Setting a new milestone for this ticket based on a cursory review.

[sagetrac-git]

Changed commit from 67c8cbb to d410caa

[sagetrac-git]

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

1256172	trac #30566: merged with 9.5.beta5
d410caa	trac #30566: cleaner use of weights

[dcoudert]

comment:7

Clean the use of weights as part of #13112

[fchapoton]

comment:8

ca me parait bien. Peut-etre ajouter un doctest que le resultat est bien un arbre lorsqu'on utilise les poids ?

[sagetrac-git]

Changed commit from d410caa to 16816c8

[sagetrac-git]

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

16816c8

trac #30566: check that the output is a tree

[dcoudert]

comment:10

Tu as raison.

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:11

ok, positif

[vbraun]

Changed branch from public/graphs/30566_random_spanning_tree to 16816c8