Preparing frontier information for each node, and applying to path counting in undirected graph

General
1

I have revised zdd-based path counting predicates of mine
to udg_path_count/4, which works for undirected graph (UDG).
udg_path_count/4 internally assumes that nodes of graph are linearly ordered, details of which is not open to the user even when nodes are given as integers.

The new version prepares so called frontier information for each node x by

frontier(x) = min{ y | y is directly linked to x, or y = x}.

The frontier function is used to pruning paths on the way of
of incremental adding of nodes and links to decide
whether the current partial paths (mates) are extendable to complete ones later in the process, in other words, to decide whether the partial paths are dead or alive at the current state of information.

udg_path_count/4 is surely after idea by D. Knuth and S. Minato
at least partially. However, I have been always afraid that
I am missing something on them. I lost energy since some point of time to search and read relevant papers in details.

Nevertheless, I would post later with an experiment which will use families of characteristic functions from the given set of links instead of families of sets of mates proposed by Knuth and given links.
So far, I never paid attention to use such characteristic functions,
but now I am thinking it would be worth to try as a new kind of exersise for me on zdd programming. I will appreciate for relevant
information from interested readers.

Here is log of queries on udg_path_count/4 with short description for usage.

%! udg_path_count(+Ends, +Links, -C, +S).
	Links is a set of undirected links.
	C is unified with the number of paths which connect A and B where Ends = (A - B).

%! rect_path_count(+rect(W, H), -C, +S).
is a short hand of rect_path_count(p(0,0)-p(W,H), rect(W,H), S).

%! rect_path_count(+Ends, +rect(W, H), -C, +S).
C is unified with the number of paths which connect A and B where Ends = (A - B).
walking along undirected grid graph of nodes  p(i,j)  (0=< i =<W, 0 =< j=< H)
visiting nodes at most once.

% ?- zdd udg_path_count(a-d, [a-b, b-c, c-d], C).
%@ C = 1.
% ?- zdd udg_path_count(a-x, [a-b, b-c, c-d], C).  % fail.
%@ No link at a or x
%@ false.

% A big circular graph:  1 -> 2 -> 3 -> ... -> n -> 1
% ?- N = 10000,
%	findall(A,	( between(1, N, I), I<N, J is I + 1, A=(I-J)), Ls),
%	time((( zdd udg_path_count(1-2,[1-N |Ls], C)))).
%@ % 18,088,296 inferences, 3.146 CPU in 3.232 seconds (97% CPU, 5750507 Lips)
%@ N = 10000,
%@ Ls = [1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, 8-9, ... - ...|...],
%@ C = 2.


% ?- time((zdd rect_path_count(p(0,0)-p(1,1), rect(6,6), C))).
%@ % 53,063,549 inferences, 4.575 CPU in 4.610 seconds (99% CPU, 11597388 Lips)
%@ C = 244306498.
% ?- time((zdd rect_path_count(p(3,3)-p(4,4), rect(6,6), C))).
%@ % 118,881,643 inferences, 10.427 CPU in 10.567 seconds (99% CPU, 11401216 Lips)
%@ C = 78979.

% ?- time((zdd rect_path_count(rect(7,7), C))).
%@ % 546,869,654 inferences, 41.653 CPU in 42.714 seconds (98% CPU, 13129283 Lips)
%@ C = 789360053252.
% ?- time((zdd rect_path_count(rect(8,8), C))).
%@ % 2,517,503,191 inferences, 306.954 CPU in 311.285 seconds
%@ C = 3266598486981642.

% Counting paths in complete graph.
% ?- N = 4, findall(I-J, ( between(1, N, I), between(1, N, J), I < J), Ls),
%  time(zdd udg_path_count(1-N, Ls, C)), length(Ls, Len), writeln(Ls).
%@  zid = 195
%@ 	[(1->4)]
%@ 	[(1->3),(3->4)]
%@ 	[(1->3),(2->3),(2->4)]
%@ 	[(1->2),(2->4)]
%@ 	[(1->2),(2->3),(3->4)]
%@ -------------------
%@ % 17,182 inferences, 0.001 CPU in 0.001 seconds (93% CPU, 13867635 Lips)
%@ C = 5,

% ?- N = 11, findall(I-J, ( between(1, N, I), between(1, N, J), I < J), Ls),
%  time(zdd udg_path_count(1-N, Ls, C)).
%@ % 1,835,060,694 inferences, 233.677 CPU in 238.492 seconds (98% CPU, 7852993 Lips)
%@ N = 11,
%@ Ls = [1-2, 1-3, 1-4, 1-5, 1-6, 1-7, 1-8, 1-9, ... - ...|...],
%@ C = 986410.
3

