TCS -TR-A-13-64

TCS Technical Report

Efficient Computation of the Number of Paths in a
Grid Graph with Minimal Perfect Hash Functions
byHiroaki Iwashita, Yoshio Nakazawa,
Jun Kawahara, Takeaki Uno, and Shin-ichi Minato

Division of Computer Science
Report Series A
April 26, 2013

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Efficient Computation of the Number of Paths in a Grid
Graph with Minimal Perfect Hash Functions
Hiroaki Iwashita∗†‡

Yoshio Nakazawa§

Jun Kawahara¶

Takeaki Unok

Shin-ichi Minato‡†
April 26, 2013

Abstract
It is not easy to find the number of self-avoiding walks from (0, 0) to (n, n), because the number increases rapidly with the increase of n and mathematical formulafor calculating it is not known. Our challenge is to develop advanced algorithmic
techniques through efforts of finding the answer to the larger n. The idea of Knuth’salgorithm is so effective that it can compute the answer to n = 11 in a second andn = 21 in a few days, even though it is designed for general graphs. In this paper,
we specialize it in grid graphs and maximize space and time efficiency. Our program
have successfully computed the answer to n = 25, which had not known before.

1

Introduction

A path (way to go from a vertex to another vertex without visiting any vertex twice)in a grid graph is called a self-avoiding walk (SAW), which is known to be introducedby the chemist Flory as a model of polymer chains [1]. In spite of its simple definition,
many difficult mathematical problems are hidden behind the SAW [2, 3]. They include a
problem of counting the number of paths connecting opposite corners of a (n+1)×(n+1)
grid graph, which have become popular through a YouTube-animation [4]. The answer is2
2
known to grow as λ n +o(n ) and λ ' 1.7 [5]. When n = 10, it is about 1024 and cannot becounted one by one in a realistic time even if we could find trillions of paths in a second.
We are studying advanced algorithmic techniques through efforts of finding the answer
to the larger n. According to The On-Line Encyclopedia of Integer Sequences (OEIS) [6],∗ iwashita@erato.ist.hokudai.ac.jp† ERATO MINATO Discrete Structure Manipulation System Project, Japan Science and Technology

Agency, Sapporo, Japan.
‡ Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.
§ Amateur programmer.
¶ Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma, Nara, Japan.
k Principles of Informatics Research Division, National Institute of Informatics, Chiyoda, Tokyo, Japan.

1

2

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO(a) G3,3(b) Paths between 1 and 9

Figure 1: Paths in a graphRosendale computed the answers up to n = 11 in 1981 and Knuth computed the answer ton = 12 in 1995. Bousquet-Mélou et al. presented the answers up tp n = 19 in their paper[5] in 2005. Their algorithm is based on the method of Conway et al. [7], which makes
good use of the fact that the target is a grid graph. On the other hand, Knuth introduced analgorithm for general graphs called S IMPATH in 2008 [8][9, exercise 225 in 7.1.4], whichconstructs a zero-suppressed binary decision diagram (ZDD) [10] representing a set of allpaths between two vertices in a graph. We have extended the answers up to n = 21 in 2012by reimplementing S IMPATH to directly count the number of paths instead of building the
ZDD structure [11]. It would be notable that the implementation is not dedicated to grid
graphs but is made for general graphs.
We specialize it in grid graphs and maximize space and time efficiency. On the premisethat the graph is a square grid, we can foretell the exact number of entries in the hash tablefilled in the algorithm. It allows us to use a simple array with a minimal perfect hashfunction instead of an ordinary hash table, which has a large impact on actual space andtime efficiency. We improve it still more by additional techniques such as in-place update
and parallel processing.
This paper is organized as follows. Section 2 introduces the original algorithm forgeneral graphs. The basic idea specific to grid graphs is shown in Section 3. Detailed
techniques to further improve space and time efficiency are described in Section 4. Section 5 shows experimental results and Section 6 mentions some additional ideas. Finally,
conclusions are drawn in Section 7.

2

Original Algorithm for General Graphs

Input to the original algorithm [11] is an undirected graph G = (V, E) and two verticess,t ∈ V where V = {v1 , . . . , vm } is a set of vertices and E = {e1 , . . . , en } is a set of edges.
The output is the number of all paths between s and t. For example, if the input is a 3 × 3
grid graph and two vertices at opposite corners, the output will be 12 as shown in Figure 1.
The algorithm is a kind of dynamic programming. A path can be represented by asubset of edges E 0 ⊆ E. The algorithm performs breadth-first search in the 2E space that
corresponds to all decision patterns on edge selections. Figure 2 illustrates the computation for G3,3 , where dotted and solid branches represent exclusion and inclusion of theEfficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

3

Figure 2: Computation for G3,3
corresponding edge respectively. A branch is pruned when it makes an inconsistent situation with the final target, e.g. making a cycle or an unexpected endpoint.
Each node p at level i has a frontier state and an integer value. A frontier is a set ofthe vertices that are contiguous with both decided and undecided edges. The frontier stateis represented by a map, mate p : Vi → Vi ∪ {0}, where Vi ⊆ V is the frontier at level i. It
maintains information about path fragments formed by a set of selected edges as follows:v if vertex v is not a part of any path fragment,
mate p [v] = w if vertices v and w are endpoints of a path fragment,
0 if vertex v is an intermediate point of a path fragment.
An entry for mate p [v] is created when vertex v is entering the frontier and an entry formate p [v] is deleted when vertex v is leaving the frontier.
Since the mate table includes sufficient information of constraints for future edge selections, nodes with equivalent mate tables can be merged during the computation. The
integer values of merged nodes are summed. The final result is the value totaled at the leaf
node. This algorithm is implemented using a hash table of which keys are mate tables andvalues are integers.

4

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO(a) For general graphs(b) For plane graphs

Figure 3: Frontier state representation

3

Basic Idea for Grid Graphs

3.1

Frontier States

Let v(i, j) be the vertex at row i and column j of an n × n grid graph (1 ≤ i ≤ n, 1 ≤ j ≤ n)
and we compute the number of paths between v(1,1) and v(n,n) . We visit the vertices
in the order of v(1,1) , . . . , v(1,n) , v(2,1) , . . . , v(2,n) , . . . and make decisions on vertical line{v(i−1, j) , v(i, j) } and horizontal line {v(i, j−1) , v(i, j) }. The frontier at the step visiting v(i, j) is{v(i,1) , . . . , v(i, j) , v(i−1, j+1) , . . . , v(i−1,n) }.
The original algorithm keeps vertex identifiers of path endpoints in mate p (Figure 3a),while we can compress the information efficiently on the premise that the graph is embedded in the plane (Figure 3b). Pairs of path endpoints always form nested structure on thefrontier because no path fragments can intersect. We do not need to record all informationof endpoint pairs but record only whether they are left or right endpoints. Let s = c1 c2 · · · cn
be a string representing a frontier state at a step visiting v(i, j) where Σ = { , , , }and ck ∈ Σ is a character representing the state of vertex at the k-th column in the frontier:
if the k-th vertex is a left endpoint of a path fragment,
if the k-th vertex is a right endpoint of a path fragment,ck =if k = j and the k-th vertex is an intermediate point of a path fragment,otherwise.
We consider the endpoint connected to v(1,1) is always a right endpoint.
is a special
character only for c j , meaning that it is different fromas we cannot include the next
horizontal line {v(i, j) , v(i, j+1) }.
Examples of state transitions are shown in Figure 4. We have no alternatives of vertical line selections in every step, because {v(i−1, j) , v(i, j) } must be excluded if v(i−1, j) is
not an endpoint and {v(i−1, j) , v(i, j) } must be included if v(i−1, j) is an endpoint. Branches
are always made by selection of horizontal lines. A frontier state changes only when horizontal line {v(i, j−1) , v(i, j) } is included except for to changes. The state transition issummarized in Figure 5.
Since
pairs are nested, the number of valid frontier states is closely related to
Motzkin numbers [12]. Let x1 < x2 and M(x1 ,y1 )→(x2 ,y2 ) be a set of routes from coordinates(x1 , y1 ) to coordinates (x2 , y2 ) on x2 − x1 steps of (1, 1), (1, −1), or (1, 0) moves withoutEfficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

