For n>=2, let G(n) be an undirected complete graph with nodes 1, 2, …, n, and S(n) the set of simple paths in G(n) which connects node 1 and 2. For example, G(2) = ({1,2}, {1-2}), G(3) = ({1,2,3}, {1-2, 2-3, 1-3}), G(4) = ({1,2,3,4}, {1-2, 1-3, 1-4, 2-3, 2-4, 3-4}), … where i - j means doubleton {i, j} for distinct i, j. The cardinality of S(n) is easily computed as codes below.
I wrote two codes, say, Z(n) in ZDD version, and L(n) in ordinal list processing to compare with them as below.
Brief conclusion is: Z(15) took time 140 seconds to enumerate S(15), but as for L(n), even L(13) failed for long enough timeout setting.
As for this specific problem of enumerating S(n), it showed that ZDD version Z(n) is much better than the ordinal list processing L(n) as sample queries below, though I am not sure my codes L(n) below is of the standard level in Prolog programming, and I have to be looking forward to seeing someone shows smarter codes.
Two codes Z(n) and L(n) are similar in that both are based on simple recursion on n . In addition, as for L(n) I applied the table directive, but it showed “out of resources” for table. I guess this is because of list arguments of the tabled predicate. In semantics, they are sets. Fortunately ZDD treats them as sets in nature. On the other hand unless given list/set distinction, there is no way for table other than preparing different entry for each p([a,b,c]), p([b,a,c]), p([a,c,b]), etc, I guess.
I hope this post some hint that ZDD programming in SWI-Prolog might be useful.
Z(n) queries in ZDD version.
% ?- zdd.
% ?- paths_of_complete_graph(2, X), card(X, C).
%@ X = 2,
%@ C = 1.
% ?- paths_of_complete_graph(3, X), card(X, C).
%@ X = 5,
%@ C = 2.
% ?- paths_of_complete_graph(4, X), card(X, C).
%@ X = 19,
%@ C = 5.
% ?- paths_of_complete_graph(5, X), card(X, C).
%@ X = 66,
%@ C = 16.
% ?- time((paths_of_complete_graph(10, X), card(X, C))).
%@ % 2,330,986 inferences, 0.328 CPU in 0.406 seconds (81% CPU, 7106556 Lips)
%@ X = 22574,
%@ C = 109601.
% ?- time((paths_of_complete_graph(11, X), card(X, C))).
%@ % 7,972,199 inferences, 0.872 CPU in 1.035 seconds (84% CPU, 9145734 Lips)
%@ X = 75638,
%@ C = 986410.
% ?- time((paths_of_complete_graph(12, X), card(X, C))).
%@ % 26,995,652 inferences, 3.237 CPU in 3.792 seconds (85% CPU, 8338858 Lips)
%@ X = 252547,
%@ C = 9864101.
% ?- time((paths_of_complete_graph(13, X), card(X, C))).
%@ % 92,585,306 inferences, 11.948 CPU in 13.743 seconds (87% CPU, 7749265 Lips)
%@ X = 839844,
%@ C = 108505112.
% ?- time((paths_of_complete_graph(14, X), card(X, C))).
%@ % 283,495,642 inferences, 37.943 CPU in 43.815 seconds (87% CPU, 7471541 Lips)
%@ X = 2783757,
%@ C = 1302061345.
% ?- time((paths_of_complete_graph(15, X), card(X, C))).
%@ % 969,329,257 inferences, 139.219 CPU in 158.912 seconds (88% CPU, 6962626 Lips)
%@ X = 9214955,
%@ C = 16926797486.
Z(n) codes in ZDD version
paths_of_complete_graph(2, X):-!, zdd_singleton(1-2, X).
paths_of_complete_graph(N, X):- N>2,
N0 is N - 1,
paths_of_complete_graph(N0, Y),
add_new_node(N, Y, Z),
zdd_join(Y, Z, X).
%
add_new_node(_, X, 0):- X<2, !.
add_new_node(N, X, Y):- memo(insnode(N, X)-Y),
( nonvar(Y) -> true %, write(.) % many hits.
; cofact(X, t(A, L, R)),
add_new_node(N, L, L0),
A = I-J,
zdd_ord_insert([I-N, J-N], R, R0),
add_new_node(N, R, R1),
zdd_insert(A, R1, R2),
zdd_join_list([L0, R0, R2], Y)
).
L(n) queries in ordinal list processing version
% ?- time(count_paths_in_comp_udg(12, C)).
%@ % 61,408,802 inferences, 5.956 CPU in 7.545 seconds (79% CPU, 10310346 Lips)
%@ C = 9864101 .
% ?- time(count_paths_in_comp_udg(13, C)).
%@ % 727,235,629 inferences, 76.901 CPU in 85.308 seconds (90% CPU, 9456730 Lips)
%@ C = 108505112 .
% ?- call_with_time_limit(160, time(count_paths_in_comp_udg(14, C))).
%@ % 1,618,867,619 inferences, 264.140 CPU in 330.791 seconds (80% CPU, 6128827 Lips)
%@ ERROR: Unhandled exception: Time limit exceeded
L(n) codes in ordinary list processing version
paths_in_comp_udg(2, [[1-2]]).
paths_in_comp_udg(N, Ps):- N>2,
N0 is N - 1,
paths_in_comp_udg(N0, P0s),
insert_node(N, P0s, P0s, Ps).
insert_node(_, [], Ps, Ps):-!.
insert_node(K, [P|R], P0s, Ps):-
insert_node_to_path(K, [], P, P0s, P1s),
insert_node(K, R, P1s, Ps).
insert_node_to_path(_, _, [], Ps, Ps):-!.
insert_node_to_path(K, Q, [I-J|P], P0s, Ps):-
math:reverse(Q, [I-K,J-K|P], P0),
insert_node_to_path(K, [I-J|Q], P, [P0|P0s], Ps).