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.