Dimers

Dimers is a package for simulating the dimer model on a 2D rectangular grid, using an algorithm of Kenyon, Propp, and Wilson. Dimers also provides support for loop erased random walks and Wilson's algorithm on an arbitrary graph.

showgraphics(drawgraph(dimersample(20)))

We can also compute the height function associated with the dimer sample:

dimerheight(dimersample(20))

11x11 Array{Int64,2}:
  0   1   0   1   0  1   0   1   0   1   0
 -1  -2  -1  -2  -1  2  -1  -2  -1  -2  -1
  0  -3  -4  -3   0  1   0   1   0  -3   0
 -1  -2  -1  -2  -1  2  -1  -2  -1  -2  -1
  0  -3   0   1   0  1   0   1   0   1   0
 -1  -2  -1   2  -1  2  -1  -2  -1   2  -1
  0   1   0   1   0  1   0   1   0   1   0
 -1  -2  -1   2  -1  2   3   2  -1  -2  -1
  0   1   0   1   0  1   0   1   0   1   0
 -1   2   3   2   3  2   3   2   3   2  -1
  0   1   0   1   0  1   0   1   0   1   0

Wilson takes a graph as its first argument and an array of true/false values specifying the roots.

showgraphics(drawgraph(Wilson(G,[[true];[false for i=1:length(G.vertices)-1]])))

LERW(G,v0,roots) samples a loop-erased random walk on the graph G starting from the vertex whose index in G.vertices is v0 stopped upon hitting one of the vertices v for which roots[v] is true.

import Graphs
n = 100
G = Graphs.adjlist((Int64,Int64),is_directed=false)

for i=1:n
    for j=1:n
        Graphs.add_vertex!(G,(i,j))
    end
end

roots = Bool[v[1] == 1 || v[1] == n || v[2] == 1 || v[2] == n  for v in
G.vertices];

v0 = find(x->x==(div(n,2),div(n,2)),G.vertices)[1]

lerw = LERW(gridgraph(n),v0,roots)
for i=1:length(lerw)-1
    add_edge!(G,lerw[i],lerw[i+1])
end

showgraphics(drawgraph(G))