<p>It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.</p>

<p>Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$.  Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.  </p>

<p>I actually think that there's a more straightforward method for choosing a cycle.  Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it.  This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.</p>

<p>Assume that you have chosen a path which is part of your random cycle.  Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path.  Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph).  For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one. </p>

<p>In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm.  Thus, a cycle can be uniformly chosen.</p>

<p>I currently have a <a href="https://cstheory.stackexchange.com/questions/6400/approximation-for-counting-the-number-of-simple-s-t-paths-in-a-general-graph">stackexchange question</a> requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.</p>

CC BY-SA 3.0
2011-05-05T04:41:53.660Z
2011-05-05T04:41:53.660Z
2017-04-13T12:32:28.167Z
bbejot
<p>In connection with the <a href="http://www.puzzle-loop.com/">Slither Link</a> puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.</p>

<p>One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?</p>

<p>Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?</p>

<p>ETA: See <a href="http://11011110.livejournal.com/214995.html">this blog post</a> for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.</p>

CC BY-SA 2.5
2011-03-16T01:23:20.490Z
How many simple cycles are there for $2\times n$ grids?  Did you work it out for $3\times n$ as well?  Your struck-out sentence, I think, still holds: there's not believed to be a simple closed form, at least not for simple lattice cycles ("self-avoiding polygons" or "closed self-avoiding walks") with a given perimeter or a given area.
mjqxxxx
CC BY-SA 2.5
2011-03-16T07:12:33.570Z
For 2xn grids the numbers are as given in http://oeis.org/A059020. For 3xn I'm pretty sure they are 6,40,213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247,... (not in OEIS). I set up the transfer matrix to calculate it by hand but I compared it to a machine-generated matrix and the only entry they differed the hand one was correct and the machine one was wrong. (This should show up in the 3x3 case — the machine matrix would have allowed an octomino with a hole in the center.)
David Eppstein
CC BY-SA 2.5
2011-03-16T12:59:18.083Z
You should send that sequence to Neil Sloane so he can put it in the OEIS.
Peter Shor 
CC BY-SA 2.5
2011-03-16T14:10:27.210Z
It seems like a transfer matrix for $3 \times 3$ should be straightforward as long as you consider X-X and X-Y as different cases.  In any case you've got 1,13,213,...  Is http://oeis.org/A140517 ("Number of cycles in an $n \times n$ grid") not the right sequence?
mjqxxxx
CC BY-SA 2.5
2011-03-16T15:46:12.073Z
My program is not yet capable of generating correct counts for arbitrary fixed widths fully automatically, without manual calculation of the transfer matrix, but it's only a small amtter of programming until it is. Once that happens (so that I have two different calculations that agree on the same numbers) I'll send an update to OEIS. Yes, A140517 looks right, and again I can doublecheck that once my code works more generally.
David Eppstein
CC BY-SA 2.5
2011-03-19T13:23:57.380Z
@David: As far as I understand, counting doesn't seem to yield sampling in this case since we'd need self-reducibility.  Being constrained on a grid looks to be an obstacle, and we would need a counting algorithm for more general problem such as the number of cycles in a plane graph.  Am I right?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-19T15:09:08.820Z
@Yoshio: the transfer matrix method of counting cycles on grids of fixed width can easily be turned into a random generation algorithm. The reducibility in that case is to patterns that can be extended to a single cycle.
David Eppstein
CC BY-SA 2.5
2011-03-20T01:48:47.783Z
@David: Thank you.  Probably, it's time for me to learn the transfer matrix method more thoroughly.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-20T18:24:41.387Z
@David: You just wasted two hours of my life with that link to the puzzle.. Thx!
domotorp
CC BY-SA 3.0
2011-05-05T20:02:59.067Z
Here is a heuristic idea with no justification that it should work: do a random walk on the squares for some number of steps, say much larger than the covering time of the $n-1 \times n-1$ grid. A random walk on the squares is what it sounds like: from the current square choose one of its neighbors at random. Then choose the last $k$ (distinct) squares visited during the random walk. This is a simply connected region of $k$ squares: is it a uniformly random simply connected region of $k$ squares?
Sasho Nikolov
CC BY-SA 3.0
2011-05-06T00:18:06.307Z
@Sasho, your algorithm would have to be modified so that it always yielded a cycle. As it currently is, you could have a repeated vertex on the circuit surrounding the $k$ cells. Also, it could create multiple independent cycles by enclosing 1 or more cells.
bbejot
CC BY-SA 3.0
2011-05-06T01:02:17.283Z
@bbejot: it was silly of me not to see that. ok, nevermind..i was thinking about the standard random walk method of generating random spanning trees, btw.
Sasho Nikolov
CC BY-SA 2.5
2011-03-14T21:16:28.843Z
The boundary of the sets counted by the OEIS sequence are not necessarily simple cycles, for example for 3x3, one of the 218 has all squares except the middle, and another four are given by further removing one corner.
Colin McQuillan
CC BY-SA 2.5
2011-03-14T23:36:59.880Z
Oops, thanks for the correction. I calculated the numbers of cycles in 2xn grids (being careful only to count simple cycles), matched it in OEIS, and found sequences in OEIS that generalize that, but as you observe there's more than one possible generalization and the one in OEIS isn't the one I actually want.
David Eppstein
<ds.algorithms><randomness><markov-chains><integer-lattice>
Random self-avoiding lattice cycle within a given bounding box
David Eppstein
# Random self-avoiding lattice cycle within a given bounding box

