Skip to content

Instantly share code, notes, and snippets.

@mango314

mango314/readme.md

Last active April 30, 2022 04:47
Show Gist options
  • Save mango314/4512890 to your computer and use it in GitHub Desktop.
Save mango314/4512890 to your computer and use it in GitHub Desktop.
Download ZIP
Implementation of David Wilson's Uniform Spanning Tree Algorithm
Raw
readme.md

David Wilson (at Microsoft Research) designed a very simple algorithm for counting uniform spanning trees that mathematicians study as well as theoretical computer scientists. Not entirely sure how UST can be used in software engineering, but we implement it in Python and output the result in d3.js

The paper Trees and Matchings makes for any interesting reading on the cusp between combinatorics, statiscal mechanics and theoretical computer science.

Manually:

  • place all files in the same folder
  • run ust.py (can give you UST of any size, but just use n = 30) which outputs ust.txt
  • open ust.html reads ust.txt and produces a nice iage.
  • possible you need to set up a server due to same-origin-policy issues

If you give me a few minutes, I can write a Bottle.py server that does all this for you.

As it runs now:

  • place all files in the same folder
  • run server.py
  • go to localhost:8080/
Raw
server.py
from bottle import static_file, route, run
import ust
@route('/static/<filename>')
def server_static(filename):
return static_file(filename, root='...')
@route('/')
def sup():
ust.toText(ust.maze(30))
return static_file('ust.html', root='...')
run(host='localhost', port=8080, debug=True)
Raw
ust.html
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
<style type="text/css">
svg { background:#888; }
</style>
</head>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script type="text/javascript">
scale = 20;
width = (30+1)*scale;
height = (30+1)*scale;
var svg = d3.select("body").append("svg:svg")
.attr("width",width)
.attr("height",height);
d3.tsv("/static/ust.txt", function(d){
for(var i= 0; i < d.length; i++){
if(d[i].b == d[i].y){
if(d[i].x - d[i].a > 0){
console.log(d[i].x - d[i].a);
svg.append("rect")
.attr("width", scale*(d[i].x - d[i].a)+10)
.attr("height",10)
.attr("x",scale*d[i].a + 15)
.attr("y",scale*d[i].b + 15)
.attr("fill","yellow");
}
if(d[i].a - d[i].x > 0 ){
console.log(d[i].a - d[i].x);
svg.append("rect")
.attr("width", scale*(d[i].a - d[i].x)+10)
.attr("height",10)
.attr("x",scale*d[i].x + 15)
.attr("y",scale*d[i].y + 15)
.attr("fill","yellow");
}
}
else if(d[i].a == d[i].x){
if(d[i].y - d[i].b > 0){
console.log(d[i].y - d[i].b);
svg.append("rect")
.attr("width", 10)
.attr("height",scale*(d[i].y - d[i].b)+10)
.attr("x",scale*d[i].a+15)
.attr("y",scale*d[i].b+15)
.attr("fill","yellow");
}
if(d[i].b - d[i].y > 0){
console.log(d[i].b - d[i].y);
svg.append("rect")
.attr("width", 10)
.attr("height",scale*(d[i].b - d[i].y)+10)
.attr("x",scale*d[i].x+15)
.attr("y",scale*d[i].y+15)
.attr("fill","yellow");
}
}
}
});
</script>
</body>
</html>
Raw
ust.py
import random
def maze(n):
grid = [[0 for y in range(n)] for x in range(n)]
grid[int(n*random.random())][int(n*random.random())] = 1
tree = []
while(sum([sum(x) for x in grid]) < n*n):
a,b = int(n*random.random()), int(n*random.random())
while(grid[a][b]):
a,b = int(n*random.random()), int(n*random.random())
walk = [(a,b)]
while(True):
c = int(4*random.random())
if(c==0 and a < n-1): a+=1
if(c==1 and a > 0): a-=1
if(c==2 and b < n-1): b+=1
if(c==3 and b > 0): b-=1
if(grid[a][b]):
break
elif(walk[-1] != (a,b)): walk += [(a,b)]
c,d = walk[-1][0], walk[-1][1]
grid[c][d] = 1
tree += [(walk[-1],(a,b))]
return tree
def toText(tree):
s = ""
s += "a\tb\tx\ty\n"
for x in tree[:-1]:
s += "%s\t%s\t%s\t%s\n"% (x[0][0],x[0][1],x[1][0],x[1][1])
s += "%s\t%s\t%s\t%s"% (tree[-1][0][0],tree[-1][0][1],tree[-1][1][0],tree[-1][1][1])
out = file("ust.txt","w")
out.write(s)
return s
if __name__ == "__main__":
#n = input("How large is your grid?\t")
n = 30
tree = maze(n)
Raw
ust.txt
a b x y
18 1 19 1
18 2 18 1
19 2 19 1
20 2 19 2
18 3 18 2
17 3 18 3
16 3 17 3
16 2 16 3
15 3 16 3
20 3 20 2
19 3 18 3
15 4 15 3
14 3 15 3
21 3 20 3
13 3 14 3
19 4 19 3
14 4 15 4
21 2 21 3
12 3 13 3
13 4 13 3
15 2 16 2
20 4 20 3
12 4 13 4
22 2 21 2
11 3 12 3
11 4 12 4
17 4 17 3
11 5 11 4
10 5 11 5
17 5 17 4
11 6 11 5
21 4 20 4
21 1 21 2
21 5 21 4
22 1 21 1
10 6 10 5
19 5 19 4
22 4 21 4
10 7 10 6
20 5 20 4
19 6 19 5
17 6 17 5
10 4 11 4
23 2 22 2
22 5 22 4
10 3 10 4
20 6 19 6
9 4 10 4
23 3 23 2
10 8 10 7
10 9 10 8
9 7 10 7
10 10 10 9
23 4 22 4
10 2 10 3
20 7 20 6
23 5 23 4
24 2 23 2
8 4 9 4
10 11 10 10
24 5 23 5
9 8 10 8
10 12 10 11
11 7 10 7
17 7 17 6
10 13 10 12
11 11 10 11
9 2 10 2
19 7 19 6
23 6 23 5
17 8 17 7
23 7 23 6
12 11 11 11
24 4 24 5
17 9 17 8
9 6 10 6
18 8 17 8
9 9 10 9
18 9 17 9
8 6 9 6
11 8 11 7
25 5 24 5
11 2 11 3
16 9 17 9
8 8 9 8
8 7 8 6
20 8 20 7
24 6 23 6
26 5 25 5
21 8 20 8
16 8 16 9
12 10 12 11
24 1 24 2
9 1 9 2
11 13 10 13
15 9 16 9
11 14 11 13
21 0 21 1
9 12 10 12
9 10 9 9
22 6 23 6
15 10 15 9
17 10 17 9
11 15 11 14
25 1 24 1
8 2 9 2
22 8 21 8
8 12 9 12
15 11 15 10
18 10 18 9
10 15 11 15
11 16 11 15
23 8 22 8
14 2 14 3
12 15 11 15
13 15 12 15
22 9 22 8
13 16 13 15
8 3 8 2
7 4 8 4
22 10 22 9
14 15 13 15
9 15 10 15
20 9 20 8
7 8 8 8
15 15 14 15
13 10 12 10
7 2 8 2
24 3 23 3
12 16 11 16
7 12 8 12
7 9 7 8
14 14 14 15
27 5 26 5
15 14 14 14
10 14 11 14
24 8 23 8
7 3 7 2
12 17 12 16
7 13 7 12
24 9 24 8
6 2 7 2
26 6 26 5
15 12 15 11
16 15 15 15
25 9 24 9
23 10 22 10
14 16 14 15
13 11 12 11
24 10 23 10
16 16 16 15
20 10 20 9
24 0 24 1
18 4 18 3
6 12 7 12
6 9 7 9
9 5 9 4
23 1 22 1
5 12 6 12
17 15 16 15
15 16 16 16
4 12 5 12
28 5 27 5
6 13 6 12
25 10 25 9
16 10 17 10
7 14 7 13
25 11 25 10
14 17 14 16
7 15 7 14
10 16 10 15
13 14 14 14
12 18 12 17
20 11 20 10
13 9 13 10
11 18 12 18
13 17 14 17
16 11 16 10
26 1 25 1
13 18 12 18
26 11 25 11
5 9 6 9
27 6 27 5
17 16 17 15
26 12 26 11
5 2 6 2
12 19 12 18
9 16 9 15
8 16 9 16
25 6 26 6
28 4 28 5
13 19 12 19
14 18 13 18
13 8 13 9
25 7 25 6
3 12 4 12
21 10 20 10
13 20 13 19
27 12 26 12
18 16 17 16
12 8 13 8
12 20 13 20
15 18 14 18
11 20 12 20
7 5 7 4
17 17 17 16
4 13 4 12
5 13 5 12
12 2 11 2
25 12 26 12
19 16 18 16
27 7 27 6
4 14 4 13
17 14 17 15
2 12 3 12
27 1 26 1
2 11 2 12
7 1 7 2
4 15 4 14
12 21 12 20
9 17 9 16
25 2 25 1
16 18 15 18
13 2 12 2
19 17 19 16
18 11 18 10
7 0 7 1
17 18 16 18
19 15 19 16
12 22 12 21
20 17 19 17
1 12 2 12
8 1 9 1
18 18 17 18
6 1 7 1
29 4 28 4
16 12 16 11
13 21 13 20
20 15 19 15
10 20 11 20
12 23 12 22
25 13 25 12
3 15 4 15
21 15 20 15
28 12 27 12
14 20 13 20
9 3 9 4
7 16 7 15
3 14 4 14
27 13 27 12
13 22 13 21
8 13 8 12
17 19 17 18
28 7 27 7
25 14 25 13
6 14 7 14
7 17 7 16
24 11 24 10
14 21 13 21
9 18 9 17
6 17 7 17
15 21 14 21
24 12 25 12
11 22 12 22
12 7 11 7
14 22 13 22
5 14 5 13
3 16 3 15
6 3 7 3
18 14 17 14
17 20 17 19
18 13 18 14
1 13 1 12
7 11 7 12
22 15 21 15
26 13 25 13
17 21 17 20
29 12 28 12
27 4 27 5
22 7 22 8
15 22 15 21
18 20 17 20
18 12 18 11
12 24 12 23
12 25 12 24
2 15 3 15
13 25 12 25
16 22 15 22
17 22 16 22
13 7 13 8
10 17 9 17
15 8 15 9
6 18 6 17
11 24 12 24
13 23 13 22
5 1 6 1
27 14 27 13
11 21 12 21
12 26 12 25
10 1 10 2
11 26 12 26
18 21 18 20
3 17 3 16
20 18 20 17
11 19 11 18
13 24 13 23
11 1 11 2
9 20 10 20
4 9 5 9
13 26 12 26
3 18 3 17
8 20 9 20
13 13 13 14
20 19 20 18
26 14 26 13
6 0 7 0
6 5 7 5
10 0 10 1
10 26 11 26
8 0 7 0
6 6 6 5
9 11 9 12
5 18 6 18
23 11 23 10
19 19 20 19
11 25 11 26
27 0 27 1
7 6 7 5
14 25 13 25
13 27 13 26
9 26 10 26
5 0 5 1
10 27 10 26
10 21 10 20
17 23 17 22
5 3 6 3
10 25 10 26
25 15 25 14
3 19 3 18
7 20 8 20
19 20 19 19
20 16 20 15
24 15 25 15
8 26 9 26
14 11 13 11
4 2 5 2
20 20 19 20
6 16 7 16
17 12 16 12
11 27 10 27
19 14 19 15
7 10 7 11
21 20 20 20
18 22 18 21
13 28 13 27
28 1 27 1
14 28 13 28
21 21 21 20
3 9 4 9
28 8 28 7
20 1 19 1
25 16 25 15
18 23 18 22
5 19 5 18
21 17 20 17
27 11 26 11
22 20 21 20
8 27 8 26
1 11 2 11
22 21 21 21
1 10 1 11
16 23 17 23
16 21 17 21
23 20 22 20
4 3 5 3
4 4 4 3
17 1 18 1
2 9 3 9
3 20 3 19
21 14 21 15
22 19 22 20
14 27 13 27
16 24 16 23
8 25 8 26
14 9 15 9
16 14 16 15
17 24 17 23
1 15 2 15
12 13 13 13
10 28 10 27
29 13 29 12
9 19 9 20
7 25 8 25
7 27 8 27
8 28 8 27
28 6 28 7
2 18 3 18
11 12 11 11
0 12 1 12
7 24 7 25
4 11 4 12
4 0 5 0
19 21 18 21
2 19 3 19
18 5 19 5
28 0 27 0
19 22 18 22
10 22 10 21
29 5 29 4
2 20 2 19
2 21 2 20
23 12 24 12
24 16 24 15
9 0 10 0
18 6 17 6
22 0 22 1
27 10 27 11
15 25 14 25
21 22 21 21
1 16 1 15
25 8 25 7
14 29 14 28
2 22 2 21
3 22 2 22
15 1 15 2
15 26 15 25
20 22 19 22
4 1 4 2
14 19 14 18
23 19 22 19
3 4 4 4
25 17 25 16
9 14 10 14
3 2 4 2
12 1 11 1
18 19 17 19
22 22 22 21
0 16 1 16
26 16 25 16
26 17 26 16
6 24 7 24
0 11 0 12
16 25 16 24
8 14 7 14
12 5 11 5
9 13 8 13
21 23 21 22
26 7 26 6
7 26 7 27
24 20 23 20
19 18 19 17
6 8 7 8
4 20 3 20
6 26 7 26
21 19 21 20
2 23 2 22
4 8 4 9
21 16 20 16
24 21 24 20
1 21 2 21
19 23 18 23
22 14 21 14
26 18 26 17
13 5 12 5
5 4 4 4
3 1 3 2
15 17 14 17
16 26 15 26
27 17 26 17
25 3 24 3
2 1 3 1
23 16 24 16
10 19 11 19
22 23 22 22
28 17 27 17
26 9 25 9
13 29 13 28
5 5 6 5
23 22 22 22
8 29 8 28
18 7 17 7
7 28 7 27
20 23 19 23
6 27 6 26
19 8 18 8
3 0 4 0
26 15 26 14
2 4 3 4
5 26 6 26
28 18 28 17
26 2 25 2
2 24 2 23
13 12 13 11
27 16 27 17
7 21 7 20
6 25 7 25
16 5 17 5
24 22 24 21
4 26 5 26
24 7 25 7
25 22 24 22
11 17 10 17
29 0 28 0
24 23 24 22
23 13 23 12
5 15 4 15
3 10 3 9
15 27 14 27
24 24 24 23
20 21 20 22
26 4 26 5
7 29 8 29
29 18 28 18
4 16 3 16
22 18 22 19
25 23 24 23
7 22 7 21
4 19 4 20
17 11 18 11
21 24 21 23
25 4 24 4
23 18 23 19
21 25 21 24
6 7 6 8
12 14 12 15
24 25 24 24
6 29 7 29
1 4 2 4
16 27 16 26
25 24 25 23
20 25 21 25
3 21 3 22
0 10 0 11
0 4 1 4
20 26 20 25
24 14 24 15
21 26 21 25
16 19 16 18
26 3 26 4
24 17 24 16
0 3 0 4
26 23 25 23
21 9 21 10
2 13 1 13
4 7 4 8
1 17 1 16
21 7 20 7
29 11 29 12
19 24 19 23
5 25 6 25
15 28 14 28
12 27 12 26
5 6 6 6
17 25 16 25
14 13 14 14
0 5 0 4
1 9 1 10
12 29 13 29
1 1 2 1
2 2 2 1
16 28 15 28
6 19 5 19
14 10 13 10
23 23 23 22
12 12 12 13
0 15 1 15
0 9 0 10
27 15 27 14
19 25 19 24
21 6 20 6
24 26 24 25
0 2 0 3
26 19 26 18
3 8 4 8
4 10 4 11
15 29 14 29
16 29 16 28
26 22 26 23
2 0 2 1
3 26 4 26
9 25 9 26
3 27 3 26
14 12 15 12
22 17 22 18
1 5 0 5
24 19 24 20
15 0 15 1
18 24 17 24
0 21 1 21
2 5 2 4
16 1 17 1
14 26 15 26
14 5 13 5
10 18 11 18
26 20 26 19
28 14 27 14
2 17 3 17
24 27 24 26
25 25 24 25
8 10 9 10
1 24 2 24
27 9 27 10
5 24 6 24
2 6 2 5
27 22 26 22
29 19 29 18
3 7 4 7
17 13 18 13
7 19 6 19
26 21 26 20
5 11 4 11
3 28 3 27
29 1 28 1
22 24 21 24
0 20 0 21
27 8 27 9
0 8 0 9
23 9 24 9
25 20 24 20
28 10 27 10
23 27 24 27
5 16 6 16
3 13 2 13
28 9 27 9
2 14 2 13
9 21 10 21
16 4 16 5
24 13 25 13
12 0 12 1
23 0 24 0
26 25 25 25
6 11 5 11
16 20 16 21
22 25 22 24
15 13 15 14
15 19 14 19
1 2 2 2
16 6 16 5
4 27 3 27
2 28 3 28
28 13 28 12
24 18 24 17
14 23 13 23
4 21 3 21
25 18 26 18
14 1 14 2
22 3 21 3
29 8 28 8
23 15 24 15
22 12 23 12
1 28 2 28
1 25 1 24
1 8 0 8
17 28 16 28
4 5 5 5
18 15 17 15
23 24 22 24
5 23 5 24
6 23 6 24
26 26 26 25
29 20 29 19
20 14 21 14
7 7 6 7
16 13 16 12
18 28 17 28
13 0 12 0
0 17 0 16
1 3 1 2
26 24 26 25
7 23 7 22
1 22 2 22
0 13 1 13
20 0 20 1
25 0 24 0
27 25 26 25
28 25 27 25
4 24 5 24
29 14 29 13
14 0 14 1
8 15 7 15
21 27 21 26
27 26 27 25
28 26 28 25
4 28 3 28
17 27 17 28
23 17 24 17
0 1 1 1
25 21 24 21
25 27 24 27
0 24 1 24
0 19 0 20
5 27 5 26
20 12 20 11
12 9 12 8
3 3 3 4
28 15 28 14
18 27 18 28
21 18 20 18
7 18 6 18
23 26 23 27
15 6 16 6
16 7 16 6
8 9 7 9
17 29 17 28
10 23 10 22
23 21 24 21
18 25 19 25
8 24 7 24
9 22 9 21
24 28 24 27
1 23 1 22
29 26 28 26
28 19 29 19
29 3 29 4
4 17 4 16
28 27 28 26
27 21 26 21
0 14 0 13
0 7 0 8
22 13 23 13
2 3 3 3
29 27 28 27
12 28 12 27
1 0 2 0
18 17 18 18
20 27 20 26
27 19 26 19
27 18 27 19
0 22 0 21
8 18 7 18
6 20 7 20
0 25 0 24
14 24 14 25
29 28 29 27
0 18 0 19
28 11 27 11
27 20 27 19
5 10 4 10
5 7 5 6
22 26 23 26
26 8 25 8
13 6 13 7
6 22 6 23
9 24 8 24
28 3 29 3
18 0 18 1
8 23 7 23
21 28 21 27
2 10 3 10
14 7 13 7
4 18 4 19
26 27 25 27
19 12 18 12
16 17 15 17
2 26 3 26
19 0 18 0
11 29 12 29
28 21 27 21
4 23 4 24
29 6 29 5
5 29 6 29
22 27 23 27
3 6 2 6
14 8 14 7
15 24 16 24
21 12 20 12
8 5 7 5
1 20 1 21
24 29 24 28
6 21 7 21
21 11 20 11
29 10 29 11
28 22 28 21
27 27 27 26
0 0 0 1
6 28 7 28
4 22 4 23
23 28 24 28
27 2 26 2
19 9 18 9
28 23 28 22
5 28 5 29
16 0 16 1
2 7 3 7
8 21 9 21
23 14 23 15
25 28 24 28
21 29 21 28
10 29 11 29
0 28 1 28
20 29 21 29
3 25 3 26
15 23 15 22
0 26 0 25
18 26 18 25
1 7 2 7
3 29 3 28
3 11 3 12
29 25 29 26
18 29 18 28
5 21 6 21
28 24 28 25
19 29 18 29
14 6 14 5
23 25 23 24
26 0 26 1
1 29 1 28
0 23 0 22
26 10 26 9
4 6 4 5
19 10 19 9
25 29 25 28
29 15 28 15
1 26 2 26
1 14 1 15
27 28 27 27
6 15 6 14
1 6 1 5
29 7 29 6
3 23 2 23
8 19 8 20
27 24 27 25
9 28 8 28
29 17 29 18
13 1 12 1
11 23 11 24
6 10 6 9
2 25 3 25
8 11 8 10
5 17 4 17
15 5 16 5
20 24 20 25
22 16 23 16
25 26 26 26
28 28 28 27
19 28 18 28
1 27 1 28
1 18 0 18
29 16 29 15
9 23 9 24
2 16 1 16
28 16 28 17
11 28 11 27
17 0 18 0
17 26 17 27
3 5 3 6
5 8 5 9
27 23 26 23
27 3 28 3
28 2 27 2
28 20 27 20
19 11 20 11
23 29 23 28
29 22 28 22
15 20 16 20
26 29 25 29
5 22 5 21
20 13 20 12
22 29 23 29
25 19 25 20
22 28 21 28
9 27 9 26
21 13 22 13
19 26 19 25
11 0 12 0
2 27 1 27
19 13 20 13
0 29 0 28
2 29 2 28
12 6 12 7
29 23 28 23
28 29 28 28
8 17 7 17
11 10 12 10
0 27 0 28
6 4 6 3
29 29 28 29
4 25 3 25
4 29 5 29
29 21 28 21
17 2 16 2
19 27 20 27
15 7 14 7
20 28 20 29
27 29 27 28
5 20 6 20
22 11 21 11
9 29 10 29
11 9 12 9
10 24 10 23
2 8 1 8
1 19 0 19
29 9 29 8
29 24 29 23
29 2 29 3
0 6 0 5
3 24 4 24
26 28 26 27
8 22 9 22
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment