A progress report on zdd programming for counting paths in rectangular grid graph

General
1

EDIT [2022/01/18]
I got the number of all paths starting at the origin p(0,0) to the end p(12,12) running for about 10 hours on an M1 macbook pro 32G bytes.

64528039343270018963357185158482118. (about 10^35)

I saw activity monitor showing about 50giga byte memory use at some final point of computation. As the physical memory size is 32G, this sounds strange for me, but I guess this is what they call virtual memory.

I want to close my zdd library for SWI but unfortunately now a couple of ideas which is new for me is coming up for larger size of the nodes of the rectangular grid graphs. More worse, I am always far from sure that I use essential idea of Knuth’s idea on frontier computation and mates. I am afraid I will be easy lost in the future.

Here is pretty printing codes for the paths. SWI-Prolog is handy for this.

% ?- print_rect_path(rect(1,1), C).
%@ p(0,0)->p(1,0)->p(1,1)
%@ p(0,0)->p(0,1)->p(1,1)
%@ C = 2.

% ?- print_rect_path(rect(2,1), C).
%@ p(0,0)->p(1,0)->p(2,0)->p(2,1)
%@ p(0,0)->p(1,0)->p(1,1)->p(2,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(2,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(1,0)->p(2,0)->p(2,1)
%@ C = 4.

% ?- print_rect_path(rect(3,1), C).
%@ p(0,0)->p(1,0)->p(2,0)->p(3,0)->p(3,1)
%@ p(0,0)->p(1,0)->p(2,0)->p(2,1)->p(3,1)
%@ p(0,0)->p(1,0)->p(1,1)->p(2,1)->p(3,1)
%@ p(0,0)->p(1,0)->p(1,1)->p(2,1)->p(2,0)->p(3,0)->p(3,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(2,1)->p(3,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(2,1)->p(2,0)->p(3,0)->p(3,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(1,0)->p(2,0)->p(3,0)->p(3,1)
%@ p(0,0)->p(0,1)->p(1,1)->p(1,0)->p(2,0)->p(2,1)->p(3,1)
%@ C = 8.

% ?- print_rect_path(rect(2,2), C).
%@ p(0,0)->p(1,0)->p(2,0)->p(2,1)->p(2,2)
%@ p(0,0)->p(1,0)->p(2,0)->p(2,1)->p(1,1)->p(1,2)->p(2,2)
%@ p(0,0)->p(1,0)->p(1,1)->p(2,1)->p(2,2)
%@ p(0,0)->p(1,0)->p(1,1)->p(1,2)->p(2,2)
%@ p(0,0)->p(1,0)->p(2,0)->p(2,1)->p(1,1)->p(0,1)->p(0,2)->p(1,2)->p(2,2)
%@ p(0,0)->p(1,0)->p(1,1)->p(0,1)->p(0,2)->p(1,2)->p(2,2)
%@ p(0,0)->p(0,1)->p(1,1)->p(2,1)->p(2,2)
%@ p(0,0)->p(0,1)->p(1,1)->p(1,2)->p(2,2)
%@ p(0,0)->p(0,1)->p(1,1)->p(1,0)->p(2,0)->p(2,1)->p(2,2)
%@ p(0,0)->p(0,1)->p(0,2)->p(1,2)->p(2,2)
%@ p(0,0)->p(0,1)->p(0,2)->p(1,2)->p(1,1)->p(2,1)->p(2,2)
%@ p(0,0)->p(0,1)->p(0,2)->p(1,2)->p(1,1)->p(1,0)->p(2,0)->p(2,1)->p(2,2)
%@ C = 12.

print_rect_path(Rect, C):- count_mqp(Rect, C, Z, S),
	forall( set_at(Path, Z, S),
		    (	pretty_path(p(0,0), Path, U0),
				writeln(U0)
		    )).

pretty_path(A, P, Q):- list_of_node_on_path(A, P, R),
	maplist(term_string, R, R0),
	atomic_list_concat(R0, '->', Q).

list_of_node_on_path(A, [], [A]):-!.
list_of_node_on_path(A, Path, [A|Atoms]):- select(X->Y, Path, Path0),
	( A = X -> B = Y
	; A = Y -> B = X
	),
	list_of_node_on_path(B, Path0, Atoms).

End of EDIT[2022/01/18].

EDIT [2021/10/06]
Tuning the program a little bit, I have run it for a square grid graph with 12 x 12 = 144 nodes. It took about 10 hours to count the paths.

% ?- time(test(rect(11,11), C)).
42,385,957,864 inferences, 39194.974 CPU in 39841.529 seconds (98% CPU, 1081413 Lips)
 C = 182413291514248049241470885236.

End od EDIT

I have found that, for path counting problem on undireted graph, say rect(w, h)
my zdd library in my package pac works better than what I had thought.

The undirected graph rect(w, h) is a familiar rectangular grid graph, which has (w+1)(h+1) nodes and 2wh+ w+h (undirected) links, with start node (0,0) and end node (w, h). For example, rect(1,1) has nodes (0,0),(0,1),(1,0),(1,1), and links (0,0)-(0,1), (0,0)-(1,0), (0,1)-(1,1), (1,0)-(1,1). Clearly rect(1,1) has totally 2 paths from the start to the end.

The following log shows that my zdd library counts the number of paths of rect(w,h) upto w=h=10.

  % ?- time(test(rect(6,6), C)).
%@ % 68,484,229 inferences, 9.811 CPU in 9.895 seconds (99% CPU, 6980701 Lips)
%@ C = 575780564.

% ?- time(test(rect(7,7), C)).
%@ % 355,978,304 inferences, 56.560 CPU in 57.168 seconds (99% CPU, 6293794 Lips)
%@ C = 789360053252.

% ?- time(test(rect(8,8), C)).
%@ % 2,093,257,106 inferences, 364.796 CPU in 368.593 seconds (99% CPU, 5738151 Lips)
%@ C = 3266598486981642.

% ?- time(test(rect(9,9), C)).
%@ % 12,014,796,025 inferences, 2313.454 CPU in 2328.010 seconds (99% CPU, 5193445 Lips)
%@ C = 41044208702632496804.

% ?- time(test(rect(10,10), C)).
%@ % 72,951,316,690 inferences, 14599.908 CPU in 14671.299 seconds (100% CPU, 4996697 Lips)
%@ C = 1568758030464750013214100.

For a long time, my zdd library counts for only upto rect(5, 5) in a reasonable time (one night). This time, I have added a few of simple functions on garbage collecting in term_hash table in zdd working spaces. Although I am not sure for the moment which functions mainly has given such progress, an
d this might still sound for zdd experts poor result, I would like to keep enjoying zdd programming in SWI-Prolog.

Kuniaki Mukai