What you describe above, is it the basis for your recent result:

Can it be done with tabling? Or do you throw away certain
non active frontier information in the course of your counting?
I have the feeling tabling is not suited for the best algorithms,

since it lacks a form of automatic forgetting. I am currently
facinated by this forgetting, it has a also a link to streaming,
depending on how much I am allowed to forget, I can replace

two streams by one stream with a sliding window. I can show
that easily for the Pascal triangle example. In the Pascal
triangle the window size is W = 2. The size can be derived

from the constraint C =:= C2+1 here:

4

No. Table can not apply due to the L, R of triple t(a, L, R) is the index
of array which may dynamically change. Instead manual gc specific to ZDD array, which as you might thought.

I think the Iwashita etal’s ('world record holder") paper you mentioned does some nice method based on Motzkin’s number (assuming planar graph), which I am trying to understand. I am not sure whether the day will come for me to understand.

GC on ZDD array 
		/*****************************************
		*     copy, slim, ord_copy, pred_copy    *
		*****************************************/

%!	slim_gc(+X, -Y) is det.
%	Do slim_iterms(X, Y), and call garbage_collect.

% ?- zdd.
% ?- X<<{[a,b]}, slim_gc(X, Y), psa(Y).
% ?- X<<{[a,b]}, slim_gc(X, Y, q_atom_slim), psa(Y).

slim_gc(X, Y):- slim_iterms(X, Y), !, garbage_collect.

%!	slim_iterms(+X, -Y) is det.
%	Remove all redundant iterms (was zdds) that are irrelevant to
%	those specified in X.

% ?- _<<pow([a,b]), X<<pow([c,d,e]), psa(X), slim_gc(X, Y), psa(Y).

slim_iterms(X, Y):-
	b_getval(zdd_node, #(_,V)),
	initial_basic_state([], #(A,H)),
	b_setval(zdd_node, A),
	b_setval(zdd_hash, H),
	!,
	reset_memo_call(slim_iterms(X, Y, V)).

% ?- V = #(0, t(a, 0, 1)),   slim_iterms(2, Y, V), psa(Y).
slim_iterms([], [], _):-!.
slim_iterms([X|Xs], [Y|Ys], V):-!,
	slim_iterms(X, Y, V),
	slim_iterms(Xs, Ys, V).
slim_iterms(X, Y, V):-
	(	integer(X) -> slim_iterm(X, Y, V)
	;   Y = X
	).

%
slim_iterm(X, X, _):- X< 2,!.
slim_iterm(X, Y, V):- memo(slim_iterm(X)-Y),
	(	nonvar(Y) -> true
	;	arg(X, V, T),
		(	T = t(A, L, R) -> slim_iterm(L, L0, V)
		;	T = t(A, R) -> L0 = 0
		),
		slim_iterm(R, R0, V),
		cofact(Y, t(A, L0, R0))
	).
5

Thats somehow the reason why I recently became interested
in sliding window techniques. Motzkin numbers are related
to Motzkin paths along a corridor. The corridor thing makes

it pretty much bounded. Yesterday I tried formulating paths
as constraints over vertexes and edges. If the vertex X points
to the vertex Y, via an edge H, we can encode path distance:

(X - Y - 1)*H #= 0

From constraints we get matrices. And from matrices we
might indeed get neural processor speed ups. Or maybe
Hofstadter butterflies, make readings into physics.

6

I don’t think it is good idea at all that preparing “frontier information” for each node. In fact with x given a node, it is just the least node y such that link y-x exists. It might be easy to conclude such “frontier” is useless for graphs like complete graph. To be honest, I do not grasp the notion of frontier yet.

7

The Hiroaki Iwashita frontier is relatively easy to grasp visually,
there are undirected graph versions, and planar undirected
graph versions:

image
image418×187 13.3 KB

https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf

Whats more difficult to derive some Prolog code from it. Basically
the frontier grows non-deterministially and can be used
for counting somehow:

image
image496×243 9.78 KB

https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf

A branching is a sign of non-determinism. Its like a Prolog
choice point in Prolog backtracking. I guess hashing is used to
find common states that come from different brachings.

image
image542×170 20.6 KB

https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf

Each state in the above can be reached by different branchings.
You have a similar pattern in the Pascal triangle, each node has
two parents. Which can be computed with sliding window N = 2.

8

It seems that they don’t use arrays of t(a, i, j), where i, j are (possibly large) integers. Instead they use something like light-weight representation using balanced parens list. Thanks for hints.