(Asked by: username_0 on 2011-03-12)

In connection with the [Slither Link](http://www.puzzle-loop.com/) puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.

One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?

Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?

ETA: See [this blog post](http://11011110.livejournal.com/214995.html) for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.

**Tags:** ds.algorithms, randomness, markov-chains, integer-lattice
> **Comments:**
> **username_7**: The boundary of the sets counted by the OEIS sequence are not necessarily simple cycles, for example for 3x3, one of the 218 has all squares except the middle, and another four are given by further removing one corner.  
> **username_0**: Oops, thanks for the correction. I calculated the numbers of cycles in 2xn grids (being careful only to count simple cycles), matched it in OEIS, and found sequences in OEIS that generalize that, but as you observe there's more than one possible generalization and the one in OEIS isn't the one I actually want.  
> **username_1**: How many simple cycles are there for $2\times n$ grids?  Did you work it out for $3\times n$ as well?  Your struck-out sentence, I think, still holds: there's not believed to be a simple closed form, at least not for simple lattice cycles ("self-avoiding polygons" or "closed self-avoiding walks") with a given perimeter or a given area.  
> **username_0**: For 2xn grids the numbers are as given in http://oeis.org/A059020. For 3xn I'm pretty sure they are 6,40,213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247,... (not in OEIS). I set up the transfer matrix to calculate it by hand but I compared it to a machine-generated matrix and the only entry they differed the hand one was correct and the machine one was wrong. (This should show up in the 3x3 case — the machine matrix would have allowed an octomino with a hole in the center.)  
> **username_2**: You should send that sequence to Neil Sloane so he can put it in the OEIS.  
> **username_1**: It seems like a transfer matrix for $3 \times 3$ should be straightforward as long as you consider X-X and X-Y as different cases.  In any case you've got 1,13,213,...  Is http://oeis.org/A140517 ("Number of cycles in an $n \times n$ grid") not the right sequence?  
> **username_0**: My program is not yet capable of generating correct counts for arbitrary fixed widths fully automatically, without manual calculation of the transfer matrix, but it's only a small amtter of programming until it is. Once that happens (so that I have two different calculations that agree on the same numbers) I'll send an update to OEIS. Yes, A140517 looks right, and again I can doublecheck that once my code works more generally.  
> **username_3**: @David: As far as I understand, counting doesn't seem to yield sampling in this case since we'd need self-reducibility.  Being constrained on a grid looks to be an obstacle, and we would need a counting algorithm for more general problem such as the number of cycles in a plane graph.  Am I right?  
> **username_0**: @Yoshio: the transfer matrix method of counting cycles on grids of fixed width can easily be turned into a random generation algorithm. The reducibility in that case is to patterns that can be extended to a single cycle.  
> **username_3**: @David: Thank you.  Probably, it's time for me to learn the transfer matrix method more thoroughly.  
> **username_4**: @David: You just wasted two hours of my life with that link to the puzzle.. Thx!  
> **username_5**: Here is a heuristic idea with no justification that it should work: do a random walk on the squares for some number of steps, say much larger than the covering time of the $n-1 \times n-1$ grid. A random walk on the squares is what it sounds like: from the current square choose one of its neighbors at random. Then choose the last $k$ (distinct) squares visited during the random walk. This is a simply connected region of $k$ squares: is it a uniformly random simply connected region of $k$ squares?  
> **username_6**: @Sasho, your algorithm would have to be modified so that it always yielded a cycle. As it currently is, you could have a repeated vertex on the circuit surrounding the $k$ cells. Also, it could create multiple independent cycles by enclosing 1 or more cells.  
> **username_5**: @bbejot: it was silly of me not to see that. ok, nevermind..i was thinking about the standard random walk method of generating random spanning trees, btw.  

---

## 1 answers

### Answer by username_6 on 2011-05-05. Score: 1

It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$. Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle. Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it. This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle. Let the set of vertices on this path be $C$ and let $v\_s$ and $v\_e$ be the endvertices of the path. Also let $N$ be the set of neighbors of $v\_e$ which are not in $C$ (note that there are only up to 3 in this particular graph). For each $u \in N$ count the number of $u$-$v\_s$ paths in the induced graph $G[V - (C - \{v\_s, v\_e \} ) ]$. Then choose a neighbor, $u$, of $v\_e$ weighted on the paths just counted. Add the edge $(v\_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm. Thus, a cycle can be uniformly chosen.

I currently have a [stackexchange question](https://cstheory.stackexchange.com/questions/6400/approximation-for-counting-the-number-of-simple-s-t-paths-in-a-general-graph) requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.


---