Figure 4: Examples of state transitions on a 6 × 6 grid graph

Current state

···

···
···
···
···
···
···
···
···
···
···
···
···

···
···
···
···
···
···
···
···
···
···
···
···

···

Next stateLine excluded
Line included
···
···
···
···
···
···
···
···
···
···
···
···
···
···
···
···
··· ········· ···
···
···
···
···
···
···
···
···
···
···
··· ········· ·········N/A (making cycle)······
N/A (branching)······N/A (branching)······N/A (branching)

Figure 5: State transition table

5

6

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO(a) Main states: M(0,1)→(6,0)(b) Blocked states: M(0,1)→(5,0)

Figure 6: Possible frontier states for a 6 × 6 grid graphvisiting negative y-coordinates. The n-th Motzkin number is given by Mn = M(0,0)→(n,0) .
They are given by recurrence relation:
M0 = M1 = 1 ,3(n − 1)Mn−2 + (2n + 1)Mn−1
Mn =
.
n+2

(1)

We divide frontier states into two classes: main states and blocked states. A main state
does not have and a blocked state has at the j-th position. Let Σ0 = Σ \ { }, S j bea set of frontier states after visiting j-th column, and S0 ⊂ S j be a set of main states. S0
does not include , i.e. S0 ⊂ Σ0 n . It corresponds to M(0,1)→(n,0) (Figure 6a) where , ,andcharacters are associated with (1, 1), (1, −1), and (1, 0) moves respectively. The
number of main states is given by:
Nn = M(0,1)→(n,0) = Mn+1 − Mn .

(2)

Let S00j = S j \ S0 be a set of blocked states after visiting j-th column. As all blocked states
haveat the j-th position, it can be ignored in enumerating S00j . That corresponds toM(0,1)→(n−1,0) (Figure 6b) and the number of blocked states is given by:
Nn−1 = M(0,1)→(n−1,0) = Mn − Mn−1 .

(3)Therefore, the number of frontier states is:
Nn + Nn−1 = Mn+1 − Mn−1 .

3.2

(4)

Basic Algorithm

Since the domain of frontier states has become clear, we can define a minimal perfect hashfunction ϕ j : S j → {1, . . . , Nn + Nn−1 } for each column position 1 ≤ j ≤ n. It allows us
to use a simple array instead of an ordinary hash table to keep intermediate results. A
simple implementation is to define some lexicographical order on the frontier states, andto calculate the order of a given state string by scanning its characters one by one. An
improved implementation is described later in Section 4.2.
Algorithm 1 shows the basic method for computing the number of paths in a grid graph.
The count array keeps the integers that represent the numbers of cases for all frontier statesat the current step. For example, if we apply this algorithm to a 24 × 24 grid graph using
56-byte integers, count requires (M25 − M23 ) × 56 bytes = 413 gigabytes of memory. The
tmp array is a temporary storage, which is the same size as count.

Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

Algorithm 1 Computing the number of paths in a grid graph
1: count[k] ← 0 for all 1 ≤ k ≤ Nn + Nn−1 ;n}|{z
2: count[ϕ1 (· · · )] ← 1;
3: for i = 1 to n do
4:
for j = 1 to n − 1 do
5:tmp[k] ← 0 for all 1 ≤ k ≤ Nn + Nn−1 ;6:for all s ∈ S j do
7:t ← the next state of s when {v(i, j) , v(i, j+1) } is excluded;8:tmp[ϕ j+1 (t)] ← tmp[ϕ j+1 (t)] + count[ϕ j (s)];9:u ← the next state of s when {v(i, j) , v(i, j+1) } is included;10:
if u is defined then11:
tmp[ϕ j+1 (u)] ← tmp[ϕ j+1 (u)] + count[ϕ j (s)];12:
end if13:
end for14:
count[k] ← tmp[k] for all 1 ≤ k ≤ Nn + Nn−1 ;15:
end for16:
tmp[k] ← 0 for all 1 ≤ k ≤ Nn + Nn−1 ;17:for all s ∈ Sn do18:t ← the string made from s by replacing its with ;19:
tmp[ϕ1 (t)] ← tmp[ϕ1 (t)] + count[ϕn (s)];20:
end for21:
count[k] ← tmp[k] for all 1 ≤ k ≤ Nn + Nn−1 ;22: end fornz}|{
23: return count[ϕ1 (
···
)];

7

8

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO

Figure 7: Data dependency

4

Techniques to Improve the Efficiency

4.1

In-place Update of the Array

If we eliminate the tmp array, the memory usage of Algorithm 1 can be reduced by half.
We put it into practice by reordering the access to the count array elements. Let 1 ≤ j ≤n − 1, α ∈ Σ0 j−1 , β ∈ Σ0 n− j−1 , and c ∈ Σ0 . We choose the minimal perfect hash functions
that holds the following relations:
ϕ j (s) = ϕ j+1 (s)for all s ∈ S0 , andϕ j (α cβ ) = ϕ j+1 (αc β ) for all α cβ ∈ S00j where c ∈ Σ0 .

(5)Hereafter, we write as count(s) to denote count[ϕ j (s)] because position j is not importantanymore.
Data dependency in the count array is illustrated in Figure 7. For instance,in Figure 7 represents a set of the frontier states that haveat position j andatposition j + 1 when we are processing a horizontal line between columns j and j +toshow that a value read from count(αβ ) is
1. A directed edge fromadded into count(αβ ) for all αβ ∈ S0 . Since count(αβ ) is used to calculate the new value of count(αβ ), we update count(αβ ) before adding the valueβ ) into count(αβ ). Storage for count(αβ ) and count(αβ ) isof count(αthe same location. We update count(αβ ) and count(αβ ) simultaneously because
they depend on each other.

4.2

Fast Mapping from Frontier States to Serial Numbers

Hash functions are evaluated frequently and have a large impact to the total speedup. In
this section, we describe a minimal perfect hash function for main states. One for blocked
states can be made in the same way by ignoring and considering that the string size isn − 1. The hash function for all frontier states can be made with their combination.
The minimal perfect hash function for main states ϕ 0 : S0 → {1, . . . , |S0 |} is implemented
as a sum of two subfunctions:
ϕ 0 (s) = ϕL0 (l) + ϕR0 (r)(6)

where l is the left half of string s and r is the right half of s. The sizes of s, l, and r aren, m = bn/2c, and n − m, respectively. This composition works because the main states

Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

9

correspond to M(0,1)→(n,0) . The left half must be in M(0,1)→(m,h) and the right half must
be in M(m,h)→(n,0) , where 0 ≤ h ≤ m. We allocate serial numbers to main states in orderof h. Let baseh + i denote the i-th serial number of the main states passing through (m, h).
It is given by:
base0 = 0 ,baseh+1 = baseh + M(0,1)→(m,h) · M(m,h)→(n,0) .

(7)

When 1 ≤ il ≤ M(0,1)→(m,h) is a serial number of string l in M(0,1)→(m,h) and 1 ≤ ir ≤M(m,h)→(n,0) is a serial number of string r in M(m,h)→(n,0) , the subfunctions can be defined as:
ϕL0 (l) = baseh + (il − 1) · M(m,h)→(n,0) ,(8)
ϕR0 (r) = ir .
Main states are implemented as 2n-bit codes under such 2-bit code assignments as= 00, = 01, and = 10. We divide a 2n-bit code into the left 2m-bit subcode andthe right 2(n − m)-bit subcode. The two subfunctions can be implemented by the simple
arrays that are indexed directly by the subcodes. The total size of the two arrays is about
2n+1 and is small enough in comparison with the size of the count array.

4.3

Fast Enumeration of All Main States

As shown in Section 4.1, we want to enumerate all frontier states in some specific orderfor in-place update of count entries. It is also acceptable to enumerate all main states insome specific order and visit each blocked state while visiting a main state related to it.
A simple implementation would be a single array of states sorted in the desired order.
Although it is very fast and accepts any state order, it consumes memory as much as thecount array. We introduce a method with much better memory efficiency for visiting mainstates in lexicographic order. We divide main states again into the left and right halves. A
left state array lstate has ordered collection of hl, hi values where l is a left state subcodeand l corresponds to M(0,1)→(m,h) . A right state array rstateh (0 ≤ h ≤ m) has ordered
collection of right state subcodes in M(m,h)→(n,0) . All main states can be visited by thefollowing double loop:
for each hl, hi in lstate dofor each r in rstateh do
visit lr;end forend for.
Running time of this double loop would be almost the same as the single array implementation because most of the time is consumed in the inner loop and it is just scanning anarray in the same way as the single array implementation.

10

4.4

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO

Shared Memory Parallel Processing

Let s = c1 c2 · · · cn be a state string and the current step is for the horizontal line connecting
columns j and j + 1. As shown in Figure 5, the transition patterns of state strings havemuch locality: except for modification of c j and c j+1 , at most one position can be changed
from to or from to .
We can partition the states into 2n−2 groups across which no transition occurs, basedon an (n − 2)-bit binary code “g(c1 ) · · · g(c j−1 ) g(c j+2 ) · · · g(cn )” where g : Σ0 → {0, 1} isdefined to be
0 if c = ,(9)g(c) =
1 if c = or c = .
It is suitable for shared memory parallel processing since data update within a group is
independent of other groups. We use the leftmost m-bit of the binary code for task allocation, where m is decided to make enough number of tasks and not to make each task
too small. Actually, m ' n/2 is a convenient choice in combination with the techniquedescribed in Section 4.3.

5

Experimental Results

We have compared the original sequential program for general graphs [11] and three newprograms for grid graphs:
GGCount-SB a sequential program based on the techniques in Section 3 and Section 4.1
using count array of 56-byte integers,
GGCount-SF an improved version of GGCount-SB with the techniques in Section 4.2
and Section 4.3, and
GGCount-PF a parallel version of GGCount-SF with the technique in Section 4.4, using
12 CPU cores.
All those programs are written in C++. Experiments were performed on 2.67GHz Intel
Xeon E7-8837 CPUs with 1.5TB memory, running 64-bit SUSE Linux Enterprise Server
11. Results for (n + 1) × (n + 1) grid graphs are shown in Table 1 and Table 2. Incomparison with the original implementation [11], space and time efficiency has been
improved five times and ten times respectively in the sequential processing (GGCountSF); time improvement of one another digit is achieved by the parallel processing using
12 CPU cores (GGCount-PF). GGCount-SF used slightly more memory than GGCountSB, while it achieved three times speedup.
As the parallel program runs fast enough, it is worth exchanging space costs for time
costs using the Chinese Remainder Theorem in the same way as [5]. Using a 64-bit modular arithmetic version of GGCount-PF, we have succeeded in finding the answer to n = 25
as well as confirming the past results for n = 22, 23, 24 by Spaans [6]. The numbers areshown in Table 3. For n = 25, we performed 9 runs with coprime moduli, of which eachEfficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

Table 1: Memory usage (megabytes)
n
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[11]
3
7
18
44
145
432
1290
3676
9993
34298
95329
297260∼700000>1500000

GGCount-SB
1
2
6
15
40
110
304
847
2367
6641
18688
52723
149108422634

GGCount-SF
1
3
6
15
41
111
306
849
2376
6663
18729
52791
149254422861

GGCount-PF
1
3
6
15
41
111
306
849
2376
6663
18729
52791
149254422861

Table 2: Computation time (seconds)
n
10
11
12
13
14
15
16
17
18
19
20
21
22
23

[11]
0.2
0.7
2.4
8.6
38.0
140.1
508.1
1763.76003.017961.961570.0208001.7>604800>604800

GGCount-SB
0.2
0.5
1.6
5.1
16.7
53.7
172.5
554.1
1755.05687.218121.456263.6
178439.6554159.8

GGCount-SF
0.0
0.1
0.3
1.0
4.7
14.0
45.8
146.4
459.3
1759.64616.1
17917.2
53671.1
170475.7

GGCount-PF
0.0
0.0
0.1
0.2
0.5
1.9
7.9
20.9
67.6
212.4
652.0
3244.35695.021313.011

12

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO

run took 18 hours on 30 CPU cores and used 480 gigabytes of memory. We also confirmed
a successful run for n = 26 on the same machine using 2 days and 1400 gigabytes; it willtake three weeks to get the exact answer.
It was not difficult to modify Algorithm 1 to compute the number of cycles [13] insteadof paths. The numbers of main and blocked states for cycle enumeration are Mn and Mn−1
respectively; count array is initialized to be 1 for· · · ; the answer is the total numberof cycles found during the main loop. The answers to (n+1)×(n+1) grid graphs (n ≤ 25)
are shown in Table 4. For n = 25, we performed 9 runs with coprime moduli, of which
each run took 9 hours on 30 CPU cores and used 260 gigabytes of memory.

55435429355237477009914318489061437930690379970964331332556958646484008407334885544566386924020875711242060085408513482933945720

12371712231207064758338744862673570832373041989012943539678727080484951695515930485641394550792153037191858028212512280926600304581386791094

8402974857881133471007083745436809127296054293775383549824742623937028497898215256929178577083970960121625602506027316549718402106494049978375604247408

24

25

22

23

31374751050137102720420538137382214513103312193698723653061351991346433379389385793965576992246021316463868
755970286667345339661519123315222619353103732072409481167391410479517925792743631234987038883317634987271171404439792

21

1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844
3962892199823037560207299517133362502106339705739463771515237113377010682364035706704472064940398

20

18

19

6344814611237963971310297540795524400449443986866480693646369387855336
1782112840842065129893384946652325275167838065704767655931452474605826692782532

172266745568862672746374567396713098934866324885408319028
68745445609149931587631563132489232824587945968099457285419306

16

227449714676812739631826459327989863387613323440

14

1564528039343270018963357185158482118
69450664761521361664274701548907358996488

13

11

12

1568758030464750013214100
182413291514248049241470885236

103266598486981642
41044208702632496804

89575780564
789360053252

6

7

8512
1262816

4

3

5

12
184

2

2

#path

1

n

Table 3: The number of paths between opposite corners of an (n + 1) × (n + 1) grid graphEfficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions13

317698324732748859895908541034955194127994098630324812636624826258997224150342908049795056399595180923955046092422345

22780223929670574691223507874671963939543945238061927803443588158966878341201898099174425109669737384772981749340922723497405087

4976037374055300327445222400443546830498798429935446621053707681453137859077914419511395195468579271956320503531047087399178114550443364089

3310986696180301144320032978096652329596523503435882543114890295466038827631907053110552071003521069706315474677769157738758382711047460804662161917199

22

23

24

25

1747591025316879549979786952655665410563226741505288698037078203555463416502484945892166703679171
13498757056229389624710286314663261122166783333470228470330291400847321675907180262434015144922092043438151

21

19

20

828994780940754546935155193723999456397444612351458013833196066822882956458645
689454183113508056830743257694610073918027584884435945831932331941835810292154647051579

1833953844023386621558992302713698922032806419330748312822875435
3038442783379807358500340876029076156976090161888565971315511241074745

17

15

16

120285789340533859558405124213592877516931371715
1157093265735985301622023713535739570361128480949044165

1436954917962039884953387868334644457
38157703688577845304445530851242055267353

13109331355810135629946698361371

11

1227359264067916806101

8988808811046283595068099

79603841648931
2318527339461265

6

101222363487150371

5

213
9349

3

4

1
13

2

#path

1

n

Table 4: The number of cycles in an (n + 1) × (n + 1) grid graph

14
H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO

Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions

15

Figure 8: The number of frontier states against n6Additional Techniques

6.1

Using Line Symmetry

The problem is line symmetrical with respect to the line passing through v(1,1) and v(n,n) ;the number of paths starting from {v(1,1) , v(1,2) } is exactly the same as the number ofpaths starting from {v(1,1) , v(2,1) }. It means that the answer can be computed by doubling
the number of paths for one size. This method, however, would not contribute to muchcomputational reduction because the two cases are merged soon in the breadth-first searchalgorithm.
One could make some algorithm utilizing line symmetry by introducing diagonal frontiers instead of horizontal frontiers. That approach seems difficult because it have to overcome faster growth of the number of frontier states than using horizontal frontiers. Figure 8 compares the peak numbers of frontier states appeared in the algorithm for generalgraphs [11].

6.2

Using Point Symmetry

If we use the point symmetry of the problem, Algorithm 1 can be stopped at the middle
of computation. We can compute the answer by enumerating every pair of main statesthat matches. Figure 9 shows that paths are completed by A =and B =(C =) when B (C) is turned over and they are combined. The
total number of paths found here iscount(A) × (count(B) + count(C)) .

16

H. I WASHITA , Y. NAKAZAWA , J. K AWAHARA , T. U NO , AND S. M INATO

Figure 9: Example of matching
Numbers stored in count grows exponentially against the number of loop iterationsin the algorithm. This technique reduces the memory usage by half because integer size
can be halved when we only compute numbers for the upper half of the graph. As forthe time cost, however, this technique might be at a disadvantage. Time growth of thematching process against n was larger than that of the basic algorithm in our preliminary
experiments.

7

Conclusions

We have maximized space and time efficiency by focusing only on grid graphs. On thepremise that the graph is a square grid, we were able to clarify the exact set of possible
frontier states and to analyze their transition patterns. They allowed us to use simple arrays
instead of dynamic hash tables and to integrate various techniques, such as in-place update
and parallel processing, into the algorithm. Our algorithm for grid graphs have achieved
double-digit performance improvement on the original algorithm for general graphs. It
have extended the numbers recorded in OEIS [6][13] and have verified those past resultscorrectly.
The YouTube-animation [4] demonstrated the importance of algorithmic techniques
against combinational explosion. We were able to realize it through this challenge. We
would like to thank all staff involved in the animation and its 1.3 million viewers who took
interest in this issue, which was a major force to boost our study.

REFERENCES

17

References[1]

Paul J. Flory. “The Configuration of Real Polymer Chains”. In: Journal of Chemical
Physics 17 (3 1949), pp. 303–310.

[2]

N. Madras and G. Slade. The Self-Avoiding Walk. Birkhäuser, 1993. ISBN: 978-08176-3891-7.

[3]

E. W. Weisstein. Self-Avoiding Walk. URL: http://mathworld.wolfram.com/
Self-AvoidingWalk.html.

[4]

MiraikanChannel. Time with class! Let’s count! URL: http : / / www . youtube .
com/watch?v=Q4gTV4r0zRs.

[5]

M. Bousquet-Mélou, A. J. Guttmann, and I. Jensen. “Self-avoiding Walks Crossing a Square”. In: Journal of Physics A: Mathematical and General 38 (2005),
pp. 9159–9181.

[6]

The On-Line Encyclopedia of Integer Sequences. A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n × n grid.
URL: http://oeis.org/A007764.

[7]

A. R. Conway, I. G. Enting, and A. J. Guttmann. “Algebraic Techniques for Enumerating Self-avoiding Walks on the Square Lattice”. In: Journal of Physics A:
Mathematical and General 26 (1993), pp. 1519–1534.

[8]

D. E. Knuth. Don Knuth’s Home Page. URL: http://www-cs-staff.stanford.
edu/~uno/.
[9] D. E. Knuth. The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1. 1st. Addison-Wesley Professional, 2011. ISBN: 0321751043.
[10]

S. Minato. “Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems”. In: Proceedings of the 30th ACM/IEEE Design Automation Conference.
1993, pp. 272–277.

[11]

H.Iwashita, J. Kawahara, and S. Minato. ZDD-Based Computation of the Number
of Paths in a Graph. Tech. rep. TCS-TR-A-12-60. Division of Computer Science,
Graduate School of Information Science and Technology, Hokkaido University,
2012. URL: http://www-alg.ist.hokudai.ac.jp/tra.html.

[12]

R. Donaghey and L. W. Shapiro. “Motzkin Numbers”. In: Journal of Combinatorial
Theory, Seires A 23.3 (1977), pp. 291–301.

[13]

The On-Line Encyclopedia of Integer Sequences. A140517 Number of cycles in ann × n grid. URL: http://oeis.org/A140517.